В эпоху Google очень легко искать «_______ вопросы для интервью». Нанимаете разработчика Java, Python или Javascript? Есть множество готовых вопросов, которые можно задать потенциальным новым сотрудникам.

Но — и это может быть довольно важно — тот, кто задает вопрос, вероятно, должен просмотреть ответ и полностью понять его. Возьмем, к примеру, вопрос, который я получил. «В чем разница между ArrayList и LinkedList — выберите свой язык. Какой из них лучше для вставки элементов?»

Совет: задавайте конкретные и хорошо сформулированные вопросы. «Сравнивая ArrayList и LinkedList, можете ли вы назвать ситуации, в которых вы бы предпочли один из них другому?» Или: «Если у вас есть список из 10 000 элементов, и вам нужно многократно читать определенные строки, что вы предпочтете? Если вам нужно часто вставлять строки, повлияет ли это на ваше решение?»

Уже раздраженный тем, что последний интервьюер (после 2 часов предыдущих членов команды) задавал технические проверочные вопросы в последние 5 минут, было особенно забавно, что он ошибся в своем собственном вопросе. Шутки в сторону?

Я проходил собеседование на позицию Python/Django. список Python — это гибкая часть языка. Но временная сложность для вставок составляет O(n). Он был специалистом по Java/Scala, поэтому думал о классах Java ArrayList и LinkedList.

Я заявил, что вставка строк в LinkedList выполняется быстрее. Его неосведомленный ответ: «Нет, на самом деле все наоборот — быстрее вставить в ArrayList».

Ошибка интервьюера.

Я понял, почему он так себя чувствовал, поскольку быстрее искать определенное место в ArrayList, чем в LinkedList. Однако он не сформулировал свой вопрос таким образом (на мой взгляд, у меня уже был итератор).

Сложность ArrayList равна O(n) — все последующие элементы после точки вставки перемещаются, чтобы освободить место. И если список достаточно полный, перед выполнением вставки будет выделено дополнительно 50% пространства. в 1,5 раза больше длины списка, и весь список копируется в новое место. Кроме того, может быстрее найти позицию в LinkedList, а затем вставить ее. При поиске точки вставки в ArrayList — O (1), вставка в LinkedList — O (1) — при условии, что у вас есть указатель/итератор в месте вставки.

Конечно, как старый чудак на C/C++, я реализовал свою долю связанных списков в свое время. Техника для больших списков заключалась в том, чтобы поддерживать данные с помощью связанного списка и поддерживать индекс (например, в хеш-таблице). Да, немного сложнее, но вы получаете O(1) доступ к узлу по индексу массива n и скорость O(1) вставок/удалений. Дети в наши дни…

Короче говоря, как кандидата (на конкурентном рынке) мой взгляд на интервьюера как на потенциального будущего сотрудника был снижен его ответом — или, по крайней мере, его отношением к нему.

Примечание о платформе

В зависимости от платформы и реализации ВМ ситуация не всегда так безнадежна, как может показаться. Например, при определенных условиях логика перемещения n элементов ArrayList ниже точки вставки может быть простой memmove, которая может быть очень быстрой — быстрее, чем Java-копия каждого элемента в виртуальной машине. Тем не менее потенциальное перераспределение памяти, перемещение элементов, смещение блока элементов под точку вставки и окончательная вставка выполняются намного медленнее, чем вставка в LinkedList. Особенно учитывая влияние на сборку мусора.

Но теперь мы уходим в глубокие сорняки. Лучше взять «муллиган» и просто двигаться дальше.