Как реализовать фильтрацию массива с сохранением уникальных элементов и порядка

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

Знание стандартной библиотеки Swift и асимптотики: сможете ли вы убрать дубли за O(n), не потеряв порядок. Попутно смотрят на протокол Hashable и умение написать обобщённое расширение. Следом просят убрать дубли по полю, например по id.

Как отвечать

Идиоматичное решение укладывается в расширение на Sequence:

extension Sequence where Element: Hashable {
    func uniqued() -> [Element] {
        var seen = Set<Element>()
        return filter { seen.insert($0).inserted }
    }
}

Проговорите, почему так:

• Set.insert возвращает кортеж (inserted, memberAfterInsert), поэтому проверка и вставка идут одним хэшированием, без отдельного contains;
• сложность: O(n) по времени в среднем и O(n) по памяти на множество. Можно добавить seen.reserveCapacity, чтобы избежать перераспределений;
• порядок: сохраняется первое вхождение, потому что filter проходит последовательность по порядку. Если нужно последнее, идите с конца и разворачивайте результат;
• по ключу: для моделей сравнивайте не весь объект, а поле: Set<ID> и seen.insert($0.id).inserted;
• без Hashable: при одном Equatable остаётся проверка через contains в уже собранном массиве, это O(n²).

Упомяните готовые варианты. В пакете Swift Algorithms есть uniqued() и uniqued(on:), в Swift Collections есть OrderedSet, который хранит уникальные элементы в порядке вставки. NSOrderedSet из Foundation тоже решает задачу, но теряет типизацию. Для самого решения Foundation не нужен: Set и Array живут в стандартной библиотеке.

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

Пишут Array(Set(array)). Дубли уходят, но порядок у Set не определён и может меняться даже между запусками программы из-за случайного зерна хэширования.

Реализуют Hashable вручную и хэшируют не те поля, что сравнивают в ==. Равные по смыслу объекты попадают в разные корзины, и дубли остаются.

Пишут вложенный цикл или contains по результату для Hashable типов. На массиве в десятки тысяч элементов это заметно тормозит главный поток, а интервьюер ждёт именно O(n).