От переводчика: сегодня публикуем для вас статью Фабиана Терха. Статья в первую очередь будет полезна для начинающих программистов.

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

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.

Заключение


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


Комментарии (6)


  1. rumkin
    11.01.2019 19:45
    +2

    Ссылка на оригинал. Флаг что это перевод. Новый контент-менеджер впервые на Хабре?


  1. gorodnev
    11.01.2019 21:00

    найдите элемент в повернутом отсортированном массиве и определите time complexity.

    Перечитал раз пять, но смысла не прибавилось. Что хотел сказать автор?


    1. rafuck
      11.01.2019 21:11

      Думаю, имеется в виду изначально отсортированный и циклически сдвинутый массив.
      www.hackerrank.com/challenges/array-left-rotation/problem


      1. gorodnev
        12.01.2019 00:37

        Да, верно. Именно это и имелось в виду. В оригинале и ссылка на задачу нашлась.


    1. MikailBag
      11.01.2019 23:14

      Или, возможно, reversed.


    1. maximw
      11.01.2019 23:18
      +1

      Потому что весь смысл статьи в предложении, начинающемся со слов «Skillbox рекомендует». Без этого вообще нет смысла переводить такую фигню.