цифровая электроника
вычислительная техника
встраиваемые системы

 
» » Про какие алгоритмы часто спрашивают на собеседованиях по программированию

Про какие алгоритмы часто спрашивают на собеседованиях по программированию

Автор: Mike(admin) от 26-09-2019, 06:55

Алгоритмы, которые должен знать каждый программист


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


Про какие алгоритмы часто спрашивают на собеседованиях по программированию

Алгоритмы обхода дерева


Это алгоритмы, которые позволяют вам обходить каждый узел дерева в структурированном порядке. Они в первую очередь предназначены для двоичных деревьев, но вы можете адаптировать эти концепции для обхода всех узлов любого дерева. Изучение этих алгоритмов также поможет вам понять, как рекурсивно обходить все узлы в дереве.


Три алгоритма, на которых вы должны сосредоточиться – это обход дерева с посещением каждого узла перед посещением узлов-потомков (Pre-Order), симметричный обход (In-Order) и обход дерева с посещением каждого узла после посещения узлов-потомков (Post-Order). Каждый из них отличается в порядке, в котором они посещают узлы дерева. Рекомендуется понять порядок, в котором они посещают значения в двоичном дереве поиска.


Алгоритмы поиска графа


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


Алгоритмы в этом классе - поиск в глубину (DFS), поиск в ширину (BFS) и алгоритм Дейкстры. Если у вас есть дополнительное время, рекомендуем вам также изучить алгоритм A*.


Алгоритмы поиска


Это класс алгоритмов, который на самом деле имеет только один важный алгоритм: бинарный поиск. Традиционный поиск – это алгоритм сложности O(n), поскольку вы посещаете каждый элемент по одному. Если у вас есть отсортированный список ввода, вы можете использовать двоичный поиск для времени выполнения O(log (n)). Соискателей часто просят реализовать бинарный поиск как часть решений для вопросов на собеседовании, поэтому мы настоятельно рекомендуем знать этот алгоритм.


Алгоритмы сортировки


Сортировка методом пузырька, сортировка методом вставки, сортировка по выбору и т. д. Все это стандартные алгоритмы, которые вы должны понимать и уметь реализовывать, но это сложность O(n²) для алгоритмов среднего случая. Наиболее важными алгоритмами сортировки для интервью являются алгоритмы O(n * log (n)). Два наиболее распространенных алгоритма в этом классе – сортировка слиянием и быстрая сортировка. Важно, чтобы вы знали по крайней мере один из них и предпочтительно оба. Мы рекомендуем начинать с сортировки слиянием, потому что она имеет временную сложность наихудшего случая O(n * log (n)), тогда как быстрая сортировка снижается до сложности O(n²) при наихудшем случае.




© digitrode.ru




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

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

Оставить комментарий