Я убеждён, что алгоритмические вопросы на собеседованиях – дерьмо, за что некоторые “программисты” испытывают ко мне поистине классовую ненависть. Прежде чем объяснить причину, я расскажу, что придерживаюсь весьма ортодоксальной точки зрения на вычисления вообще (и компьютерные вычисления в частности).
Она очень проста: вычисления, которые производятся более одного раза, бессмысленны. За исключением случаев, когда ваша цель – улучшить качество результата. Но в обычном, повседневном программировании, когда вы обдумываете уже кем-то обдуманное, изобретаете кем-то изобретённое, вычисляете кем-то вычисленное – вы просто бесполезно греете атмосферу.
Хороший пример – ряд Фибоначчи (последовательность, в которой каждый следующий член является суммой двух предыдущих). Популярнейший вопрос на собеседованиях программистов программистами. Любой из вас, когда понадобится 138-ой член ряда фибоначчи, напишет в продукте банальную функцию с рекурсией, которая спустится до первого члена и соберёт их сумму. Любой, кроме меня. Потому что я тупо положу в продукт текстовый файлик, где ряд фибоначчи от 1-го до миллионного члена записан построчно, и при запросе 138-ого члена тупо прочитаю 138-ую строку. Всё.
И нет никакой разницы, насколько оптимальным алгоритмом я его посчитал, сколько машинных ресурсов съел и как долго это происходило. Да хоть неделю. По сравнению со сроком разработки проекта – это ничто.
Более того, адепты знания алгоритмов никогда не поймут и не признают, что алгоритм, переписанный из книжки, будет работать заведомо не хуже, чем ты воспроизвёл по памяти. Более того, любой разумный человек знает, что память несовершенна, и в критически надёжном софте (в медицине, в авиатехнике) лучше перестраховаться и взять заведомо надёжный источник знаний. Видимо, “свидетели алгоритмов” не относятся к подвиду человека разумного, потому что продолжают снова и снова просить вспомнить (!) и рассказать как устроена сортировка массива. Я не буду даже и говорить о том, что крут не тот, кто написал алгоритм, а тот кто произвёл продукт – попробуйте без гугла назвать авторов алгоритма из недавнего приложения prisma (и нет, это не выходцы из Mail.Ru Group).
Есть такая штука – функциональное программирование. Оно непопулярно, потому что там внезапно оказывается что нужно думать, прежде чем писать код. Однако оно (точнее, ФП-компилятор) делает совершенно магическую штуковину: когда признаёшь за истину, что любая функция при одних и тех же входных данных – всегда возвращает один и тот же результат, компилятор тупо его запоминает с первого же раза.
Представляете? Однажды вычислив, что если на вход подано 2 и 2, и на выходе получилось 4, компилятор никогда больше не вычислит эту функцию вновь. Он просто возвращает запомненный результат при следующих вызовах той же функции с теми же данными. Это “магия”, которая гарантированно сносит башку неподготовленному новичку, потому что начинаешь по-другому смотреть на программирование, на код, на данные, на вычисления и на свою жизнь вообще.
Особенно если ты работаешь в вебе. Концепция PHP, например, согласно которой приложение рождается заново в ответ на каждый (!) запрос пользователя – начинает выглядеть безумием. Методы, вычисляющие валидность модели данных при каждом обращении к ней, начинают выглядеть подозрительными. Коллеги, до посинения оттачивающие тонкости realtime-алгоритмов вместо того чтобы пользоваться предрасчитанными данными – начинают выглядеть безумцами.
Рекурсивные функции удивительно ведут себя в мире ФП. Первое вычисление 138-го члена ряда Фибоначчи займёт некоторое время, зато вычисление 139-го члена произойдёт практически мгновенно, потому что компилятор записал предыдущие. Это заложено в глубокие основы, о которых не нужно думать программисту.
Удерживать в памяти все на свете алгоритмы – бесполезно на практике. Точно так же, как наши папы и мамы брали значение синуса угла из таблиц Брадиса, когда тебе понадобится сортировка массива – открой учебник и прочитай. И никогда больше не требуй воспроизвести их по памяти на собеседовании. Не повышай энтропию своей бесполезной умственной деятельностью – займись лучше тем, что ещё не открыто, не исследовано, не разведано до тебя.
P.S. я ещё обещал рассказать про будущее интернета. Одим из предназначений интернета при его рождении был обмен информацией между учёными. В будущем я вижу этот “обмен” гораздо более широким: я верю, что всё, что сегодня день за днём заново вычисляется в миллионах запущенных инстансов программ по всему миру – будет однажды вычислено и положено в гигантский, общедоступный кэш. И что каналы связи будут настолько легковесными, что процессору будет проще спросить у кэша “сколько букв А в строке Мама мыла раму”, чем вычислять это самостоятельно.
И тогда мы получим удивительный мир, в котором разум каждого талантливого учёного (программиста!) будет освобождён от рутины и полностью сфокусирован только на новых открытиях.
P.S. А если вам это кажется безумием, откройте для себя сайт oeis.org