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

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

Где учиться решать алгоритмы

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

Зачем разработчику решать алгоритмы

Чем лучше разработчик понимает, как алгоритмы реализованы внутри, тем проще ему будет найти эффективное решение и избежать багов. Например, если разработчик разбирается в алгоритмах, то он сможет ускорить доступ к данным в хэш-таблице. Хорошее знание алгоритмов также необходимо для модификации сложных алгоритмов, чтобы их можно было гибко использовать под конкретные задачи. В этой статье мы делимся ресурсами, которые помогут разработчику научиться решать алгоритмы
и подготовиться к собеседованию.

Бесплатные курсы по алгоритмам

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

Курс научит разбираться в базовых структурах данных, алгоритмах сортировки и поиска. Это темы, которые должен понимать каждый разработчик. Они рассматриваются
с реализацией на Java. Материал разделен по модулям, после которых можно пройти тест и выполнить дополнительные задания.

Курс сфокусирован на жадном алгоритме и динамических парадигмах, а также на NP-полных задачах. Советуем приступать
ко второй части сразу после прохождения первой, когда в памяти еще свежи основы. После каждой темы будут дополнительные задания, которые нужно выполнить
для закрепления материала.

В курсе разбирают базовые алгоритмические методы: жадные алгоритмы, метод «разделяй
и властвуй», динамическое программирование. Занятия проходят на интерактивной платформе, где можно сразу писать код и проверять ошибки. В курсе есть как теоретические задачи, так и тесты с выбором ответы, практические задания и задачи с повышенной сложностью.

Грокаем алгоритмы: Гайд по алгоритмам для тех, кому сложно решать задачи

Эта статья — для разработчиков, которые частично уже знают алгоритмы. Если вы еще не знакомы с ними, советуем пройти трек «Алгоритмы и структуры данных» в Хекслете. Вы изучите списки, стеки, очереди, структуры данных, которые помогут проектировать структуры и алгоритмы.

Бесплатные курсы по программированию в Хекслете

• Освойте азы современных языков программирования
• Изучите работу с Git и командной строкой
• Выберите себе профессию или улучшите навыки

Грокать алгоритмы или не грокать? Что делать, если вам не хочется решать сто задач к вашему следующему собеседованию?

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

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

Коротко расскажу о себе, чтобы вы убедились в моей экспертности. Я программирую уже 20 лет, за это время я много раз менял место работы. Всего я прошел около 30 воронок найма — больше 120 собеседований. Плюс к этому у меня есть опыт с той стороны баррикад: я провел около 300 технических собеседований и больше 200 собеседований по системному дизайну .

Где мы грокаем алгоритмы

Если вы когда-нибудь искали работу, то знаете, что есть ресурсы, которые собирают задачи с собеседований . Один из них — LeetCode, это самый популярный сайт, где очень много задач. Плюс вокруг него сложилось развитое сообщество, где можно обсуждать задачки с другими инженерами. Если выдается свободная минутка, я всегда не прочь провести ее на LeetCode. Там я решаю задачи или читаю чужие решения, после чего сравниваю со своими.

Самая большая проблема LeetCode в том, что сайту не хватает продуманной системы обучения. У него много разных задач, в которых легко потеряться. Сколько нужно таких задач, чтобы подготовиться к собеседованию? Я бы предпочел двигаться по продуманной программе, в конце которой я смогу ощутить уверенность в собственных знаниях. Но системы нет, а я ленивый, и вообще — не хочу решать 500+ задач.

Одно из популярных решений для этой проблемы — решать задачи, которые относятся к одной структуре данных (например, прорешать несколько задач с деревьями). Какая-то система обучения появляется, но это решение меня все равно не устраивает. Например, что делать, если задачу можно решить при помощи разных структур данных?

Какую систему обучения придумал я

Я бы предпочел такую систему, в которой задачи распределены по паттернам, а не по структурам данных. Мои любимые паттерны — скользящее окно, нахождение цикла и топологическая сортировка. Когда я научился пользоваться этими методами, я стал решать незнакомые задачи по аналогии с задачами, которые решал до этого. Благодаря этому весь процесс подготовки к собеседованиям стал более интересным и веселым. Ну и конечно же, более систематичным.

Я обнаружил 25 паттернов, которые лежат в основе решения большинства задач. Думаю, эти паттерны помогут кому угодно показывать на собеседованиях красивые и элегантные решения. Вся фишка этих паттернов в том, что понимая один из них, вы научитесь решать сразу несколько задач, десятки задач.

Самые распространенные паттерны для решения задач

1. Метод скользящего окна
2. Метод двух указателей
3. Нахождение цикла
4. Интервальное слияние
5. Цикличная сортировка
6. In-place Reversal для LinkedList
7. Поиск в ширину
8. Поиск в глубину
9. Двоичная куча
10. Подмножества
11. Усовершенствованный бинарный поиск
12. Побитовое исключающее ИЛИ
13. Top K Elements
14. K-образное слияние
15. Задача о рюкзаке 0-1
16. Задача о неограниченном рюкзаке
17. Числа Фибоначчи
18. Наибольшая последовательность-палиндром
19. Наибольшая общая подстрока
20. Топологическая сортировка
21. Чтение префиксного дерева
22. Задача: количество островов в матрице
23. Метод проб и ошибок
24. Система непересекающихся множеств
25. Задача: найти уникальные маршруты

Читайте также: Это снова я, резиновая уточка: что такое метод Фейнмана и почему с его помощью так просто изучать программирование

Метод скользящего окна

Контекст: Мы используем этот метод, когда у нас есть входные данные с заданным размером окна.

Задачи для этого паттерна:

• 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 и командной строкой
• Выберите себе профессию или улучшите навыки

Как научиться решать алгоритмические задачи?

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

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

Оттачивать навыки написания кода на LeetCode — это не просто запоминать ответы. Вам нужно знать шаблоны решения задач и уметь их применять. Количество решённых задач — это только одна сторона знакомства с шаблонами, но изучение включает в себя не только числа.

Пункт 0: За пределами основ компьютерных наук

В этом руководстве предполагается, что вы по крайней мере слышали об основных вещах, таких как двойные указатели и манипулирование битами. Вам не нужно знать их в совершенстве, но хотя бы базовые знания о том, что это такое, помогут вам более эффективно практиковаться решать задачи на LeetCode. Если вы изучали только основы компьютерных наук, вам может понадобиться обратиться к некоторым книгам, чтобы немного подтянуться.

Легкие алгоритмические задачи на LeetCode

Легкие задачи призваны помочь вам ознакомиться с основными приёмами. Обычно у них есть грубые тривиальные решения. Вам нужно научиться применять эти приёмы, чтобы лёгкие задачи не вызывали у вас никаких проблем.

Пункт 1: Практика основных приёмов

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

Как тренироваться

1. Отсортируйте задачи по убыванию рейтинга принятия (англ. acceptance rate). Обычно задачи с более высоким рейтингом принятия немного легче.
2. Старайтесь решать лёгкие задачи без подсказок.
3. Как ни странно, злоупотреблять кнопкой «run» не очень полезно. Попробуйте написать решение лёгких задач так, чтобы они были приняты с первого раза. Такой подход имитирует ситуацию, когда вы пишете код на доске, что позволит вам научиться рассматривать все варианты сразу в голове.
4. Иногда следует приглядываться к решениям в топе на предмет применения каких-то интересных приёмов. Часто решения попадают в топ, когда они короткие и недостаточно документированы. Также читайте комментарии и не стесняйтесь просить пояснить какие-то моменты.
5. Как только вы чувствуете что изучили достаточно шаблонов решений простых задач, вернитесь к пункту 1 и решите, готовы ли вы двигаться дальше.

Средние алгоритмические задачи на LeetCode

Средние задачи предназначены для того, чтобы вы научились видеть суть. Чаще всего они представляют собой различные комбинации лёгких задач. Но решения «в лоб» часто могут привести к ошибке времени выполнения. Вам нужно уметь определять, какой именно шаблон решения требует та или иная задача.

Пункт 2: Распознавание шаблонов задач

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

Как тренироваться

1. Внимательно читайте сам текст задачи и ищите в нём подсказки по поводу реализации. Например, количество подзадач может указывать на динамическое программирование, строковое преобразование с помощью dictionary указывает на поиск в ширину, поиск в длину или префиксное дерево, поиск повторяющихся или уникальных элементов указывает на хеширование или манипулирование битами и т. д. Если вам требуется более полный список приёмов, то следует обратить внимание на книгу-руководство для программистов.
2. Когда есть приблизительное представление о решении — это уже полпути. Попытайтесь реализовать его, даже если оно не совсем оптимальное. Это нормально, ведь обычно люди тратят гораздо больше времени на оптимизацию, чем на само решение.
3. Когда вы реализовали своё неидеальное решение, посмотрите на топовые решения этой же задачи, чтобы посмотреть, как вы можете улучшить своё.
4. Затем попытайтесь хорошо понять основную мысль и реализовать более оптимальное решение, не используя подсказки.
5. Как только вы чувствуете, что можете больше, чем просто применять шаблоны, настало время перейти к сложным задачам.

Сложные алгоритмические задачи на LeetCode

Сложные задачи предназначены для того, чтобы заставить вас напрячься. Обычно 45 минут достаточно для того, чтобы вы могли придумать рабочее решение. Чтобы научиться их решать, нужно научиться видеть какие-то более изящные пути, чем тривиальное решение «в лоб».

