Грокаем алгоритмы: Гайд по алгоритмам для тех, кому сложно решать задачи
Эта статья — для разработчиков, которые частично уже знают алгоритмы. Если вы еще не знакомы с ними, советуем пройти трек «Алгоритмы и структуры данных» в Хекслете. Вы изучите списки, стеки, очереди, структуры данных, которые помогут проектировать структуры и алгоритмы.
Бесплатные курсы по программированию в Хекслете
- Освойте азы современных языков программирования
- Изучите работу с Git и командной строкой
- Выберите себе профессию или улучшите навыки
Грокать алгоритмы или не грокать? Что делать, если вам не хочется решать сто задач к вашему следующему собеседованию?
Часть меня ненавидит технические собеседования, в первую очередь из-за того, что мне нужно повторять много материала. Кроме того, в процессе самого собеседования мне часто приходится предлагать какое-то особенное решение, а не то, которое я бы выбрал в своей будничной практике.
Несмотря на это, я люблю алгоритмы и люблю решать задачки по программированию. Для меня это веселое времяпровождение и хорошая тренировка для мозга. Учитывая все это, хочу рассказать вам о моей собственной технике подготовки к собеседованиям, которая намного интереснее и волнительнее, чем обычная подготовка.
Коротко расскажу о себе, чтобы вы убедились в моей экспертности. Я программирую уже 20 лет, за это время я много раз менял место работы. Всего я прошел около 30 воронок найма — больше 120 собеседований. Плюс к этому у меня есть опыт с той стороны баррикад: я провел около 300 технических собеседований и больше 200 собеседований по системному дизайну .
Где мы грокаем алгоритмы
Если вы когда-нибудь искали работу, то знаете, что есть ресурсы, которые собирают задачи с собеседований . Один из них — LeetCode, это самый популярный сайт, где очень много задач. Плюс вокруг него сложилось развитое сообщество, где можно обсуждать задачки с другими инженерами. Если выдается свободная минутка, я всегда не прочь провести ее на LeetCode. Там я решаю задачи или читаю чужие решения, после чего сравниваю со своими.
Самая большая проблема LeetCode в том, что сайту не хватает продуманной системы обучения. У него много разных задач, в которых легко потеряться. Сколько нужно таких задач, чтобы подготовиться к собеседованию? Я бы предпочел двигаться по продуманной программе, в конце которой я смогу ощутить уверенность в собственных знаниях. Но системы нет, а я ленивый, и вообще — не хочу решать 500+ задач.
Одно из популярных решений для этой проблемы — решать задачи, которые относятся к одной структуре данных (например, прорешать несколько задач с деревьями). Какая-то система обучения появляется, но это решение меня все равно не устраивает. Например, что делать, если задачу можно решить при помощи разных структур данных?
Какую систему обучения придумал я
Я бы предпочел такую систему, в которой задачи распределены по паттернам, а не по структурам данных. Мои любимые паттерны — скользящее окно, нахождение цикла и топологическая сортировка. Когда я научился пользоваться этими методами, я стал решать незнакомые задачи по аналогии с задачами, которые решал до этого. Благодаря этому весь процесс подготовки к собеседованиям стал более интересным и веселым. Ну и конечно же, более систематичным.
Я обнаружил 25 паттернов, которые лежат в основе решения большинства задач. Думаю, эти паттерны помогут кому угодно показывать на собеседованиях красивые и элегантные решения. Вся фишка этих паттернов в том, что понимая один из них, вы научитесь решать сразу несколько задач, десятки задач.
Самые распространенные паттерны для решения задач
- Метод скользящего окна
- Метод двух указателей
- Нахождение цикла
- Интервальное слияние
- Цикличная сортировка
- In-place Reversal для LinkedList
- Поиск в ширину
- Поиск в глубину
- Двоичная куча
- Подмножества
- Усовершенствованный бинарный поиск
- Побитовое исключающее ИЛИ
- Top K Elements
- K-образное слияние
- Задача о рюкзаке 0-1
- Задача о неограниченном рюкзаке
- Числа Фибоначчи
- Наибольшая последовательность-палиндром
- Наибольшая общая подстрока
- Топологическая сортировка
- Чтение префиксного дерева
- Задача: количество островов в матрице
- Метод проб и ошибок
- Система непересекающихся множеств
- Задача: найти уникальные маршруты
Читайте также: Это снова я, резиновая уточка: что такое метод Фейнмана и почему с его помощью так просто изучать программирование
Метод скользящего окна
Контекст: Мы используем этот метод, когда у нас есть входные данные с заданным размером окна.
Задачи для этого паттерна:
- Longest Substring with K Distinct Characters
- Fruits into Baskets
- Permutation in a String
Метод двух указателей
Контекст: Мы используем два указателя, чтобы перебрать все входные данные. Обычно два указателя движутся в противоположных направлениях с фиксированным интервалом.
Задачи для этого паттерна:
- Squaring a Sorted Array
- Dutch National Flag Problem
- Minimum Window Sort
Нахождение цикла
Контекст: Еще этот алгоритм называют алгоритмом черепахи и зайца. В отличие от предыдущего метода, два указателя тут движутся с разной скоростью.
Задачи для этого паттерна:
- Middle of the LinkedList
- Happy Number
- Cycle in a Circular Array
Интервальное слияние
Контекст: Этот метод применяют, если есть пересекающиеся интервалы. Например, на этом изображении мы видим, что интервалы a и b могут пересекаться шестью разными способами:
Задачи для этого паттерна:
- Intervals Intersection
- Conflicting Appointments
- Minimum Meeting Rooms
Цикличная сортировка
Контекст: Если входные данные лежат в заданном интервале, используйте цикличную сортировку.
Задачи для этого паттерна:
- Find all Missing Numbers
- Find all Duplicate Numbers
- Find the First K Missing Positive Numbers
In-place Reversal для LinkedList
Техника: Эта техника описывает эффективный способ перевернуть связи между узлами в LinkedList (класс Java). Часто мы ограничены in-place, то есть мы должны использовать исходные узлы.
Задачи для этого паттерна:
- Reverse every K-element Sub-list
- Rotate a LinkedList
Поиск в ширину
Контекст: Это метод для решения задач с деревьями.
Задачи для этого паттерна:
- Binary Tree Level Order Traversal
- Minimum Depth of a Binary Tree
- Connect Level Order Siblings
Поиск в глубину
Контекст: Тот же, что для предыдущего метода.
Задачи для этого паттерна:
- Path With Given Sequence
- Count Paths for a Sum
Двоичная куча
Контекст: Во многих задачах у нас есть набор элементов, который можно разделить на две части. Тогда мы могли бы выяснить, какой элемент является наименьшим в первой куче и какой является наибольшим во второй куче.
Задачи для этого паттерна:
- Find the Median of a Number Stream
- Next Interval
Подмножества
Контекст: Если задача требует перестановки или комбинаций элементов, используйте подмножества.
Задачи для этого паттерна:
- String Permutations by changing case
- Unique Generalized Abbreviations
Усовершенствованный бинарный поиск
Контекст: Эта техника использует логический оператор для наиболее эффективного поиска элементов.
Задачи для этого паттерна:
- Two Single Numbers
- Flip and Invert an Image
Наибольшее K элементов
Контекст: Эта техника используется, чтобы найти наибольший/наименьший или наиболее часто встречающийся набор k-элементов в коллекции.
Задачи для этого паттерна:
- ‘K’ Closest Points to the Origin
- Maximum Distinct Elements
Читайте также: Как решить задачу, если непонятно, с чего вообще начать: советы от Хекслета
K-образное слияние
Контекст: Используйте эту технику, если у вас есть список отсортированных массивов.
Задачи для этого паттерна:
- Kth Smallest Number in M Sorted Lists
- Kth Smallest Number in a Sorted Matrix
Рюкзак 0-1
Контекст: Этот паттерн используют для задач на оптимизацию. Используйте эту технику, чтобы выбирать элементы, которые дают максимум выгоды в данном наборе ограничений по вместимости. Учитывая то, что каждый элемент может быть выбран лишь единожды.
Задачи для этого паттерна:
- Equal Subset Sum Partition
- Minimum Subset Sum Difference
Неограниченный рюкзак
Контекст: То же самое, что в предыдущем паттерне, но только каждый элемент может быть выбран повторно сколько угодно раз.
Задачи для этого паттерна:
- Rod Cutting
- Coin Change
Числа Фибоначчи
Контекст: Как очевидно из названия, это паттерн для чисел Фибоначчи. Это последовательность, в которой каждое последующее число равно сумме двух предыдущих чисел.
Задачи для этого паттерна:
Наибольшая последовательность — палиндром
Контекст: Имеется в виду задача, которая может быть использована как для последовательности, так и для строк . По сути это задача на оптимизацию.
Задачи для этого паттерна:
- Longest Palindromic Subsequence
- Minimum Deletions in a String to make it a Palindrome
Наибольшая общая подстрока
Контекст: Как понятно из названия, это паттерн для работы со строками или другими последовательностями, а также для работы с наборами строк или последовательностей.
Задачи для этого паттерна:
- Maximum Sum Increasing Subsequence
- Edit Distance
Чтение префиксного дерева
Контекст: Это специфичная для структуры данных техника, с помощью которой читают или создают префиксное дерево.
Задачи для этого паттерна:
- Longest Word in Dictionary
- Palindrome Pairs
Острова в матрице
Контекст: Этот паттерн подходит для чтения любого двумерного массива, где нам нужно обнаружить связанные между собой элементы.
Задачи для этого паттерна:
- Number of Distinct Islands
- Maximum Area of Island
Путь проб и ошибок
Контекст: Этот паттерн подойдет для того, чтобы пройтись по массиву в поисках подходящего под требования элемента.
Задачи для этого паттерна:
- Find Kth Smallest Pair Distance
- Minimize Max Distance to Gas Station
Система непересекающихся множеств
Контекст: Если данные раскиданы по непересекающимся множествам, то они решаются одним и тем же способом.
Задачи для этого паттерна:
- Number of Provinces
- Bipartite Graph
Поиск уникального маршрута
Контекст: Этот паттерн подойдет для прохождения по любому многомерному массиву.
Задачи для этого паттерна:
- Find Unique Paths
- Dungeon Game
Бесплатные курсы по программированию в Хекслете
- Освойте азы современных языков программирования
- Изучите работу с Git и командной строкой
- Выберите себе профессию или улучшите навыки
10 шагов по решению задач в программировании
Это сборник советов для разработчиков-новичков, которые смотрят на пустой экран и не знают, с чего начать. Нередко можно услышать от молодых разработчиков, работающих над решением каких-то задач в программировании, что они не уверены, за что нужно хвататься. Ты понимаешь саму задачу, логику, основы синтаксиса и так далее. Если ты видишь чей-то код, или тебе кто-то помогает, то можно всё сделать самому. Но бывает, что ты не уверен в своих силах, или поначалу тебе трудно реализовать свои мысли в коде, несмотря на то, что ты знаешь синтаксис и логику. Под катом — несколько советов по решению этой проблемы, которые помогут вам в повседневной работе.
1. Прочитайте условия задачи как минимум трижды (или хотя бы столько раз, сколько вам будет удобно)
Вы не сможете решить задачу, если не поймёте её. Есть разница между задачей и задачей, которую, как вам кажется, вы решаете. Можно прочитать первые несколько строк, а насчёт остального выстроить предположения, поскольку всё выглядит похожим на то, с чем вы сталкивались раньше. Даже если вы делаете популярную игру наподобие Виселицы, удостоверьтесь, что прочитали все её правила, пусть даже вы играли в неё раньше.
Иногда можно попробовать объяснить задачу другу и посмотреть, поймёт ли он ваше объяснение. Вы же не хотите пройти половину пути и обнаружить, что неправильно поняли требования. Так что лучше потратить в начале больше времени, чтобы всё прояснить. Чем лучше поймёте задачу, тем легче будет её решить.
Допустим, мы создаём простую функцию selectEvenNumbers , которая берёт массив чисел и возвращает массив evenNumbers с одними лишь чётными числами. Если чётных чисел в исходном массиве нет, то массив evenNumbers возвращается пустым.
function selectEvenNumbers() < // здесь ваш код >Какие вопросы можно себе задать:
- Как компьютер может сказать, что число является чётным? Разделить на 2 и проверить, чтобы результат получился целым.
- Что я передаю этой функции? Массив.
- Что содержит этот массив? Одно или несколько чисел.
- Какие типы данных у элементов массива? Числа.
- Какова цель этой функции? Что я возвращаю в конце её выполнения? Цель — получить все чётные числа и вернуть их в массиве. Если нет чётных чисел, то массив возвращается пустым.
2. Пройдите по задаче вручную как минимум с тремя наборами данных
Возьмите лист бумаги и пройдите по задаче вручную. Выберите не менее трёх наборов данных для проверки. Выберите предельно допустимые и крайние случаи.
Предельно допустимые случаи: проблема или ситуация, возникающая за пределами нормальных параметров функционирования. Например, когда одновременно несколько переменных или состояний среды имеют экстремальные значения, даже если каждый из параметров находится в своём специфическом диапазоне.
Крайние случаи: проблемы или ситуации, возникающие только при экстремальных (минимальных или максимальных) значениях параметров функционирования.
Вот, к примеру, несколько наборов данных для использования:
[1]
[1, 2]
[1, 2, 3, 4, 5, 6]
[-200.25]
[-800.1, 2000, 3.1, -1000.25, 42, 600]
Когда только начинаешь, то зачастую пренебрегаешь какими-то шагами. Поскольку наш мозг уже знаком с чётными числами, то можно просто посмотреть на набор чисел и сразу передать в массив 2, 4, 6 и так далее, не думая о том, как наш мозг выбирает конкретные числа. Если вы замечаете это за собой, то лучше взять большой набор данных, чтобы помешать мозгу решать задачу, просто глядя на числа. Это поможет придерживаться настоящего алгоритма.
Давайте пройдём по массиву [1]
- Смотрим на единственный элемент массива [1] .
- Определяем, является ли он чётным. Не является.
- Замечаем, что других элементов в массиве нет.
- Определяем, что здесь нет чётных чисел.
- Возвращаем пустой массив.
- Смотрим на первый элемент массива [1, 2]
- Это 1 .
- Определяем, является ли он чётным. Не является.
- Смотрим на следующий элемент.
- Это 2 .
- Определяем, является ли он чётным. Является.
- Создаём массив evenNumbers и добавляем в него 2 .
- Замечаем, что других элементов в массиве нет.
- Возвращаем массив evenNumbers — [2] .
3. Упрощайте и оптимизируйте свой алгоритм
Поищите подходящие паттерны, может быть, что-то удастся обобщить. Подумайте, можно ли уменьшить количество шагов.
- Создадим функцию selectEvenNumbers .
- Создадим новый пустой массив evenNumbers для хранения чётных чисел.
- Проходим по каждому элементу массива [1, 2] .
- Находим первый элемент.
- Делим его на 2 и определяем, чётный ли он. Если да, то прибавляем к evenNumbers .
- Находим следующий элемент.
- Повторяем шаг №4.
- Повторяем шаги №5 и №4, пока не кончатся элементы в массиве.
- Возвращаем массив evenNumbers вне зависимости от того, есть ли в нём что-то.
- Доказываем истинность для n = 1 , n = 2 , .
- Предполагаем, что будет истинно для n = k .
- Доказываем истинность для n = k + 1 .
4. Пишите псевдокод
После проработки основных шагов напишите псевдокод, который можно перевести в настоящий код. Это поможет определить структуру кода, да и вообще облегчит его написание. Пишите псевдокод построчно. Это можно делать на бумаге или в виде комментариев в редакторе. Если вы только начинаете и считаете, что пустой экран выглядит жутковато или отвлекает, то лучше писать на бумаге.
В целом не существует правил для написания псевдокода, но можно включать синтаксис из вашего языка, если так будет удобнее. Но сосредотачивайтесь не на синтаксисе, а на логике и этапах алгоритма.
Применительно к нашему случаю есть много разных вариантов. Например, можно использовать filter , но ради простоты примера воспользуемся простым циклом for (однако при последующем рефакторинге мы ещё столкнёмся с filter ).
Вот пример псевдокода, в основном состоящего из слов:
function selectEvenNumbers создаём массив evenNumbers и делаем его эквивалентным пустому массиву для каждого элемента в этом массиве смотрим, является ли элемент чётным если чётный (при делении на 2 результат получается нецелым) добавляем его к массиву evenNumbers return evenNumbersА вот псевдокод, в котором слов гораздо меньше:
function selectEvenNumbers evenNumbers = [] for i = 0 to i = length of evenNumbers if (element % 2 === 0) добавляем его к массиву evenNumbers return evenNumbersГлавное, писать код построчно и понимать логику каждой строки.
Вернитесь к задаче, чтобы удостовериться, что вы на правильном пути.
5. Преобразуйте псевдокод в нормальный код и отладьте его
Когда ваш псевдокод будет готов, преобразуйте каждую строку в реальный код на вашем языке. Здесь мы воспользуемся JavaScript.
Если вы писали на бумаге, то перенесите всё в редактор в виде комментариев, а затем замените каждую строку.
Теперь вызовите функцию и дайте ей некоторые из ранее использованных наборов данных. Так можно проверить, возвращает ли код нужный результат. Также можете написать тесты для проверки соответствия выходных данных ожидаемому результату.
selectEvenNumbers([1]) selectEvenNumbers([1, 2]) selectEvenNumbers([1, 2, 3, 4, 5, 6]) selectEvenNumbers([-200.25]) selectEvenNumbers([-800.1, 2000, 3.1, -1000.25, 42, 600])После каждой переменной или строки можно использовать console.log() . Это поможет проверить, ведут ли себя значения и код так, как ожидается, прежде чем двигаться дальше. Таким образом вы выловите любые проблемы, не зайдя слишком далеко. Вот пример того, какие значения можно проверить при начале работы.
function selectEvenNumbers(arrayofNumbers) < let evenNumbers = [] console.log(evenNumbers) // Удаляем после проверки выходных данных console.log(arrayofNumbers) // Удаляем после проверки выходных данных >Ниже приведён код, полученный после обработки каждой строки псевдокода. Символы // обозначают строки из псевдокода. Жирным выделен реальный код на JavaScript.
// function selectEvenNumbers function selectEvenNumbers(arrayofNumbers) // evenNumbers = [] let evenNumbers = [] // for i = 0 to i = length of evenNumbers for (var i = 0; i < arrayofNumbers.length; i++) // if (element % 2 === 0) if (arrayofNumbers[i] % 2 === 0) // добавляем его к массиву evenNumbers evenNumbers.push(arrayofNumbers[i]) > > // return evenNumbers return evenNumbers >Уберём псевдокод, чтобы не путаться.
function selectEvenNumbers(arrayofNumbers) < let evenNumbers = [] for (var i = 0; i < arrayofNumbers.length; i++) < if (arrayofNumbers[i] % 2 === 0) < evenNumbers.push(arrayofNumbers[i]) >> return evenNumbers >Иногда разработчики-новички настолько увлекаются синтаксисом, что им трудно идти дальше. Помните, что со временем вам будет проще соблюдать синтаксис, и нет ничего стыдного в том, чтобы потом при написании кода обращаться к справочным материалам для корректного соблюдения синтаксиса.
6. Упрощайте и оптимизируйте код
Возможно, вы заметили, что упрощение и оптимизация — это повторяющиеся темы.
«Простота — предпосылка надёжности».
Эдсгер Дейкстра, нидерландский учёный и один из первопроходцев в ряде областей информатики
В нашем примере одним из путей оптимизации будет фильтрация элементов в массиве посредством возвращения нового массива с помощью filter . В этом случае нам не нужно определять переменную evenNumbers , потому что filter вернёт новый массив с копиями элементов, которые соответствуют фильтру. При этом исходный массив не изменится. Также нам не нужно использовать цикл for . filter пройдёт по каждому элементу, и если вернёт true, то элемент попадёт в массив, а если false , то будет пропущен.
function selectEvenNumbers(arrayofNumbers) < let evenNumbers = arrayofNumbers.filter(n =>n % 2 === 0) return evenNumbers >Может потребоваться несколько итераций упрощения и оптимизации кода, по мере того как вы будете находить новые способы.
Задавайте себе такие вопросы:
- Каковы цели упрощения и оптимизации? Цели зависят от принятого в вашей команде стиля или ваших личных предпочтений. Вы пытаетесь максимально уплотнить код? Или вы хотите сделать его более читабельным? В таком случае вы можете добавить отдельные строки с определением переменной или вычислением чего-либо, а не пытаться всё сделать в одной строке.
- Как ещё можно сделать код более читабельным?
- Можно ли ещё уменьшить количество шагов?
- Есть ли переменные или функции, которые не нужны или не используются?
- Какие-то шаги повторяются? Посмотрите, можно ли определить в другой функции.
- Существуют ли более эффективные способы обработки крайних случаев?
«Программы должны быть написаны так, чтобы люди их читали, и лишь во вторую очередь — чтобы машины их исполняли».
Джеральд Сассман и Гарольд Абельсон, авторы “Structure and Interpretation of Computer Programs”
7. Отлаживайте
Этот шаг необходимо выполнять в ходе всего процесса. Сквозная отладка поможет раньше выловить любые ошибки синтаксиса или недостатки логики. Воспользуйтесь преимуществами своего IDE (Integrated Development Environment) и отладчика. При обнаружении бага рекомендуется просматривать код построчно, стараясь найти неожиданные вещи. Несколько советов:
- Читайте, что пишется в сообщения об ошибках в консоли. Иногда в них указываются номера строк для проверки. Это даст вам исходную точку для поисков, хотя иногда проблемы могут скрываться в других строках.
- Комментируйте блоки кода или строки, а также выходные данные, чтобы быстро подмечать поведение кода. При необходимости код можно всегда раскомментировать.
- Используйте другие образцы данных, если возникают непредусмотренные сценарии.
- Сохраняйте разные версии файла, если применяете другие подходы. Не стоит терять наработанное, если захочется откатиться к прежнему решению!
«Самый эффективный инструмент отладки — тщательное продумывание в сочетании с разумно размещёнными командами вывода на экран».
Брайан Керниган, профессор информатики в Принстонском университете
8. Пишите полезные комментарии
Через месяц вы можете и не вспомнить, что означает каждая строка кода. А тот, кто будет работать с вашим кодом, вообще этого не знает. Поэтому важно писать полезные комментарии, чтобы избежать проблем и сэкономить впоследствии время, когда придётся снова вернуться к этому коду.
Избегайте таких комментариев:
// Это массив. Итерируем его.
// Это переменная.
Старайтесь писать короткие, высокоуровневые комментарии, которые помогут понять, что тут происходит, если это не очевидно. Это пригодится при решении сложных задач, вы сможете быстро понять, что делает конкретная функция, и почему. Благодаря использованию понятных комментариев и имён переменных и функций вы (и другие люди) сможете понять:
- Для чего этот код?
- Что он делает?
9. Получайте отзывы посредством ревизии кода
Получайте отзывы от коллег, руководителей и других разработчиков. Читайте Stack Overflow. Смотрите, как другие решали аналогичные задачи и учитесь у них. Нередко бывает несколько способов решения задачи. Узнайте, что они собой представляют, и вам будет быстрее и проще приходить к ним самостоятельно.
«Неважно, насколько медленно вы пишете чистый код, вы всегда будете тратить больше времени, если пишете грязный код».
Дядя Боб Мартин, программный инженер и соавтор манифеста Agile
10. Практикуйтесь, практикуйтесь, практикуйтесь
Даже опытные разработчики постоянно практикуются и учатся. Если вы получили полезный отклик, внедрите его. Снова решите задачу, или аналогичные задачи. Заставляйте себя. С каждой решённой задачей вы становитесь лучше как разработчик. Радуйтесь каждому успеху и не забывайте, как много вы уже прошли. Помните, что программирование, как и любая деятельность, со временем будет даваться всё проще и легче.
«Гордитесь тем, сколько вы прошли. Верьте в то, что пройдёте ещё больше. Но не забывайте наслаждаться путешествием».
Майкл Джозефсон, основатель Института этики Джозефа и Эдны Джозефсон
Где решать задачи по программированию, чтобы пройти путь from zero to hero
Если вам о чём-то говорят фамилии Зив, Хомченко и Рымкевич, иди сюда, дай обниму, бедолага-олимпиадник, то вы наверняка знаете, как важно прорешивать задачи для полноценного, осознанного и глубокого понимания изученного материала. Когда нет или совсем мало реальной практики, задачи дают возможность покрыть практикой все теоретические знания, погрузиться в неожиданные выводы, сложности, баги, препятствия. Более того, даже если практики достаточно, задачи помогают относительно быстро, комплексно и глубоко проработать типичные и нетипичные ситуации, возникающие в разработке (любой другой науке). Это всегда безопасный (никто не взрывает лабораторию и не роняет прод), доступный и удобный способ подробно разобраться в предмете. Определённо, программирования это касается в первую очередь.
Как решать задачи?
Большинство сайтов из этого дайджеста предоставляют удобные и интуитивные интерфейсы для работы с кодом онлайн, и, кажется, этого вполне достаточно. Но такая практика быстро выветривается из головы: на 12-15 задаче ты уже напрочь не помнишь даже формулировку первых, не то что свои выводы и находки. Это неудобно и иногда сводит все старания на нет.
- Положите перед собой блокнот или тетрадку, чтобы фиксировать там две важных вещи: свои находки и вопросы, в которых нужно не забыть разобраться (они обязательно возникают по ходу решения задач, особенно более высокого уровня сложности).
- После окончания работы над очередным сетом задач пройдитесь по записям, подчеркните самое главное, начните искать ответы на вопросы.
- Перед новым подходом просмотрите предыдущие записи, освежите в памяти решённое.
- Если вы нашли изящный путь решения, обязательно используйте его в дальнейшем. Старайтесь, как и в математике, найти наиболее рациональное и даже красивое решение.
- Если вам удалось решить очередную задачу, нагородив костылей, вернитесь к ней позже и попробуйте отрефакторить своё же решение — это не напрасная трата времени, а практика работы над хорошим кодом, которая не помешает любому уровню специалиста.
- Если на портале есть какие-то челленджи или соревнования, обязательно участвуйте — даже если у вас нет ни шанса на победу, вы испытаете своё мышление в новых экстремальных условиях и сможете сравнить себя с другими участниками. В таком опыте обычно лежат точки роста.
- Если не получается — не сдавайтесь, разбирайтесь, используйте источники и сторонние сайты, не стесняйтесь обращаться к менторам и коммьюнити.
- Помните: путь в любую разработку начинается с hello world.
�� Kaggle — сайт содержит множество исследовательских задач, связанных с машинным обучением и большими данными. Особенно ценно то, что на Kaggle можно найти крутые датасеты, код и материалы для самостоятельного изучения и тренировок.
- Kaggle titanic dataset. Анализ данных с помощью SQL запросов
- Разговор с дата-сайентистом — гроссмейстером Kaggle
- Kaggle: Британские спутниковые снимки. Как мы взяли третье место
- Как я занял 13 место из 3500+ участников и стал Kaggle Competition Master / Хабр
- «Айсберг вместо Оскара!» или как я пробовал освоить азы DataScience на kaggle / Хабр
- Kaggle: История о том как мы учились предсказывать релевантность поисковых запросов и заняли 3-е место
�� Codewars — сборник задач и челленджей по широком спектру тем: алгоритмам, проектированию, паттернам, различным языкам программирования.
�� LeetCode — популярный сайт с задачами, который особенно любят соискатели, мечтающие о работе в FAANG. Отличается от остальных тем, что решение задач нацелено именно на подготовку к собеседованиям в крупных компаниях.
- From Zero to Hero: определите ваш уровень решения LeetCode задач от 1 до 5
- Я решил 500 задач на LeetCode — и они действительно меня чему-то научили
- Есть ли польза от решения алгоритмических задач на LeetCode?
- Пройти LeetCode за год: экскурсия по сайту и roadmap
- Моя история подготовки к интервью в FAANG
- Разбор алгоритмических задач с собеседований в Google, Facebook, Amazon
- Первые 255 задач на «литкоде» / Хабр
�� Codeforces — популярнейший сайт с задачами, тренировками, соревнованиями (раундами) и прочими активностями для прокачки практики программирования. Кроме того, что позволяет решать всё про всё и содержит одну из крутейших баз заданий, имеет развитое сообщество, систему рейтинга и множество встроенных элементов геймификации.
- Если хочешь разобраться, найдешь возможность»: говорим о Codeforces с основателем проекта
- Как выиграть ВСОШ по информатике и больше не волноваться о ЕГЭ?
�� Exercism — классический задачник для 67 языков программирования. Подразумевает геймификацию, систему менторинга, обучение и т.д. При таких параметрах, конечно, имеет своё коммьюнити (хоть и не такое впечатляющее, как у предыдущих ресурсов).
�� All Cups — соревновательно-обучательно-решательный портал с множеством задач от VK. Включает задачи по спортивному программированию (привет участникам олимпиады!), машинному обучению, искусственному интеллекту и, что особенно важно, по системному администрированию и всяческому хайлоаду. Если так можно сказать, это самый комфортный сайт для русскоязычного программиста (но мы же помним, что без английского далеко всё равно не уйти, даже здесь).
- All Cups — новая экосистема чемпионатов для IT-специалистов / Хабр
- Соревнования по программированию на платформе All Cups
- All Cups: история одного дизайна экосистемы с большой историей
�� Задачи для программистов — раздел задач на ТПрогере, который включает задачи и их разбор от компаний и пользователей. Ещё один комфортный русскоязычный ресурс с форматом статей-разборов.
�� SQL-EX.ru — совершенно вырвиглазный сайт с наикрутейшими задачами и базой знаний по SQL. Отличное русскоязычное сообщество, справочники, учебники, обсуждения, статьи и книги. Настоящий мир SQL, пригодный как для школьника, так и для старшего инженера и разработчика.
- Как изучать SQL в 2023 году
- Ультимативная дорожная карта для изучения SQL и баз данных в 2023 году + источники для знаний
�� Питонтьютор — интерактивный учебник-задачник по Python с задачами разной сложности. Русскоязычный, приятный, пошаговый и комфортный. Отличная помощь начинающим (и не только) питонистам.
- Как не стать Python-разработчиком
- Изучаем Python за 6 месяцев. Подробный план обучения
Подборки от авторов Хабра — где-то есть неактуальные ссылки, но в целом подборки полезные.
- Сайты для обучения программированию: Топ 100
- Топ 8 лучших ресурсов для практики программирования в 2018
- 11 крупнейших международных соревнований по программированию на 2022 год / Хабр
P.S. Если вы давно хотели написать статью на Хабр, но сомневаетесь в своих силах или качестве материала, пишите мне в личку или присылайте черновик и свои вопросы на neo@habr.team — поможем, подскажем, дадим редакторский совет.
- обучение
- практика программирования
- обучение программированию
- задачи по программированию
Как Решать Задачи По Программированию
Наверное, у многих новичков бывало такое, когда ты смотришь решение какой-то задачи в Интернете или на уроке, читаешь чужой код и кажется что всё максимально просто и понятно. Но вот приступаю к решению такой же задачи самостоятельно, впадаешь в ступор. Что делать, с чего начать и т. д. Хотя казалась бы было всё было понятно. Знакомое чувство? С ним сталкивается каждый, кто только начинает изучать программирование. Поэтому сегодня я расскажу как решать зачади по программированию на языке Python, да и любом другом языке. Меня зовут Макс. Я один из авторов YouTube-канала PyLounge. Поехали!
Во-первых, ты должен чётко понимать, что от тебя требуется.
Как нельзя лучше сделать это тебе поможет декомпозиция. Декомпозиция — это когда ты разбиваешь одну большую сложную задачу на несколько мелких простых задача. При этом в момент дробления задачи не пытайся думать о программной реализации и программировании вообще. Старайся думать как ТЫ бы решал эту задачу, ты сам, будучи человеком. Опиши свои человеческие действия на каждом этапе. Перед этим вдумчиво прочитай текст задачи. Можно даже читать вслух. Часто проговаривание вслух помогает восприятию. И начинай декомпозировать с человеческой точки зрения.
Допустим перед нами стоит задача:
Написать функцию, которая получает из текстового файла словарь с настройками графики для игры.
Файл имеет следующий вид:
Начинаем смотреть на задачу глазами обычного человека. Вот у меня на Рабочем столе лежит текстовый файл. Чтобы мне прочитать содержимое файла его надо открыть. Соответственно это и есть первый пункт наше алгоритма — Открыть файл.
Далее я глазами вижу первую строчку файла. Здесь через пробел записаны два слова. Так как в файле записаны настройки графики то, очевидно, в каждой строчке хранится пара «название опции — её значение». Например, Разрешение 1920×1080. Соответственно я, будучи человеком, мысленно читаю первую строчку. Дальше мне нужно отделить «ключ настройки» от её значения. Как я будучи человеком понимаю, что в этой строчке два разных слова? Как я понимаю, что здесь не одно слово? Слова разделены между собой пробелами. Значит слово до пробела ключ, после значение. Это и есть следующий этап нашего алгоритма — читаем строку и делим её, за разделитель принимаем символ пробела. Затем первую половину строки заносим в ключ, вторую в значение.
Далее я будучи человеком, опускаю взгляд на следующую строку и повторяю описанное выше действие. Потом следующую и следующую. До тех пор, пока в файле не закончатся строки. Это и есть следующий шаг — по очереди обрабатывать каждую строчку из файла.
Теперь у меня в голове (или в переменной типа dict (словарь)) имеется вся нужная информация. По аналогии с функцией мы возвращаем словарь с данными. Потом я закрываю файл. Вот у нас и есть по сути готовый алгоритм:
1. Открыть файл.
2. Читаем строку из файла.
3. Делим её на две части через символ пробела.
4. Записываем первую часть строки в «ключ», а второю в «значение ключа» (например, ключ vsync — значение ключа off).
5. Аналогичным образом по очереди обрабатываем каждую следующую строку. Пока строчки в файл не кончатся.
6. Закрываем файл.
7. Сообщаем результат.
Можно для себя набросать псевдокод. То есть описание каждого шага алгоритма не на конкретно языке программирования, а абстрактно, на русском. Также неплохим вариантом может являться нарисовать блок-схему.
Псевдокод — это изложенные простым языком шаги алгоритма. Иными словами, это пошаговый план решения задачи. Если вы и так чётко понимаете процесс или задача относительно простая, то псевдокод и схему можно пропустить.
Теперь когда у нас имеется алгоритм, надо задать себе два вопроса:
1. Что мы имеем на вход (входящие данные).
2. Что мы имеем на выходе.
Снова смотри с позиции обычного человека. Чтобы я, будучи человеком, смог открыть какой-то файл и прочитать его, я должен знать где он лежит. Значит на вход мы и наша функция получает путь до файла.
Также в условии уже сказано, что мы должны сформировать словарь настроек. Значит словарь с ключами и значениями (куда сохраняются данные из файла) мы и должны вернуть из функции (вывести результат).
Теперь пытаемся переложить это на программный код. Также построчно всё проговаривая:
import os def read_settings_file(file_name): settings = dict() file = open(file_name, 'r') for row in file.readlines(): key, value = row.split(' ') settings[key] = value file.close() return settings print(read_settings_file('D://game_settings.txt')Очень важно давать осмысленные и понятные названия переменным и функция. Это помогает делать код более читаемым и ты сам не запутаешься, если откроешь его спустя неделю. Рекомендую посмотреть наше видео «4 Совета Которые Помогут Сделать Твой Код Лучше».
Также стоит подумать, какие ошибки у нас могут возникнуть. Опять таки, задаём себе вопросы, например:
1. Что делать если файл не будет существовать?
Надо сделать проверку, добавить обработку такой ситуации.
2. Что случится если структура файла будет другой?
3. Кодировка файла будет нестандартной?
Нужно придумать как можно больше таких вопросов. И ответить на каждый из них, реализовав программное решение с помощью исключений, сообщений об ошибках и т.д.
Теперь когда у нас есть рабочее решение на руках, надо подумать, как его можно улучшить. То есть надо провести рефакторинг кода и сделать решение более эффективным.
Рефакторинг — это процесс улучшения кода, когда мы переписываем какие-то участки кода, которые можно сделать лучше.
При рефакторинге можно задавать себе следующие вопросы:
1. Можно ли получить этот результат как-то иначе? Какие еще подходы есть?
2. Понятно ли это решение с первого взгляда?
3. Можно ли использовать результат или метод для какой-то другой задачи?
4. Можно ли улучшить производительность решения?
5. Как эту задачу решают другие люди?
Никогда не пренебрегай внутренним диалогом с собой. Составляй план, блок-схему и т. д. Многие люди не делают этого, им кажется, что это бесполезная трата времени. Но на самом деле именно в этом и кроется ключевой момент в решении любой задачи.
В нашем случае мы могли бы работать с файлом через менеджер контекста, чтобы явно не вызывать функцию close () и метод readlines (). И применить к значением настроек функцию strip (), что бы не оставлять в строке символы переноса, табуляции и т. д. В случае с Python можно ещё и аннотации типов добавить:
from typing import Optional, Dict import os def read_settings_file(file_name:str) -> Optional[str]: if not os.path.exists(file_name): return None settings:Dict[str, str] = dict() with open(file_name, 'r') as file: for row in file: key, value = row.split(' ') settings[key] = value.strip() return settings print(read_settings_file('D://game_settings.txt')К слову, очень важно смотреть, как другие решали подобную задачу. Так читая чужой код вы набираетесь опыта и вырабатываете надсмотренность. В чужом коде можно подсмотреть интересные решения, которые затем взять себе на вооружение.
Я в своё время очень часто смотрел чужие решения, сравнивал их со своим и это сильно мне помогло. Главное не смотреть ответ сразу) А именно сравнивать своё решение с чужим, если сам ну никак не можешь сделать.
Я привел пример простой задачи. Но более сложная задача будет отличаться лишь количеством этапов и инструментами, которые будет необходимо применить.
Запомните, умение решать задачи — это навык. Чем больше практики, тем лучше вам это будет удаваться. Если вы хотите много раз подтягиваться, то надо подтягиваться. Если вы хотите научиться быстро бегать, то надо бегать. Если вы хотите научиться решать задачи по программированию, то надо решать задачи. Истина всегда на поверхности.
Также есть чуть более подробная видеоверсия этой статьи на YouTube: