Сегодня был озадачен следующим вопросом (у нас его иногда задают на интервью), требующим потенциально ответа в 5-10 минут, желательно с примером кода.

Найти середину связного списка за один проход. Длина заранее не известна, а есть только указатель на голову.

Кто не догадается, смотрите комментарии. Уверен, там задачу быстро “возьмут”.

Задача очень жизненная, и реально полезно знать решение.

Как научиться решать задачи подобного рода? алгоритмические программистские задачи? В чем суть обучения?

Есть определенная категория программистов, которым я профессионально завидую. Это бойцы спортивного программирования типа TopCoder’а, Google Code Jam’а и прочих контестов. Для которых что-то вроде поиска цепочек в частично упорядоченном множестве как для меня сложить две переменные. Там, где мне надо открыть книгу или хотя бы Википедию, они это пишут сходу из головы.

Из личного опыта, перед некоторыми интервью, я мог на память сходу написать любую базовую сортировку, вставку в красно-черное дерево, послойный обход дерева и многое другое. Но проблема в том, что это ни разу не помогало на интервью! Все что я в итоге решал (или не решал), было связанно с задачами, которые могли быть в разы проще любой сортировки или дерева, но требовали “догадаться”. И основном спортивное программирование построено на теме “догадаться как”.

Но как научиться догадываться? Есть ли какая-то методика обучения? Именно методика, а не “решай все подряд, и все тебе будет”. Второй подход, конечно, работает, но методика могла бы ускорить процесс, сделать его более эффективным.

Например, взять физику или математику. Обычно ты учишь теорию и ее отражение на физический мир вокруг нас, учишь уже выведенные законы, теоремы (возможно их доказательства) и построенные на них базовые формулы. Далее при решении конкретной задачи ты, основываясь на выученных основах, пытаешься понять, что за физическая или математическая модель могла бы иметь место в задаче. Далее пытаешься приложить эту модель и смотришь, что получается (или не получается).

То есть тут есть методика, которая помогает тебе найти связь между теорией и задачей. Конечно, есть задачи, в которых “надо догадаться”, но это как опция, нежели норма. Тебе дается инструмент, когда зная малое, можно решать многое.

В нашем же программистском мире, как мне кажется, все из серии “надо догадаться”. Взять, например, эту задачу про поиск середины связного списка в один проход. Я могу изучить всё про такие списки: как их строить, как их сортировать, как их обходить (просто линейно) и т.д. Но все эти знания не подвинут меня ни шаг к решению этой простой задачи. Тут надо “просто догадаться”. Как научить догадываться? Неужели есть только один путь - решать и решать, пока количество не перейдет в качество, и ты будешь легко решать задачи на “догадаться” просто потому, что ты это уже так или иначе видел раньше.

Кстати, сравним среднего выпускника MIT и МАИ (я там учился). Наверное, выпускник MIT потенциально “сильнее” выпускника МАИ (при всей моей любви и уважении к Альма-матер). Почему? Там книги другие? Там профессора хуже? Я не могу пожаловаться, что мой курс программирования, где изучались алгоритмы был недостаточен.

Пока у меня только одно объяснение - скажем так, в объективно престижных ВУЗах просто больше прессуют и фактически заставляют учиться (иначе - это пустая трата денег и большой шанс вылететь).

Выходит, что количество так или иначе переходит в качество. И никакой магии.