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



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

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

    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.

    Заключение


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


    Skillbox
    260,00
    Онлайн-университет профессий будущего
    Поделиться публикацией

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

      +2

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

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

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

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

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

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое