Примечание переводчика: оригинальная статья опубликована в серии твитов
Вероятно, вы уже читали кучу объяснений, почему обработка связных списков — плохой вопрос для собеседования. Я же в первую очередь хочу объяснить, откуда он вообще взялся. Всем пристегнуться, погружаемся в теорию игр ИСТОРИЮ!
Хотя индустрия программного обеспечения процветала в 80-е годы, но действительно взлетела в 90-е. В это десятилетие число работников отрасли в США утроилось и превысило миллион человек. Со взрывным ростом пришла необходимость нанимать массу сотрудников и оценивать их.
Что нужно оценить? Ну, в первую очередь, знание языков. Согласно TIOBE, в 1986−2006 годы самым популярным языком в мире был C, далее следовал C++. К 2006 году Java вышла на первое место, но C остался рядом.
C работал близко к железу без лишних абстракций. Пустой словарь Python расходует аж 288 байт, то есть 5% всего объёма памяти первого поколения Apple II. Абстракции слишком дороги, слишком много накладных расходов. Если вам нужна сложная структура данных, вы должны построить её самостоятельно с помощью массивов, структур и указателей.
(C++ оказался получше в этом отношении, поскольку там появилась стандартная библиотека шаблонов, но её официально приняли только в 1998 году, а повсеместно использовать начали гораздо позже. Помню, как читал аргументы о накладных расходах даже в 2005 году).
Связные списки — необходимая структура данных, которая позволяет производить динамическое выделение памяти с меньшими рисками переполнения буфера. И нужно было писать эти связные списки вручную. Это означает, что вы должны были вручную манипулировать указателями в связных списках.
Другими словами, в 90-е годы вопрос «Как развернуть связный список» — это не проверка алгоритмического или знания структур данных, это вопрос «Вы программировали на C?». Если да, то для вас ответ тривиален. Если нет, ответить (в идеале) невозможно.
В настоящее время большинство из нас не программирует на C. Но устаревший вопрос не исчез, а модифицировался. Я подозреваю, причина в том, что огромное количество программистов продолжали задавать и задавать его, не понимая исторического контекста и причин, почему этот вопрос появился.
Вероятно, ситуацию помог зацементировать бестселлер «Взлом собеседования по программированию». Её автор Гейл Лакман Макдауэлл работала по специальности в 2000−2008 годы и, вероятно, написала книгу на основе собственного опыта. Книга стала настольным справочником компаний, которые проводят собеседования — и связные списки укрепились в списке стандартных вопросов.
Без исторического контекста связные списки стали преподносить как вопрос на «навыки решения проблем». Но это полностью противоречит изначальной цели: если вы проверяете знание языка, вы не хотите, чтобы на вопрос могли ответить (то есть «решить проблему») люди, не знакомые с этим языком.
Например, вопрос «Определите, есть ли в связном списке цикл». Предполагается, что кандидат должен придумать решение типа «черепаха и заяц», опубликованное в обильно цитируемой научной статье 1967 года. Вы просите кандидата повторить научное исследование за 30 минут!
Возможно, когда мы перешли к вопросам типа «решение проблем», то откалибровали сложность, взяв связные списки в качестве ориентира. Что совершенно искажает шкалу.
(Кстати: ещё один аргумент для связных списков — это «проверка фундаментальных знаний информатики». Ну если так, то почему у всех не спрашивают про детерминированные конечные автоматы? Теорему Райса? Как работает компилятор? Структуры данных — очень небольшая часть компьютерной науки и часто нерепрезентативная).
Подводя итог, вопрос о связном списке был хорошей проверкой умения писать на С, а теперь стал плохой проверкой «Умеете ли вы решать проблемы?»
Мораль: подумайте ещё раз о том, чтобы задавать вопросы по связным спискам в собеседовании.
Ещё одна мораль: из истории можно многому научиться.
(Третья мораль: если видите наполовину завершённую статью и думаете «Эх, легче запустить проект в серии твитов», это ловушка, не попадайтесь в неё)
Автор: m1rko
