Перевод статьи «How to improve your data structures, algorithms, and problem-solving skills».
В этом посте отражен мой собственный опыт. Я приступил к своему последнему семестру, не имея практически никаких знаний по структурам данных и алгоритмам, а также не умея решать задачи. Как программисту-самоучке мне были более знакомы такие идеи как объектно-ориентированное программирование. Однако для решения задач по структурам данных и алгоритмам требовались навыки решения проблем.
Здесь я рассмотрю ресурсы, которые помогли мне приобрести нужные знания и навыки.
Проблема: вы знаете теорию, однако не умеете применять ее на практике
С этой проблемой я столкнулся на раннем этапе, причем в условиях, когда я не знал, чего именно я не знаю, и это было особенно плохо.
Я довольно хорошо понимал теорию. Например, я знал, что такое связный список, как он работает, какие списки бывают и какова их временная сложность, какие абстрактные типы данных они поддерживают и как реализовываются операции с ними.
Но поскольку я не знал, чего именно я не знаю, я не мог научиться применять все эти знания для решения проблем.
Различные типы вопросов
Вот пример вопроса по структурам данных:
«Опишите, как бы вы вставили узел в связный список, и укажите временную сложность».
А вот по алгоритмам:
«Поиск элемента в перевернутом отсортированном массиве с указанием временной сложности».
Наконец, вопрос по решению проблем, который я считаю вопросом более «высокого уровня», чем два предыдущих. Такой вопрос может кратко описывать сценарий и список требований проблемы.
На экзамене вас могут попросить описать решение. А на соревнованиях по программированию от вас может требоваться сдать рабочий код, причем вы не получите указаний использовать какие-то определенные структуры данных или алгоритмы. Другими словами, от вас ждут, что вы примените наиболее подходящие из них, обеспечивающие максимально эффективное решение проблемы.
Как улучшить навыки применения структур данных, алгоритмов, а также навыки решения проблем?
Для практики я пользовался главным образом тремя сайтами: HackerRank, LeetCode и Kattis. Они имеют много общего, особенно первые два, однако не совсем идентичны. Я обнаружил, что у каждого сайта немного отличается фокус, и все они очень полезны, но каждый по-своему.
Навыки, необходимые для нахождения ответов на указанные выше вопросы, я бы разбил на три категории:
- Знание структур данных.
- Знание алгоритмов.
- Умение применять структуры данных и алгоритмы.
Первые две группы можно считать «примитивами» или строительными блоками, нужными для успеха в третьей категории.
Знание структур данных
В этом плане я нахожу особенно полезным HackerRank. На этом сайте есть раздел, посвященный структурам данных. Там можно использовать фильтр по типам (массивы, связные списки, деревья, кучи и т. п.).
Вопросы на знание структур данных касаются не столько решения проблем, сколько умения работать со структурами данных. Например:
- Массивы: поворот массива (array rotation), манипуляции с массивами (array manipulation)
- Связные списки: разворот связного списка (reversing a linked list), определение зацикленности (cycle detection)
- Деревья: замена узлов (node swapping), проверка двоичного дерева поиска (BST validation)
Вы поняли принцип. Некоторые вопросы могут даже никогда не применяться напрямую в решении проблем. Но они важны для понимания концепции в целом, а это имеет большое значение.
На HackerRank нет «моделей решения» в свободном доступе, однако в разделе обсуждения обычно полно подсказок, зацепок и даже отрывков рабочего кода. Я до сих пор находил эти отрывки полезными, хотя поначалу вам, возможно, придется разбирать их построчно в своей IDE.
Знание алгоритмов
На HackerRank есть также и раздел с алгоритмами, но по этой теме я предпочитаю пользоваться LeetCode. Я считаю, что на этом сайте куда шире набор проблем. Кроме того, мне очень нравится, что многие проблемы имеют решение с объяснением и даже временными сложностями.
Хорошим стартом будет раздел top 100 liked questions на LeetCode. Вот некоторые из вопросов, которые мне особенно понравились:
- Слияние аккаунтов
- Самая длинная непрерывно возрастающая подпоследовательность
- Поиск в повернутом отсортированном массиве
В отличие от вопросов по структурам данных, здесь фокус скорее не на том, как это работает, и не на манипуляциях со структурами данных, а на том, как что-то сделать.
Например, задача со слиянием аккаунтов это прежде всего применение стандартных алгоритмов UFDS (union–find data structure, русск. «система непересекающихся множеств»). «Поиск в повернутом отсортированном массиве» представляет собой измененный двоичный поиск.
Порой случается изучить и совершенно новую технику решения проблем. Например, решение «раздвижное окно» («sliding window») для задачи «Самая длинная непрерывно возрастающая подпоследовательность».
Умение применять структуры данных и алгоритмы
Наконец, для улучшения навыков решения проблем в целом, я пользуюсь Kattis. Архив задач Kattis содержит множество проблем из различных источников, например, с соревнований по программированию, проходивших по всему миру.
Kattis может порой разочаровывать, поскольку там нет официальных решений или форума для обсуждений (в отличие от HackerRank и LeetCode). Кроме того, там скрыты test cases. У меня есть несколько проблем с Kattis, которые я никак не могу решить не потому, что не знаю решения, а потому что не могу найти баг.
Этот сайт мне нравится меньше других, так что я там провожу меньше всего времени.
Другие ресурсы
Еще одним очень ценным ресурсом для изучения структур данных и алгоритмов является Geeksforgeeks. Мне он нравится тем, что там даются отрывки кода на разных языках, обычно на C++, Java и Python. Их можно скопировать и вставить в своей IDE, чтобы проследить решение построчно.
Наконец, есть старый добрый Google, который чаще всего приводит вас к GeeksForGeeks, и Youtube для визуальных объяснений.
Заключение
В заключение могу сказать, что, к сожалению, нет никакой возможности «срезать» путь. Вы должны просто погрузиться с головой в эти темы. Начать писать код, заниматься его отладкой, читать правильный код других людей, чтобы понять, где, как и почему сами свернули не туда. Это сложно, но с каждой новой попыткой ваши навыки будут расти, а по мере их роста все станет проще.
[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]
