Какие базовые алгоритмы вы знаете?

Что проверяют

Не память на названия, а умение выбрать алгоритм и структуру данных под задачу и оценить сложность. Следом обычно дают задачу или спрашивают, что на самом деле делает List<T>.Sort и за сколько работает поиск в Dictionary.

Как отвечать

Перечисляйте группами, сразу с оценкой сложности и примером из .NET:

• сортировка: пузырьком O(n²) для понимания, слиянием O(n log n) и стабильная, быстрая O(n log n) в среднем и O(n²) в худшем случае. Array.Sort и List<T>.Sort используют интроспективную сортировку и нестабильны, а LINQ OrderBy стабилен;
• поиск: линейный O(n) и бинарный O(log n) по отсортированному массиву. Array.BinarySearch при промахе возвращает отрицательное число, побитовое дополнение места вставки, его разворачивают оператором ~;
• хэширование: Dictionary<TKey,TValue> и HashSet<T> дают O(1) в среднем, если у ключа корректные GetHashCode и Equals;
• деревья и кучи: SortedDictionary и SortedSet построены на красно-чёрном дереве, O(log n). PriorityQueue<TElement,TPriority> появилась в .NET 6, это минимальная куча;
• графы: обход в ширину через Queue<T>, в глубину через рекурсию или Stack<T>, Дейкстра на PriorityQueue для неотрицательных весов;
• приёмы для задач: два указателя, скользящее окно, префиксные суммы, динамическое программирование на примере рюкзака или наибольшей общей подпоследовательности.

Если просят написать код, проговаривайте сложность по времени и памяти до реализации и проверяйте граничные случаи: пустой массив, один элемент, дубликаты.

Где спотыкаются

Называют стек и очередь алгоритмами. Это структуры данных, на них строятся алгоритмы, и интервьюер это различает.

Пишут бинарный поиск с (lo + hi) / 2. На больших индексах сумма переполняет int, безопаснее lo + (hi - lo) / 2.

Используют глубокую рекурсию на больших данных. StackOverflowException в .NET не перехватывается и завершает процесс, поэтому DFS на большом графе лучше писать с явным стеком.