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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Обзор задач по алгоритмам для собеседований — генерация множеств

Этим постом начинается разбор задачек по алгоритмам, которые крупные IT-компании (Mail.Ru Group, Google и т.п.) так любят давать кандидатам на собеседованиях (если плохо пройти собеседование по алгоритмам, то шансы устроиться на работу в компанию мечты, увы, стремятся к нулю). В первую очередь этот пост полезен для тех, кто не имеет опыта олимпиадного программирования или тяжеловесных курсов по типу ШАДа или ЛКШ, в которых тематика алгоритмов разобрана достаточно серьезно, или же для тех, кто хочет освежить свои знания в какой-то определенной области.

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

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

1. Начнем с баян-баяныча: нужно сгенерировать все правильные скобочные последовательности со скобками одного вида (что такое правильная скобочная последовательность), где количество скобок равно k.

Эту задачу можно решить несколькими способами. Начнем с рекурсивного.

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

Сложность этого алгоритма — , дополнительной памяти требуется .

При заданных параметрах вызов функции выведет следующее:

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

Все правильные скобочные последовательности для одного типа скобок можно упорядочить с учётом того, что . Например, для n=6 самой лексикографически младшей последовательностью будет , а самой старшей — .

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

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

Сложность этого алгоритма такая же, как и в прошлом примере.

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

Отлично, со скобками пока всё, теперь перейдем к генерированию подмножеств. Начнем с простой задачки.

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

Заметим, что количество подмножеств такого множества равно в точности . Если каждое подмножество представить в виде массива индексов, где означает, что элемент не входит в множество, а — что входит, тогда генерирование всех таких массивов будет являться генерированием всех подмножеств.

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

Сложность этого алгоритма — , по памяти — .

Теперь чуть-чуть усложним предыдущую задачу.

3. Дан упорядоченный массив по возрастанию с числами от до , требуется сгенерировать все его -элементные подмножества (решить итеративным способом).

Замечу, что по формулировке эта задача похожа на предыдущую и решать её можно с помощью примерно такой же методики: взять изначальный массив с единицами и нулями и последовательно перебрать все варианты таких последовательностей длиной

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

Также упорядочим последовательность по кодам символов: (это, конечно, странно, но так надо, и сейчас поймем, почему). Например, для самой младшей и старшей будут последовательности и .

Осталось понять, как описать переход от одной последовательности к другой. Тут всё просто: если меняем на , то слева пишем лексикографически минимальное с учетом сохранения условия на . Код:

Сложность этого алгоритма — , по памяти — .

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

Теперь попробуем рекурсию. Идея простая: на этот раз обойдемся без описания, смотрите код.

Пример работы:

Сложность такая же, как и у прошлого способа.

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

Будем решать с помощью рекурсии. Решение похожа на предыдущее, где у нас есть вспомогательный список. Изначально он нулевой, если на -ом месте элемента стоит единица, то элемент уже есть в перестановке. Сказано — сделано:

Сложность этого алгоритма — , по памяти —

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

6. Сгенерировать все двумерные коды Грея длиной n.

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

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

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

Это сложно воспринять «на слух», изобразим итерации этого алгоритма.

Сложность этой задачи — , по памяти такая же.

Теперь усложним задачу.

7. Сгенерировать все k-мерные коды Грея длиной n.

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

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

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

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

Однако, в рамках экономии памяти, будем решать эту задачу с помощью двух одномерных массивов длины : в одном массиве будут лежать сами элементы последовательности, а в другом их направления (стрелочки).

Сложность алгоритма — , по памяти — .

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

В следующем посте будем разбирать задачки на динамику.

Источник

10 шагов по решению задач в программировании

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

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

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

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

Какие вопросы можно себе задать:

2. Пройдите по задаче вручную как минимум с тремя наборами данных

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

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

Крайние случаи: проблемы или ситуации, возникающие только при экстремальных (минимальных или максимальных) значениях параметров функционирования.

Вот, к примеру, несколько наборов данных для использования:

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

Давайте пройдём по массиву [1]

3. Упрощайте и оптимизируйте свой алгоритм

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

4. Пишите псевдокод

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

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

Вот пример псевдокода, в основном состоящего из слов:

А вот псевдокод, в котором слов гораздо меньше:

Главное, писать код построчно и понимать логику каждой строки.

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

5. Преобразуйте псевдокод в нормальный код и отладьте его

Когда ваш псевдокод будет готов, преобразуйте каждую строку в реальный код на вашем языке. Здесь мы воспользуемся JavaScript.

Если вы писали на бумаге, то перенесите всё в редактор в виде комментариев, а затем замените каждую строку.

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

Ниже приведён код, полученный после обработки каждой строки псевдокода. Символы // обозначают строки из псевдокода. Жирным выделен реальный код на JavaScript.

Уберём псевдокод, чтобы не путаться.

Иногда разработчики-новички настолько увлекаются синтаксисом, что им трудно идти дальше. Помните, что со временем вам будет проще соблюдать синтаксис, и нет ничего стыдного в том, чтобы потом при написании кода обращаться к справочным материалам для корректного соблюдения синтаксиса.

6. Упрощайте и оптимизируйте код

Возможно, вы заметили, что упрощение и оптимизация — это повторяющиеся темы.

Эдсгер Дейкстра, нидерландский учёный и один из первопроходцев в ряде областей информатики

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

Задавайте себе такие вопросы:

«Программы должны быть написаны так, чтобы люди их читали, и лишь во вторую очередь — чтобы машины их исполняли».

Джеральд Сассман и Гарольд Абельсон, авторы “Structure and Interpretation of Computer Programs”

7. Отлаживайте

Этот шаг необходимо выполнять в ходе всего процесса. Сквозная отладка поможет раньше выловить любые ошибки синтаксиса или недостатки логики. Воспользуйтесь преимуществами своего IDE (Integrated Development Environment) и отладчика. При обнаружении бага рекомендуется просматривать код построчно, стараясь найти неожиданные вещи. Несколько советов:

«Самый эффективный инструмент отладки — тщательное продумывание в сочетании с разумно размещёнными командами вывода на экран».

Брайан Керниган, профессор информатики в Принстонском университете

8. Пишите полезные комментарии

Через месяц вы можете и не вспомнить, что означает каждая строка кода. А тот, кто будет работать с вашим кодом, вообще этого не знает. Поэтому важно писать полезные комментарии, чтобы избежать проблем и сэкономить впоследствии время, когда придётся снова вернуться к этому коду.

Избегайте таких комментариев:

// Это массив. Итерируем его.
// Это переменная.

Старайтесь писать короткие, высокоуровневые комментарии, которые помогут понять, что тут происходит, если это не очевидно. Это пригодится при решении сложных задач, вы сможете быстро понять, что делает конкретная функция, и почему. Благодаря использованию понятных комментариев и имён переменных и функций вы (и другие люди) сможете понять:

9. Получайте отзывы посредством ревизии кода

Получайте отзывы от коллег, руководителей и других разработчиков. Читайте Stack Overflow. Смотрите, как другие решали аналогичные задачи и учитесь у них. Нередко бывает несколько способов решения задачи. Узнайте, что они собой представляют, и вам будет быстрее и проще приходить к ним самостоятельно.

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

Дядя Боб Мартин, программный инженер и соавтор манифеста Agile

10. Практикуйтесь, практикуйтесь, практикуйтесь

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

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

Источник