Пункт 3: Последняя проверка

В сложных задачах обычно есть ограничения, которые не позволят вам получить решения, используя привычные шаблоны. Если вы можете модифицировать обычные приёмы для решения сложных задач, то ваша подготовка завершена. Время здесь не так важно, вы должны научиться видеть связь между привычными шаблонами решений и этими ограничениями.

Как тренироваться

1. В этом случае решение задачи важнее, чем нахождение оптимального решения. Если вы можете решить задачу «в лоб», жертвуя ограничениями по времени и/или месту, делайте это.
2. И только после нужно определить, как оптимизировать решение, чтобы оно соответствовало ограничениям.
3. Если у вас не получается оптимизировать решение, то самое время обратить внимание на топовые варианты реализации. Здесь очень важно понять ход решения. Вы должны научиться подбирать правильный алгоритм и использовать нужные структуры данных, а также уметь учитывать все случаи.
4. Как только вы научитесь находить решения одних сложных задач, переходите к другим видам задач и старайтесь делать ваши решения более оптимальными.

Спасибо, что прочитали. Надеемся, вы нашли для себя что-то полезное.

***
Подписывайтесь на наш канал в Telegram!

Как решать алгоритмические задачи

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

В этом уроке вы узнаете основы этого процесса, без которых сложно освоить остальные темы курса.

Часто можно встретить мнение: «Я прочитаю условие задачи, потом посмотрю каноничное решение и запомню его». Увы, так не работает. В поведенческой экономике есть такое понятие, как «Эффект Икеа». Люди ценят больше то, к созданию чего приложили руку и много усилий. То же самое и с алгоритмическими задачами — мы ценим и лучше запоминаем те, которые придумали, а иногда выстрадали сами. Время, проведённое за решением, поможет в дальнейшем легче находить паттерны в новых задачах. Воспринимайте сложности в процессе решения задач как вызов, который сделает вас ощутимо сильнее.

Есть ещё одна ловушка, в которую часто попадают разработчики.

«Да что тут сложного, всё понятно, пойду сразу запрограммирую». Дальше происходит ситуация, знакомая многим. Разработчик пишет код, запускает, а он выдаёт ошибку. Ошибка простая и понятная. Он её исправляет. Затем вылезает новая, которую исправить не так просто. Через несколько итераций код превращается в чудовище Франкенштейна, где некоторые части исправлены только потому, что а вдруг ошибка именно тут.

Изначально на всю задачу разработчик выделял 20 минут. Фактически ушло 4 часа. Злость и разочарование. Вроде осталось совсем чуть-чуть поправить, чтобы заработало. Впрочем, то же самое было и 3,5 часа назад.

Чтобы такое происходило как можно реже, не пренебрегайте решением задачи на листочке. Уберите подальше клавиатуру и правильно подготовьтесь к написанию кода. Это не значит, что сначала нужно написать программу в блокноте (хотя этот опыт был бы полезен для собеседований). Но что же это значит?

Последовательность решения алгоритмических задач

1. Внимательно прочитайте условие задачи:

• зафиксируйте, что нужно найти;
• отметьте все особенности входных данных;
• ознакомьтесь с лимитами по времени и памяти.

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

1. Придумайте примеры входных данных и зарисуйте, если это возможно. В задачах нашего курса всегда будет пара примеров для понимания условия. Допишите ещё и ответьте на вопрос: «Достаточно ли примеров получилось?» О том, как придумывать хорошие тесты, поговорим подробнее в одном из следующих уроков.
2. На примерах разберите, как вы находили бы ответ на заданный вопрос, если бы вам потом не надо было писать код. Подумайте, какой результат работы своей программы вы ожидаете при обработке каждого набора входных данных. Запишите, как именно находите ответ, какие формулы используете для промежуточных вычислений. Возможно, вы делите входные данные друг на друга, сортируете массив или вычисляете какие-то вспомогательные данные?

Правильный результат на этом этапе — решение, которое легко объяснить школьнику. В нём не встречаются сложные слова и высокоуровневые абстракции.

Алгоритм, который первым приходит на ум, называется наивным. Во многих случаях он будет неоптимальным. Не пропускайте формулирование наивного алгоритма, даже если вы понимаете, что он работает очень медленно. Подумайте, чем конкретно плох алгоритм. Он работает медленно? Ему требуется много дополнительной памяти?

Часто бывает так, что придумать алгоритм не получилось. На этот случай есть 5 советов, как подступиться к задаче:

