Зачем разработчику знать алгоритмы и структуры данных?

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

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

Алгоритмы в реальной жизни

Знание алгоритмов и тесно связанной с ними организации структуры данных необходимо для серьезной работы в любой отрасли информатики:

1. Протоколы маршрутизации в коммуникационных сетях используют классические алгоритмы поиска кратчайшего пути.
2. Шифрование с открытым ключом опирается на эффективные теоретико-числовые алгоритмы.
3. Компьютерная графика задействует вычислительные примитивы, которые предоставляют геометрические алгоритмы.
4. Индексация в базах данных опирается на структуры данных сбалансированных деревьев поиска.
5. Вычислительная биология использует алгоритмы динамического программирования для измерения сходства геномов.

И так можно продолжать бесконечно.

Что дает знание алгоритмов рядовому разработчику

Освоение алгоритмов требует времени и усилий, но при этом дает несколько серьезных преимуществ:

• Повышение эффективности. Существуют максимально быстрые алгоритмы для обработки данных и эффективные структуры для их организации. Такие паттерны избавляют от необходимости изобретать велосипед при решении типовых задач, позволяют прогнозировать производительность ПО и служат основой для разработки новых нетривиальных решений.
• Развитие аналитических способностей и алгоритмического мышления. Изучение и реализация алгоритмов улучшают не только навыки программирования: привычка разбивать сложные задачи на логически связанные шаги, необходимые для их эффективного решения, пригодится везде – от планирования отпуска до разработки инвестиционной стратегии.
• Успехи в спортивном программировании. Знание алгоритмов необходимо для успешного решения задач в контестах: как правило, из любого олимпиадного задания торчат уши какого-нибудь алгоритма. Вот всего лишь один пример: известная задача «Поле чудес» (Periodic Strings в англоязычном варианте) элементарно решается с помощью алгоритма Кнута-Морриса-Пратта. Стоит заметить, что олимпиадные задачи часто предлагают кандидатам на техническом собеседовании.
• Успешное прохождение собеседований. Чем сложнее задачи, которые предстоит решать разработчикам компании, тем выше вероятность, что значительная часть вопросов будет посвящена алгоритмам и структурам данных. Работодатели отдают предпочтение кандидатам, которые способны найти самое эффективное и эргономичное решение проблемы.
• Знакомство с величайшими достижениями информатики. Изучение алгоритмов и структуры данных похоже на просмотр дайджеста, состоящего из суперхитов информатики за последние 70 лет. В следующий раз, когда коллега пришлет мем про Дейкстру и его путь к подруге, будешь знать, в каком месте надо смеяться.

С чего начать изучение алгоритмов

Существует множество алгоритмов и немало структур данных. Некоторые из них можно назвать универсальными или общими, другие – узкоспециальными, предназначенными для решения специфических задач: очевидно, что в вычислительной геометрии и в биоинформатике проблемы будут разными. Без какой-либо базы (в виде университетского курса или опыта участия в олимпиадах по программированию) разобраться во всем этом довольно сложно. В этом случае важно начать с азов и базовых концепций, к которым относятся:

1. Асимптотический анализ сложности алгоритмов. Лучший, средний и худший случаи. «O» большое и «o» малое. Очень часто на собеседованиях предлагают оценить сложность алгоритма или обосновать выбор в пользу определенного решения.
2. Линейные структуры данных – массивы, стеки, связанные списки, хэш-таблицы и очереди.
3. Нелинейные структуры данных – деревья, графы, множества.
4. Рекурсия. Значительная часть алгоритмов использует рекурсию; она неразрывно связана с рекурсивно определяемыми структурами данных – деревьями, – и восходящим / нисходящим динамическим программированием.
5. Концепция «разделяй и властвуй» и алгоритмы, основанные на ней – бинарный поиск, сортировка слиянием, быстрая сортировка, сортировка подсчетом, умножение Карацубы, субкубический алгоритм Штрассена, задача о паре ближайших точек. Такие алгоритмы разбивают исходную задачу на более мелкие подзадачи, рекурсивно решают их, а затем объединяют решения подзадач в решение исходной задачи.

После знакомства с азами пора переходить к темам, которые всплывают на большинстве собеседований: поиск и сортировка, жадные алгоритмы, графы (поиск в ширину и в глубину), динамическое программирование. Абсолютный минимум, который необходим для подготовки к техническому собеседованию, доступно и интересно изложен в книге Томаса Х. Кормена «Алгоритмы. Вводный курс». Исчерпывающий вариант – четырехтомник Тима Рафгардена «Совершенный алгоритм»:

• в первой книге рассматриваются азы и базовые концепции;
• во второй – графовые алгоритмы и структуры данных;
• в третьей – жадные алгоритмы и динамическое программирование;
• в четвертой – алгоритмы для NP трудных задач.

Материалы четырехтомника основаны на лекциях, которые Рафгарден читал в Стэнфордском университете и на онлайн-курсах, которые он ведет сейчас. Книги написаны вполне доступным языком и содержат множество практических заданий и тестов с решениями.

Алгоритмическая секция

Особенности технического собеседования варьируются в различных компаниях, но общие моменты выделить можно:

• Кандидатам предлагают решить 5-6 задач разной степени сложности. На задачу можно потратить 15-45 минут – это очень мало. Поэтому с первого дня изучения алгоритмов нужно привыкать решать задачи – не только правильно, но и максимально быстро.
• Часто решение приходится писать от руки – на листе бумаги или на доске. Так интервьюеру проще оценить, насколько последовательно и структурированно складывается решение в голове кандидата – чем меньше зачеркиваний и стираний, тем лучше.
• При решении задач в IDE действуют лимиты по времени и памяти, как и в контестах спортивного программирования. Чтобы уложиться в лимиты, нужно учитывать не только быстродействие выбранного алгоритма, но и мелочи вроде небрежного считывания всех данных из огромного файла целиком (вместо одной нужной строчки).

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

Источник: m.vk.com

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