Что такое массивы и какова сложность основных операций с ними

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

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

Как отвечать

Сначала классическая часть: массив это непрерывная память, доступ и запись по индексу O(1), поиск по значению O(n), вставка и удаление в середине O(n), добавление в конец амортизированное O(1).

Дальше уточнение про JavaScript, которого и ждут. Массив здесь объект, а не блок памяти фиксированного типа. Движок держит быстрое представление с плотным хранением, пока индексы идут подряд и элементы однородны; дырки, огромные индексы и удаление через delete переводят массив в словарное представление, где обращение по индексу становится походом в хеш-таблицу.

Стоимость методов:

• push и pop это амортизированное O(1);
• shift, unshift и splice это O(n), они двигают хвост;
• indexOf, includes, find, filter, map и reduce это O(n);
• sort это O(n log n), в современных движках устойчивая;
• копия через slice или расширение это O(n).

Если нужен частый поиск по ключу, массив меняют на Map или Set, где проверка принадлежности в среднем константная.

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

Копят результат в reduce через расширение массива: на каждом шаге создаётся новая копия, и линейный проход превращается в квадратичный. Дешевле накапливать в один массив, а неизменяемость обеспечивать одной копией в конце.

Удаляют элемент через delete. Длина не меняется, на месте остаётся дырка, массив съезжает в медленное представление, а методы обхода ведут себя с дырками по-разному. Удаление это splice или фильтр с новым массивом.

Зовут sort без компаратора и получают сравнение строк: десятка встаёт между единицей и двойкой. И забывают, что sort меняет исходный массив на месте, а значит правит состояние, которое считали неизменяемым, и React не увидит изменения по ссылке.