От переводчика: сегодня публикуем для вас статью Фабиана Терха. Статья в первую очередь будет полезна для начинающих программистов.
Я программист-самоучка, этот пост отражает мой личный опыт и навыки в такой сфере, как алгоритмы и структуры данных; кроме того, я рассказываю и о способах решения задач (к слову, второе мне дается несколько хуже, чем первое).
Skillbox рекомендует: двухлетний практический курс «Я — веб-разработчик PRO».
Напоминаем: для всех читателей «Хабра» — скидка 10 000 рублей при записи на любой курс Skillbox по промокоду «Хабр».
Проблема: вы знаете теорию, но у вас трудности с практикой
Не так давно у меня возникла проблема, которую можно описать как «я не знаю, чего я не знаю» — можно сказать, курьез. Дело в том, что я понимаю теорию, причем весьма неплохо. Я знаю, как работают списки, что представляют собой отдельные операции, что такое абстрактные типы данных и т.п.
Но проблема в том, что я не знаю, какая информация мне может пригодиться на практике, и не представляю, чего может не хватать для реализации некоторых задач. А значит, мне приходится сложно тогда, когда нужно решать какие-то проблемы.
Типы задач, которые могут встретиться
Пример вопроса о структурах данных: опишите, как бы вы вставили узел в связный список, и укажите time complexity.
Вот вопрос по алгоритмам: найдите элемент в повернутом отсортированном массиве и определите time complexity.
Наконец, последний вопрос, более высокого «уровня», чем предыдущие, — просьба описать способ решения задачи и перечисление требований к ее выполнению.
В ходе работы вам может потребоваться именно это, т.е. описание решения. В конкурентном программировании часто нужно предоставить рабочий код без явного указания каких-либо структур данных или алгоритмов. Другими словами, от вас ожидают, что вы сможете использовать оптимальные в каждом конкретном случае структуры данных и алгоритмы для максимально эффективного решения проблемы.
Как я могу улучшить свои навыки?
Лично я использовал для этого три ресурса: HackerRank, LeetCode и Kattis. Они похожи друг на друга, особенно первые два, но не идентичны.
Я бы разделил скиллы, которые нужны для решения проблем, на три группы:
- знание структур данных;
- знание алгоритмов;
- умение применять структуры данных и алгоритмы.
Первые две категории являются основными, они лежат в самом низу. Третья категория более высокого класса.
Знание структур данных
Здесь мне больше всего пригодился HackerRank. В нем есть секция, посвященная структурам данных, где информацию можно фильтровать по типам, включая деревья, связные списки, массивы и т.п.
Вопросы, которые рассматриваются на HackerRank, в основном имеют отношение к работе со структурами данных:
- Массивы: вращение массива и выполнение с ним иных действий.
- Связные списки: reversing, cycle detection.
- Деревья: node swapping, BST validation.
Вероятно, вы уже поняли, в чем дело. Поданные ресурсом вопросы не могут использоваться непосредственно при решении проблем. Но они нужны для понимания основ, что было чрезвычайно важно в моем случае.
У HackerRank нет общедоступных «моделей решений», хотя в разделе обсуждений можно найти много советов, подсказок и даже фрагментов рабочего кода. Мне все это очень помогло.
Знание алгоритмов
У HackerRank есть раздел с алгоритмами, хотя мне ближе подача информации у LeetCode. Мне кажется, что на втором ресурсе список рассматриваемых проблем гораздо шире, и есть разъяснения и советы.
Лучше всего начать со 100 наиболее распространенных вопросов (этот раздел есть на LeetCode). Некоторые мне очень пригодились:
- слияние учетных записей;
- самая большая непрерывно возрастающая подпоследовательность;
- поиск в повернутом отсортированном массиве.
В отличие от вопросов, связанных со структурами данных, здесь основное внимание уделяется тому, как что-то сделать. Например, проблема слияния учетных записей главным образом связана с применением стандартных алгоритмов UFDS. Проблема поиска в повернутом отсортированном массиве представляет собой поворот в бинарном поиске. Порой удается найти качественно новые методы решения проблем — например, метод «скользящего окна» для задачи на самую длинную непрерывную возрастающую подпоследовательность».
Умение применять структуры данных и алгоритмы
Ну а этот скилл я прокачивал уже при помощи ресурса Kattis. Здесь есть огромный архив решенных проблем, где собраны данные из различных источников, включая соревнования программистов со всего мира.
К сожалению, у Kattis нет форума, плюс кейсы являются частными, а не общими случаями. Поэтому есть несколько проблем, которые у меня не получилось решить с его помощью.
Тем не менее ресурс может помочь многим программистам. Сам я провел за его изучением не слишком много времени.
Другие ресурсы
Geeksforgeeks — еще один ценный ресурс для изучения алгоритмов и структур данных. Мне нравится, что он предоставляет сниппеты на различных языках, включая C++, Java и Python. Вы можете использовать их без всяких проблем.
И, конечно, есть старые добрые Google с YouTube.
Заключение
Собственно, главное — это писать код, заниматься отладкой, изучать код других разработчиков, что поможет быстрее разобраться с вашими текущими задачами. Решать проблемы тяжело, но с каждой попыткой, с каждым решенным вопросом у вас будет получаться все лучше и лучше.
- Онлайн-курс «Профессия frontend-разработчик»
- Практический курс «Мобильный разработчик PRO».
- Практический годовой курс «PHP-разработчик с нуля до PRO».
Автор: skillbox
