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

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

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

Как отвечать

Массив в Java это объект фиксированной длины с элементами одного типа, лежащими в памяти подряд. Длина задаётся при создании и не меняется, читается как поле length, а не как метод.

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

Операции добавления у массива нет вовсе: расширение это создание нового массива и копирование.

int[] a = {1, 2, 3};
int[] b = Arrays.copyOf(a, a.length + 1); // O(n)
b[b.length - 1] = 4;

Arrays.sort(a);                    // O(n log n)
int i = Arrays.binarySearch(a, 2); // O(log n)

Дальше сравнение со списком на массиве: внутри тот же массив, но с запасом, поэтому добавление в конец амортизированное O(1), а удаление из середины по-прежнему O(n). Массив выигрывает по памяти на примитивах: int лежит в нём как есть, а в коллекции каждое значение упаковано в объект.

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

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

Не знают про ковариантность массивов. Ссылку типа Object[] можно направить на массив строк, а при попытке положить туда чужой тип получить ArrayStoreException уже в рантайме; у обобщённых типов такой дыры нет, и это довод в пользу коллекций.

Берут массив примитивов ради скорости там, где узкое место совсем в другом месте. На небольших объёмах разница незаметна, а код становится хрупким: ручное изменение размера, отсутствие проверок и ошибки на границах, которые всплывают как ArrayIndexOutOfBoundsException.