Курс DSA с нуля: рекурсия, поиск, сортировки

Что в ролике
Если вы готовитесь к собеседованиям в продуктовые компании, этот курс даёт структурное введение в DSA на Python, начиная с того, зачем алгоритмы и структуры данных нужны, даже когда большую часть кода пишет AI. Автор объясняет структуры данных на бытовых примерах: разбросанные книги превращаются в книжный шкаф, а отмена и повтор действий в редакторе — в работу со стеком; графом представлены карты и связи между друзьями, деревом — файловая система. Рекурсия вводится через принцип математической индукции: базовый случай, допущение, доказательство; на примерах факториала (5! = 120), степени двойки, суммы цифр и Фибоначчи автор показывает, как код без базового случая падает по лимиту глубины рекурсии Python около 3000, и чем вызов рекурсии до собственной работы отличается от вызова после неё. Далее он переходит к спискам: сумма массива, проверка отсортированности, поиск первого, последнего и всех вхождений; здесь он отдельно показывает, почему лучше передавать индекс, а не делать срезы списка, чтобы не создавать лишние копии. Затем разбираются линейный и бинарный поиск: рекурсивный бинарный поиск проверяется на онлайн-платформе, а автор специально демонстрирует ошибки, связанные с порядком вызовов и индексами. Сортировка слиянием объясняется как разделяй-и-властвуй: массив делится до одного элемента и затем объединяется в отсортированном порядке, а быстрая сортировка — как выбор опорного элемента и разбиение относительно него. В финальной части решаются задачи на строки: подпоследовательности (для ABC — 8 вариантов, включая пустую), перестановки, комбинации букв телефонного номера и Ханойская башня (3 диска — 7 ходов, 4 диска — 15), с деревьями вызовов и заданиями.
Практика
- Что получишь
- Вы поймёте, как решать задачи на массивы, строки, поиск и сортировку рекурсивно, и сможете объяснить, почему рекурсивные функции требуют базового случая и как строить и читать деревья вызовов.
- Первый шаг
- Поставьте Jupyter или Python, возьмите пример факториала из видео и сначала допишите базовый случай, затем повторите сумму массива с передачей индекса вместо среза.
- Цифры
- —3000 — стандартный лимит глубины рекурсии Python, который автор показывает через sys.getrecursionlimit()
- —120 — результат 5!, который считается после добавления базового случая в рекурсивный факториал
- —7 — минимальное число ходов для Ханойской башни с 3 дисками
- —15 — минимальное число ходов для Ханойской башни с 4 дисками
- Честно
- Автор активно просит ставить лайки, комментировать, подписываться и делиться видео, однако сам курс по DSA в ролике бесплатный, платные продукты или закрытое сообщество не упоминаются. Нужные код и диаграммы деревьев вызовов видны только на экране: в пересказе полные листинги не приводятся, поэтому для повторения придётся смотреть видео или искать материалы по его ссылкам. Язык объяснения — хинглиш/хинди.
Если слова незнакомы — 6 терминов
- DSAструктуры данных и алгоритмы — база для технических собеседований
- рекурсияспособ решения задачи через вызов функцией самой себя на уменьшенной версии той же задачи
- базовый случайусловие, при котором рекурсия останавливается, чтобы не уходить в бесконечные вызовы
- стекструктура данных LIFO; также область памяти для незавершённых вызовов функций
- графмодель из узлов и связей, например карты или дружеские связи
- подпоследовательностьнабор символов или элементов в исходном порядке, не обязательно подряд
Компоненты
6 шт.Формат: пошаговый урок · для новичков · уверенность разметки 0.9 · источник