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

Семь бесплатных автоматизированных платформ-задачников для прокачки навыков программирования

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

Проект из Украины «Чекио» сфокусирован на Python и JavaScript. Это сборник игровых задач по программированию для тех, кто уже не новичок. Большой упор на геймификацию, симпатичную графику и общение в сообществе. В самом решении задач игрового процесса нет, но есть общий сценарий для прохождения платформы. Полезная фича — смотреть другие решения и подсказывать студентам как их можно улучшить.

Сборник задач по программированию на разных языках. Цель сервиса — готовить программистов к заданиям, которые встречаются на интервью. Платформа сразу даёт фидбэк на правильность и эффективность решения, показывает варианты решений и позволяет обсудить их с другими участниками. В платной версии можно пройти автоматизированное интервью в Google, Facebook или Amazon: робот подберёт вопросы, засечёт время и даже поможет оценить.

Известный американский проект включает «челленджи», соревнования, вакансии, лидерборд и помощь в подготовке к интервью. Много тематических туториалов в стиле «30 Days of Code» или «10 Days of Statistics».

Задания делятся по конкретным скиллам: алгоритмы, структуры данных и математику. Задачи можно решать на большинстве популярных языков: C++/#, Java, PHP, Python, JavaScript, Kotlin и другие. Еще Hackerrank выпускает ежегодные исследования на тему востребованных технологий и образования в программировании.

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

Codebattle — проект сообщества Хекслета. Название говорит за себя: вам и сопернику даётся задача, выбираете язык и решаете. Вы видите код соперника в реальном времени, результаты запуска тестов и можете общаться с ним и зрителями в чате. Кто первый решит задачу (пройдёт тесты) — тот победил.

Еще известные сервисы:

Kaggle. Платформа для дата-саентистов и специалистов по машинному обучению. Предлагает открытые датасеты и контесты от компаний с призовыми фондами.

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

Поделитесь в комментариях какими платформами-задачниками вы пользуетесь и чем они нравятся. Интересные сервисы добавим в этот пост.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

Прохожу курсы по программированию (Python) на Stepik, если кто проходил, то начиная со второго модуля задачи очень сложные, решаю очень долго в 15-20 а то и более строк, можете посоветовать какую либо литературу для решения задач по программированию (чтобы руку набить + логику развить), или ссылки на какие либо еще курсы.

P.S. Далее я намерен пройти курсы по углубленному Python, по алгоритмам и структуры данных, дискретная матем и теор вер, оттуда в машинное обучение, все это безумно интересно(и сложно), учусь на 1 курсе, с выш матом проблем пока нет. Может посоветуете что нибудь еще (ссылки, или доп. курсы еще какие нибудь)

Не нужно учиться решать бредовые задачи!

Нужно учиться:
1. Понимать последовательность шагов/действий для получения ожидаемого результата реальной задачи.
2. Применять оптимизацию к найденному алгоритму, используя википедию и/или любые другие источники с открытыми алгоритмами, методами, способами.
3. К найденной оптимизации применить оптимальные функции из выбранного инструмента разработки (языка программирования).
(только здесь мы начинаем писать код!)
4. Оптимизировать производительность полученного кода (рефакторинг).

Источник

Как решать задачи на программирование

Перевод статьи «How to Solve Coding Problems with a Simple Four Step Method».

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

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

То, что я нашла, было не просто подходом, а бесценной стратегией. Это был проверенный временем алгоритм действий в четыре шага, который по какой-то причине остался незамеченным в сфере разработки.

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

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

Универсальный подход к решению задач

Этот метод изложен в книге «Как решать задачу» Дьёрдя Пойа. Первое издание вышло еще в 1945 году, было продано больше миллиона экземпляров. (На русском языке книга публиковалась как пособие для учителей еще в 1959 году. — Прим. перев.).

Метод Пойа используют многие программисты, от профессоров информатики (см. курс «Intro to CS» на Udacity, который ведет профессор Дэвид Эванс) до преподавателей современной веб-разработки вроде Кольта Стила.

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

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

Вот четыре шага по решению любой задачи:

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

Давайте сделаем первый шаг.

Шаг 1: понять задачу

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

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

Прочтите текст задачи. Можно даже читать вслух, если это поможет вам притормозить.

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

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

Чтобы помочь себе разобраться, спросите себя:

Каковы здесь входящие данные?

Какого рода input-ы следует ожидать? В нашем примере это аргументы, принимаемые функцией.

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

Эти вопросы мы можем задать интервьюеру или поискать ответ в описании задачи. (К задаче может прилагаться примечание типа «Исходите из того, что в функцию всегда будут передаваться только два числа». Конечно, это сразу все прояснит).

Можно задаться и другими вопросами. Всегда ли входящими данными будут числа? Что должна делать функция, если получит в качестве аргументов «a» и «b»? Уточните, всегда ли input будет числовым.

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

Далее следует спросить себя:

Каковы должны быть результаты?

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

Придумайте простые примеры

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

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

Начните с написания одного-двух простых примеров.

Давайте вернемся к нашей складывающей функции. Назовем ее «add».

Каким может быть input? Ну, допустим, таким:

Каким будет результат при таких входящих данных? Записать это можно так:

Это показывает, что наша функция принимает в качестве input 2 и 3, а как output возвращает 5.

Придумайте сложные примеры

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

Например, что будет, если наши входящие данные будут не числами, а строками? Что, если мы получим в качестве аргументов две строки, например, add(‘a’, ‘b’)?

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

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

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

Например, в задаче может говориться «При отсутствии input-а верните undefined». В таком случае можно написать комментарий:

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

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

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

Шаг 2: разработать план решения задачи

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

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

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

Теперь у вас есть четырехэтапный план решения задачи.

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

3. Шаг 3: осуществить план (решить задачу!)

Следующий шаг — собственно решение задачи. Руководствуясь псевдокодом, напишите настоящий код.

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

Если взять наш псевдокод, мы можем написать следующее:

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

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

Шаг 4: оглянуться назад

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

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

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

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

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

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

Итоги

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

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

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

Источник