Что такое массив как структура данных

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

Понимаете ли вы, что стоит за индексацией за константное время, и знаете ли, чем питоновский список отличается от массива в классическом смысле. Вопрос про кругозор за пределами синтаксиса.

Как отвечать

Массив это непрерывный участок памяти из ячеек одинакового размера. Адрес элемента вычисляется арифметикой от начала, поэтому доступ по индексу это O(1), а соседние элементы попадают в кэш процессора вместе, что и делает перебор быстрым.

Сложность операций: чтение и запись по индексу O(1), поиск по значению O(n), вставка и удаление в середине O(n) из-за сдвига хвоста, добавление в конец у динамического массива амортизированное O(1).

В Python классического массива нет, зато есть три разных инструмента. Список это динамический массив указателей на объекты: он растёт с запасом, хранит что угодно, но сами объекты разбросаны по памяти. Тип из модуля array хранит числа одного типа плотно, без обёрток. Массив из numpy добавляет к плотному хранению векторные операции, ради которых его обычно и берут.

import array

nums = array.array("i", [1, 2, 3])
nums.append(4)     # амортизированное O(1)
nums.insert(0, 0)  # O(n), сдвигается весь хвост

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

Называют список массивом и на этом останавливаются. Разница существенная: список хранит ссылки, поэтому миллион чисел в нём занимает кратно больше памяти, чем в плотном массиве, и перебор проигрывает из-за промахов кэша.

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

Обещают строго O(1) на добавление в конец. Время амортизированное: когда запас исчерпан, происходит перевыделение с копированием всех элементов, и одна отдельная вставка оказывается линейной. Там, где важно время отклика отдельной операции, об этом надо помнить.