Какова сложность доступа к элементу массива по индексу

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

Понимаете ли вы, откуда в теории берётся O(1) и насколько это правда для массивов JavaScript. Хороший кандидат знает, что в JS массив это особый объект, и может рассказать, когда движок перестаёт хранить его как настоящий массив. Следом часто спрашивают про push и shift.

Как отвечать

Классический ответ: O(1), потому что элементы лежат подряд и адрес считается как начало плюс индекс, умноженный на размер элемента. Для JS стоит добавить, что спецификация ECMAScript сложность не обещает: массив там описан как объект со строковыми ключами и особым свойством length. Константный доступ обеспечивают движки.

Как это устроено в V8:

• плотные массивы: элементы лежат в непрерывном хранилище, arr[i] действительно O(1) и очень быстрый. V8 различает виды элементов: только малые целые, числа с плавающей точкой, произвольные значения;
• дырявые массивы: new Array(5) или запись arr[10] в массив длины 3 создают пропуски. Такой вид элементов движок оптимизирует хуже и обратно в плотный уже не переводит;
• словарный режим: если массив сильно разрежен, например arr[1000000] = 1 на пустом массиве, V8 хранит элементы в хэш-таблице. Доступ остаётся O(1) в среднем, но с заметно большей константой;
• типизированные массивы: Float64Array, Uint8Array всегда лежат в непрерывном ArrayBuffer, это самый предсказуемый вариант для графики и больших объёмов чисел.

Для контраста назовите операции, которые константными не являются: indexOf, includes и find проходят по массиву за O(n), unshift сдвигает все элементы.

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

Отвечают, что массив в JavaScript всегда непрерывный блок памяти. Интервьюер спросит про arr[1000000] = 1, и ответ придётся менять на ходу.

Путают доступ по индексу с поиском. Вызов arr.includes(id) внутри map по другому массиву даёт O(n·m), и на списках в несколько тысяч элементов это уже заметно в интерфейсе. Для таких проверок заранее строят Set.

Удаляют элемент через delete arr[i]. Он оставляет дыру, length не меняется, а массив переходит в дырявый вид. Для удаления нужен splice, который сдвигает хвост за O(n), или filter, создающий новый массив.