Как удалить дубликаты из массива чисел

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

Знаете ли вы стандартное решение через хеширование, его сложность и готовые средства .NET. Следом спрашивают, сохраняется ли порядок, и просят решение без дополнительной памяти.

Как отвечать

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

• LINQ: numbers.Distinct().ToArray(). O(n) по времени и памяти, внутри хеш-набор. На практике порядок первого вхождения сохраняется, но документация называет результат неупорядоченным, так что это деталь реализации;
• HashSet<int> и цикл: if (seen.Add(x)) result.Add(x);. Метод Add возвращает false для дубля, поэтому одна операция и проверяет, и добавляет. Порядок сохраняется гарантированно, это лучший ответ на собеседовании;
• new HashSet<int>(numbers): короче всего, но порядок перечисления HashSet не гарантирован;
• сортировка и два указателя: Array.Sort, затем проход, который сдвигает уникальные элементы в начало. O(n log n) без дополнительной коллекции, но исходный порядок теряется;
• известный диапазон: если числа, скажем, от 0 до 1000, хватит bool[] или BitArray, это быстрее хеширования.

Упомяните DistinctBy из .NET 6 для объектов по ключу и то, что для своих классов нужны корректные Equals и GetHashCode либо IEqualityComparer<T>. На горячем пути цикл с HashSet, созданным с заданной ёмкостью (new HashSet<int>(numbers.Length)), обычно выигрывает у LINQ по выделениям памяти.

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

Пишут вложенный цикл или List.Contains внутри цикла. Это O(n²), и на массиве в сто тысяч элементов разница с хеш-набором видна без профилировщика.

Утверждают, что HashSet хранит элементы в порядке добавления. После удалений освободившиеся ячейки занимают новые элементы, порядок перечисления меняется, и тест, проходивший на маленьком примере, падает.

Не уточняют про порядок и сразу сортируют. Из { 3, 1, 3, 2, 1 } получается { 1, 2, 3 }, хотя интервьюер ждал { 3, 1, 2 }, и решение засчитывают частично.