Какова алгоритмическая сложность удаления дубликатов с использованием объекта для хранения ключей?

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

Знаете ли вы сложность решения и, главное, подводные камни объекта в роли хеш-таблицы. Ответ «O(n) по времени и памяти» интервьюер ждёт сразу, а дальше спрашивает, что станет с числами, объектами и порядком и почему не Set.

Как отвечать

Сложность: один проход по массиву, проверка и запись ключа в среднем O(1), итого O(n) по времени и O(n) дополнительной памяти на объект и результат. Для сравнения, arr.filter((x, i) => arr.indexOf(x) === i) даёт O(n²), и на массиве в сто тысяч элементов разница заметна без профайлера.

Дальше покажите, что понимаете ограничения объекта:

• ключи всегда строки: 1 и '1' схлопнутся в один ключ, а Object.keys вернёт строки, то есть [1, 2, 1] превратится в ['1', '2'];
• объекты в массиве: все приводятся к строке '[object Object]' и считаются одним значением;
• прототип: у {} есть унаследованные свойства, и проверка if (!seen[item]) для строки 'toString' или 'constructor' решит, что элемент уже встречался. Лечится Object.create(null) или проверкой через Object.hasOwn;
• порядок: целочисленные ключи Object.keys отдаёт по возрастанию, поэтому исходный порядок чисел теряется.

Современный ответ: [...new Set(arr)]. Та же сложность O(n), значения не приводятся к строкам, порядок вставки сохраняется, сравнение идёт по SameValueZero, так что NaN тоже схлопывается корректно. Для объектов с дублями по полю берите Map с ключом id: new Map(items.map(i => [i.id, i])), в значении останется последний дубль.

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

Называют O(1) без оговорки «в среднем». Это средняя оценка для хеш-таблицы, в плохом случае операции дороже.

Не замечают, что функция вернула строки вместо чисел, и дальше result.includes(1) внезапно даёт false.

Предлагают Set для массива объектов и ждут удаления дублей по содержимому. Set сравнивает ссылки, и два одинаковых по полям объекта для него разные.