Структуры данных, алгоритмы и умение решать проблемы: улучшаем свои навыки

0
2675
views

Перевод статьи «How to improve your data structures, algorithms, and problem-solving skills».

Структуры данных и алгоритмы
Source: Arafat Khan

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

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

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

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

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

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

Различные типы вопросов

Вот пример вопроса по структурам данных:

«Опишите, как бы вы вставили узел в связный список, и укажите временную сложность».

А вот по алгоритмам:

«Поиск элемента в перевернутом отсортированном массиве с указанием временной сложности».

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

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

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

Для практики я пользовался главным образом тремя сайтами: HackerRank, LeetCode и Kattis. Они имеют много общего, особенно первые два, однако не совсем идентичны. Я обнаружил, что у каждого сайта немного отличается фокус, и все они очень полезны, но каждый по-своему.

Навыки, необходимые для нахождения ответов на указанные выше вопросы, я бы разбил на три категории:

  1. Знание структур данных.
  2. Знание алгоритмов.
  3. Умение применять структуры данных и алгоритмы.

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

Знание структур данных

Двоичное дерево поиска

В этом плане я нахожу особенно полезным HackerRank. На этом сайте есть раздел, посвященный структурам данных. Там можно использовать фильтр по типам (массивы, связные списки, деревья, кучи и т. п.).

Вопросы на знание структур данных касаются не столько решения проблем, сколько умения работать со структурами данных. Например:

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

На 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 для визуальных объяснений.

Заключение

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

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here