Как вы подходите к решению проблем структур данных и алгоритмов?

Question

У меня были проблемы с поиском лучших решений вопросов о структурах данных и алгоритмах, задаваемых интервьюерами. Мне было интересно, как вы, ребята, подходите к этим проблемам. Это просто практика решения всех видов проблем, чтобы получить опыт, или у вас, ребята, есть систематические способы распознать определенные типы проблем? Можете ли вы порекомендовать книги, которые могут мне помочь? Я перечитал много Введение в алгоритмы от CLRS, и я уверен, что смогу освежить в памяти фундаментальные концепции CS.

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

Спасибо за чтение.

Answer 1

Я не уверен, что SO - лучшее место для этого вопроса, но я рекомендую вам «Взломать интервью по кодированию» Гейл Лакманн МакДауэлл.

Классические книги об алгоритмах в порядке, но они сосредоточены на большемфундаментальные и "академические" вещи. ТПП ориентирована специально на решение вопросов интервью.

Answer 2

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

1. «что нужно сделать в этой проблеме»:то есть глава о сортировке, глава о поиске, деревья, кучи. Например, "Алгоритмы" Роберта Седжвика, "Введение в алгоритмы" Томаса Кормена.

и

«как спроектировать алгоритм для решения этой проблемы»: то есть «разделяй и властвуй», «ветвь и связывай», жадный подход. Например, «Основы алгоритмов» Ричарда Э. Неаполитана и в определенной степени «Алгоритмы с подсветкой» Тима Рафгардена

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

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

Еще одна хорошая книга, которая может оказаться полезной, - "Руководство по разработке алгоритмовСтивен Скиена . Это гибрид двух подходов, но он содержит множество реальных анекдотов и «военных историй».