Подготовку к собеседованиям по программированию можно упростить, сосредоточив внимание на шаблонах. Каждый программист должен изучить шаблоны программирования, такие как скользящее окно, два указателя, две кучи и т.д. Таким образом, инженеры-программисты смогут развить навык «отображения новой проблемы в существующую». В этом посте мы узнаем, какие шаблоны программирования целесообразнее всего изучать.
В Grokking the Coding Interview составили список 18 шаблонов из вопросов интервью, основанных на сходстве методов, необходимых для их решения. Идея курса состоит в том, чтобы обучить известным шаблонам программирования, чтобы после того, как кто-то ознакомится с ними, он смог решать с их помощью десятки других задач.
Распределение проблем в LeetCode
LeetCode — крупнейший репозиторий задач по программированию, в нем содержится более 2000 вопросов. Каждый вопрос в LC может быть помечен одной или несколькими темами. Этими темами являются либо структуры данных, такие как массив, хэш-таблица, дерево и т.д., либо алгоритмические методы, такие как жадность, разделяй и властвуй, сортировка и т.д., либо шаблоны программирования, такие как скользящее окно, поиск в глубину, топологическая сортировка и т.д. Вот Распределение тем по вопросам в LC:
На первом месте стоят Массивы с 1142 задачами, за ними следуют Строки с 549 задачами и так далее. Давайте подробнее рассмотрим каждую категорию, а именно структуры данных, алгоритмы и шаблоны программирования.
Структуры данных, которые стоит учить
Вот структуры данных, которые стоит учить в первую очередь:
- Массив (1142 задачи)
- Строка (549)
- Хэш-таблица (392)
- Дерево (191)
- Матрица (171)
- Стек (128)
- Куча или приоритетная очередь (107)
- Граф (102)
- Связанный список (69)
- Префиксное дерево (44)
Алгоритмические методы, которые стоит учить
Вот самые популярные алгоритмические методы с самой высокой отдачей от инвестиций вашего времени:
- Динамическое программирование (383)
- Сортировка (253)
- Жадность (248)
- Бинарный поиск (186)
- Поиск с возвратом (91)
- Рекурсия (44)
- Разделяй и властвуй (38)
Лучшие шаблоны программирования
Вот самые используемые шаблоны:
- Поиск в глубину (250)
- Поиск в ширину(198)
- Бинарный поиск (186)
- Два указателя (147)
- Скользящее окно (72)
- Монотонный стек (44)
- Пересекающийся поиск (63)
- Мемоизация (32)
- Топологическая сортировка (28)
- Дерево отрезков (27)
Шаблоны программирования, с которых стоит начать
Объединив все категории, приведенные выше, можно составить список лучших шаблонов/методов с самой высокой рентабельностью инвестиций в изучение.
1. Два указателя (массивы, строки, быстрый и медленный указатель)
Этот шаблон охватывает огромный набор вопросов, связанных с массивами и строками, которые являются структурами данных с самыми используемыми тегами. Быстрый и медленный указатель можно легко понять как вариант шаблона Два указателя.
2. Скользящее окно (массивы, строки, хеш-таблицы)
Скользящее окно охватывает большинство проблем, связанных с основными структурами данных, такими как массивы, строки и хеш-таблицы.
3. Поиск в глубину дерева и графа (обход матрицы)
Большинство проблем с деревьями и графиками можно решить с помощью поиска в глубину (DFS). Обход матрицы, который также является шаблоном на основе DFS, охватывает большинство проблем, связанных с матрицами.
4. Поиск в ширину по дереву и графу (очередь, подмножества, обход матрицы, топологическая сортировка)
Поиск в ширину (BFS) — очень удобный шаблон. Шаблоны BFS, такие как подмножества, обход матрицы, топологическая сортировка, охватывают большое количество проблем.
5. Бинарный поиск (массивы)
Двоичный поиск и его варианты используются для решения огромного количества вопросов в программировании.
6. Интервальное слияние
Хотя проблем, связанных с интервальным слиянием, не так много, они часто возникают на собеседованиях по программированию.
7. Рекурсия/поиск с возвратом
Поиск с возвратом и рекурсия используются для решения широкого круга задач. Освоение этих техник настоятельно рекомендуется.
Подготовка к coding-интервью
Большинство интервью по программированию включают вопросы, которые обсуждаются на LeetCode. Инженерам-программистам можно посоветовать практиковать решение таких задач перед собеседованиями. Наивысшая отдача от инвестиций времени и усилий достигается за счет грамотной подготовки и сосредоточения внимания на целевых паттернах.