• Предположите, какие дополнительные ограничения бы вам помогли. Если в задаче дана последовательность произвольных чисел, попробуйте решить задачу, например, для последовательности только из целых чисел, а потом переходите к вещественным числам.
• Попробуйте решить задачу для входных данных небольшого размера. Например, 3 числа в последовательности вместо 200.
• Подумайте, можете ли вы разбить задачу на подзадачи меньшего размера. Например, если у вас есть массив длины n и требуется найти максимальный элемент, что будет, если поделить массив на две равные части? Зная ответ для каждой половины, можно ли получить ответ для целого массива? А если просто убрать один элемент? Аналогично можно работать и с числами, и со строками, обрезать и делить их, находить решение для меньшей задачи, после чего пытаться перейти от решения на меньшем объёме входных данных к решению на большем объёме.
• Предположите, какие из известных вам алгоритмов и структур данных могут помочь в решении задачи. Пока мы будем учиться, задачи будут соответствовать темам из спринта. Чтобы после обучения было удобно пользоваться этим методом, заведите список пройденных тем. Собственный конспект — лучшая подсказка.
• Возьмите какое-то решение, пусть даже вы не уверены в его правильности. Проверьте его на примерах, которые вы придумали. В каких ситуациях ваш алгоритм даст неправильные ответы? Проанализировав неправильное решение, можно найти и исправить ошибки.

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

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

1. Оцените сложность, с которой работает ваш наивный алгоритм. Проверьте, это достаточно хорошая сложность с учётом известных ограничений на входные данные или лимиты не покорятся? Попробуйте обосновать, какая асимптотика вашего алгоритма.
2. Оптимизируйте! Подумайте, как можно улучшить свой алгоритм. Есть несколько способов:

• Bottleneck или Бутылочные горлышко. Как мы уже говорили, так называют самое узкое место программы. Это та часть, которая работает дольше всего. Если у вас есть часть кода, которая работает за квадратичное время, а весь остальной код — за линейное, ищите, можно ли ускорить квадратичную часть. Ведь небольшие изменения в линейной части не дадут асимптотических преимуществ и в большинстве случаев ускорят программу незначительно.

• Повторяющаяся работа. Например, вам надо ответить на один и тот же вопрос для 10 разных элементов массива. Вы знаете, что ответ можно быстро найти на отсортированном массиве. Лучше отсортировать массив один раз в начале, чем делать это каждый раз для каждого из 10 элементов. Чтобы заметить повторяющиеся действия, ищите одинаковые куски кода и внимательно посмотрите все инструкции, которые выполняются в теле каждого цикла вашей программы. Может быть, некоторые инструкции стоит вынести за пределы цикла.
• Ненужные действия. Иногда сортировать не нужно. Например, программе на вход подаются числа и надо найти наименьшее число. Можно массив отсортировать и выдать первый элемент, а можно в процессе считывания перевыбирать минимум. Или вам надо сложить числа в двоичной системе счисления — тогда ни к чему переводить числа в десятичную систему счисления, а потом сумму обратно в двоичную. Проверьте, нет ли у вас лишних действий.
• Оптимальные структуры данных. Ответьте на вопрос, какие операции с данными предстоит осуществлять? Какая структура данных позволит сделать это быстро, без лишних издержек? Может быть, вы хотите быстро узнавать, есть ли элемент в вашем наборе данных, но используете для этого массив?
• Подумайте, всю ли информацию из условия задачи вы уже применили. Может, есть ограничение, которое вы проигнорировали в наивном решении. Перечитайте условие ещё раз.
• Ищите компромисс между памятью и временем. В задачах контеста у вас будет два типа ограничений: на дополнительную память и на время выполнения программы. Иногда мы можем ускорить программу, сохранив промежуточную информацию. В других случаях, как в задаче про счастливые билеты, лучше сэкономить память.

1. Напишите аккуратный код.

• Следите за именами переменных. Хорошее имя переменной описывает, что за объект в ней лежит, даже если эта переменная — просто счётчик цикла.
• Следите за именами функций. Хорошие имена функций складываются как раз в тот алгоритм, который вы озвучили бы пятикласснику.

Часто так пишут рецепты:

Почистите картофель и морковку
Картофель нарежьте кубиками
Морковку нарежьте кружочками
Пробланшируйте овощи
Выложите овощи на тарелку

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

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

1. Внимательно перечитайте написанный код. Особое внимание уделите:

• условным выражениям; иногда можно перепутать знаки < и >или неаккуратно объединить несколько логических условий, забыв о порядке применения отрицания, логического И и ИЛИ .
• условиям выхода из циклов или функций; правильно ли обрабатывается первый и последний элемент? Есть ли ситуации, когда мы выходим из цикла досрочно?
• константам; Вы точно помните, зачем каждая из них нужна? Всегда ли это значение одинаковое?

1. Протестируйте свой код.

Похожие записи:

1. Эффективный ввод-вывод в разных языках программирования
2. Unittest в Django: тестирование моделей
3. Django — доработка шаблона формы регистрации
4. Django ORM и модели