Паттерны алгоритмов: навык, который никто не тренирует

Попросите разработчика написать бинарный поиск. Большинство справится.

Покажите задачу, которая его требует, но без этих слов. Большинство не увидит.

Второе и проверяют на собеседовании.

Распознавание паттернов никто не тренирует. Каждый туториал объявляет ответ в заголовке.

Почему туториалы так устроены, разобрано в статье почему алгоритмы ненавидят.

Что такое распознавание

Опытный человек читает условие. Через секунд десять что-то срабатывает.

Срабатывает короткий список.

«Пахнет окном». «Это граф под маской». «Ответ монотонный, значит можно искать по нему».

Такое узнавание строится на выученном соответствии. От поверхностных признаков задачи к небольшому набору кандидатов.

У шахматистов то же самое для позиций на доске. Психологи называют это чанкингом.

Чанкинг берётся из насмотренности. Насмотренность можно устроить намеренно.

Обычно её получают по 30 секунд за раз, как прелюдию к часу написания кода. Тренируйте отдельно, и пропорция меняется.

Сигналов немного, и они выучиваются

Большинство задач с собеседований идёт примерно из 50 паттернов. У каждого есть пара примет.

Два указателя с концов. Вход отсортирован. Ответ это пара.

Скользящее окно. Подряд идущие, подстрока, подмассив. Плюс самый длинный, самый короткий или счёт под лимитом.

Бинарный поиск по ответу. Минимальное или максимальное значение, при котором ещё работает. Проверить одно значение легко.

Куча. k лучших из чего-то. Или наименьший элемент, снова и снова.

Монотонный стек. Для каждого элемента: следующий больший или меньший.

Система непересекающихся множеств. Объекты сливаются в группы. Вас всё время спрашивают, в одной ли группе двое.

Шесть паттернов. По одной строке. Это помещается в голову сегодня.

Работа в том, чтобы они срабатывали сами.

Учите соседей, а не только сигналы

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

Два указателя против скользящего окна. Оба ведут два индекса. Указатели сходятся с концов и требуют сортировки. Окно двигает оба индекса в одну сторону.

Жадность против динамического программирования. Оба строят ответ по шагам.

Жадность безопасна, только если локальный выбор невозможно потом пожалеть.

BFS против DFS. Оба обходят все вершины. У кратчайшего пути в невзвешенном графе верный ответ один.

Сортировка против кучи. Оба дают порядок.

Для топ-3 из миллиона сортировка всего миллиона не подходит.

Распознавание ломается здесь. На двух, которые похожи.

Как это тренировать

Спрячьте категорию. Перемешайте список, закройте теги или возьмите источник, сделанный для этого.

Отвечайте до решения. Паттерн и слова, которые вам его выдали. 3 минуты.

Дальше остановитесь. Угадали? Идите дальше. Решение съедает время, которое нужно на повторы.

Записывайте каждый промах парой. Что было. Что вы сказали.

Подмешивайте старое. Распознавание на теме этой недели только напоминает, какая сейчас неделя.

Двадцать задач в час это норма. Двести это несколько недель лёгкой практики.

Примерно там и происходит сдвиг.

Где это стоит в рабочей неделе, разобрано в статье как готовиться правильно.

Как это ощущается, когда заработало

Вы читаете задачу, и первая мысль это категория.

Всю работу по решению всё равно делать вам. Но вы знаете, какого рода эта работа.

Паника от пустого условия перестаёт приходить.

На собеседовании меняется ещё одно. Правдоподобный подход в первую минуту покупает вам разговор. Четыре минуты молчания покупают подсказку, а подсказки стоят дорого.

Где это применено

Тренажёр распознавания это причина, по которой AlgoPath существует.

52 паттерна с их сигналами и соседями. 194 неподписанные задачи. Забег на время. Матрица, показывающая, какие пары путаете лично вы.

Первые 33 шага бесплатны, и тренажёр работает внутри них.