Лучшие шаблоны LeetCode для подготовки к кодинг интервью

Подготовку к собеседованиям по программированию можно упростить, сосредоточив внимание на шаблонах. Каждый программист должен изучить шаблоны программирования, такие как скользящее окно, два указателя, две кучи и т.д. Таким образом, инженеры-программисты смогут развить навык «отображения новой проблемы в существующую». В этом посте мы узнаем, какие шаблоны программирования целесообразнее всего изучать.

В Grokking the Coding Interview составили список 18 шаблонов из вопросов интервью, основанных на сходстве методов, необходимых для их решения. Идея курса состоит в том, чтобы обучить известным шаблонам программирования, чтобы после того, как кто-то ознакомится с ними, он смог решать с их помощью десятки других задач.

Распределение проблем в LeetCode

LeetCode — крупнейший репозиторий задач по программированию, в нем содержится более 2000 вопросов. Каждый вопрос в LC может быть помечен одной или несколькими темами. Этими темами являются либо структуры данных, такие как массив, хэш-таблица, дерево и т.д., либо алгоритмические методы, такие как жадность, разделяй и властвуй, сортировка и т.д., либо шаблоны программирования, такие как скользящее окно, поиск в глубину, топологическая сортировка и т.д. Вот Распределение тем по вопросам в LC:

На первом месте стоят Массивы с 1142 задачами, за ними следуют Строки с 549 задачами и так далее. Давайте подробнее рассмотрим каждую категорию, а именно структуры данных, алгоритмы и шаблоны программирования.

Структуры данных, которые стоит учить

Вот структуры данных, которые стоит учить в первую очередь:

1. Массив (1142 задачи)
2. Строка (549)
3. Хэш-таблица (392)
4. Дерево (191)
5. Матрица (171)
6. Стек (128)
7. Куча или приоритетная очередь (107)
8. Граф (102)
9. Связанный список (69)
10. Префиксное дерево (44)

Алгоритмические методы, которые стоит учить

Вот самые популярные алгоритмические методы с самой высокой отдачей от инвестиций вашего времени:

1. Динамическое программирование (383)
2. Сортировка (253)
3. Жадность (248)
4. Бинарный поиск (186)
5. Поиск с возвратом (91)
6. Рекурсия (44)
7. Разделяй и властвуй (38)

Лучшие шаблоны программирования

Вот самые используемые шаблоны:

1. Поиск в глубину (250)
2. Поиск в ширину(198)
3. Бинарный поиск (186)
4. Два указателя (147)
5. Скользящее окно (72)
6. Монотонный стек (44)
7. Пересекающийся поиск (63)
8. Мемоизация (32)
9. Топологическая сортировка (28)
10. Дерево отрезков (27)

Шаблоны программирования, с которых стоит начать

Объединив все категории, приведенные выше, можно составить список лучших шаблонов/методов с самой высокой рентабельностью инвестиций в изучение.

1. Два указателя (массивы, строки, быстрый и медленный указатель)

Этот шаблон охватывает огромный набор вопросов, связанных с массивами и строками, которые являются структурами данных с самыми используемыми тегами. Быстрый и медленный указатель можно легко понять как вариант шаблона Два указателя.

2. Скользящее окно (массивы, строки, хеш-таблицы)

Скользящее окно охватывает большинство проблем, связанных с основными структурами данных, такими как массивы, строки и хеш-таблицы.

3. Поиск в глубину дерева и графа (обход матрицы)

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

4. Поиск в ширину по дереву и графу (очередь, подмножества, обход матрицы, топологическая сортировка)

Поиск в ширину (BFS) — очень удобный шаблон. Шаблоны BFS, такие как подмножества, обход матрицы, топологическая сортировка, охватывают большое количество проблем.

5. Бинарный поиск (массивы)

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

6. Интервальное слияние

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

7. Рекурсия/поиск с возвратом

Поиск с возвратом и рекурсия используются для решения широкого круга задач. Освоение этих техник настоятельно рекомендуется.

Подготовка к coding-интервью

Большинство интервью по программированию включают вопросы, которые обсуждаются на LeetCode. Инженерам-программистам можно посоветовать практиковать решение таких задач перед собеседованиями. Наивысшая отдача от инвестиций времени и усилий достигается за счет грамотной подготовки и сосредоточения внимания на целевых паттернах.

Источник