Какова временная сложность решения с сортировкой и проходом по массивам?

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

Умеете ли вы сложить стоимость шагов решения и знаете ли, как на самом деле работает Array.prototype.sort в JavaScript. Следом обычно просят решить ту же задачу без сортировки или спрашивают, почему сортировка чисел выдала странный порядок.

Как отвечать

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

• сортировка: O(n log n). V8 с 2018 года использует TimSort, он стабильный и на почти упорядоченных данных близок к O(n). Стабильность sort требует стандарт начиная с ES2019. Дополнительная память O(n);
• проход: O(n), или O(n + m) для двух указателей по двум массивам;
• итог: шаги идут последовательно, поэтому складываются: O(n log n + n) = O(n log n). Для двух массивов разного размера честнее оставить O(n log n + m log m).

Затем предложите альтернативу: с Set или Map та же задача часто решается за O(n + m) в среднем, но с памятью O(n) на структуру. Сортировка выигрывает, если данные уже отсортированы или нужен упорядоченный результат.

Два нюанса JavaScript проверяют почти всегда. По умолчанию sort() сравнивает элементы как строки: [10, 9, 1].sort() даст [1, 10, 9], для чисел нужен компаратор (a, b) => a - b. И sort() меняет исходный массив, что в React ломает сравнение состояния по ссылке; новую копию даёт toSorted() из ES2023 или [...arr].sort().

Во фронтенде это не абстракция: сортировка большого списка прямо в рендере повторяется при каждом обновлении компонента, поэтому результат кешируют через useMemo.

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

Перемножают шаги: «сортировка n log n, потом проход n, итого n² log n». Последовательные шаги складываются, перемножаются только вложенные.

Пишут filter с includes по второму массиву и считают это линейным. На деле это O(n·m).

Повторяют, что быстрая сортировка деградирует до O(n²) на уже отсортированном массиве. Это верно только для наивного выбора опорного элемента, а V8 быструю сортировку в sort давно не использует.