Инсайдерское руководство по вопросам на собеседовании по алгоритму

Что такое алгоритмические парадигмы?

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

Они часто проверяются на собеседованиях, поэтому стоит потратить дополнительное время на их рассмотрение.

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

Например: Отслеживание с возвратом

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

Какие алгоритмы мне следует знать во время собеседования?

• Грубая сила — это Метод требует, чтобы мы использовали все возможности, чтобы найти решение проблемы, которую мы собираемся решить. Часто в первую очередь приходит на ум именно этот алгоритм, и даже если он наименее эффективен, решение вам гарантировано.
• Жадные алгоритмы — алгоритмическая парадигма, которая строит решение по частям, то есть выбирает следующую часть, которая предлагает наиболее очевидную и немедленную выгоду.

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

• Разделяй и властвуй — шаблон, который разбивает проблему на более мелкие подзадачи, которые затем рекурсивно решаются и, наконец, собираются заново. Часто используется для операций сортировки.
• Алгоритмы сортировки и поиска — сортировка слиянием, быстрая сортировка, сортировка по выбору, пузырьковая сортировка, сортировка вставкой
• Алгоритмы построения графиков — обход графа в ширину, обход по графу в глубину

Измерение эффективности

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

Сложность — это приблизительная мера эффективности алгоритма, связанная с с каждым написанным вами алгоритмом . Это то, о чем все программисты должны постоянно помнить.

Есть два вида сложностей: время и пространство. Сложность времени и сложность пространства — это, по сути, приближения того, сколько времени и сколько места потребуется алгоритму для обработки определенных входных данных соответственно.

Как правило, есть три уровня, которые нужно решить:

• В лучшем случае — представлен как Big Omega или Ω ( n ) (n) (n)
• Среднее case — представлен как Big Theta или Θ ( n ) (n) (n)
• Худший случай — представлен как нотация Big O или O ( n ) O (n) O (n)

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

Сложность Big O

Если на собеседовании вас просят найти Big O сложность алгоритма здесь — это общее практическое правило:

• Отбросьте ведущие константы
• Игнорируйте члены более низкого порядка

Пример: найти сложность Big O алгоритма с временной сложностью 3 n 3 + 4 n + 2 3n ^ 3 + 4n + 2 3n 3 + 4n + 2

Это упрощается до O ( n 3 ) O (n ^ 3) O (n 3).

Как вычислить сложность без заданного уравнения

При вычислении временной сложности алгоритма вам нужно сделать три шага:

• Перечислить вниз все основные операции в коде
• Подсчитайте количество выполнений каждого из них
• Суммируйте все подсчеты, чтобы получить уравнение

Вот простой пример, который измеряет временную сложность цикл for размером n .

Вот цикл размером n:

 #include  using namespace std;  int main () {int n = 10; //0 (1) int sum = 0; //0 (1) for (int i = 0; i  
 
     
 
  

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

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

Сложность времени =

1 + 1 + 1 + ( n + 1 ) + n + n + 1 = 3 + ( n + 1 ) + 2 n + 1 = > 3 n + 5 1 + 1 + 1 + (n + 1) + n + n + 1 = 3 + (n + 1) + 2n + 1 => 3n + 5 1 + 1 + 1 + (n + 1) + n + n + 1 = 3 + (n + 1) + 2n + 1 => 3n + 5

Общие советы по асимптотическому анализу:

• Каждый раз, когда список или массив повторяется на протяжении x раз, это, скорее всего, в семантике O ( n ) O(n) O (n) time.
• Когда вы видите проблему, где число Количество элементов в проблемном пространстве каждый раз уменьшается вдвое, скорее всего, оно будет в O ( l o g n ) O (logn) O (logn) runtime.
• Всякий раз, когда у вас есть одиночно вложенный цикл , проблема, скорее всего, заключается в квадратичном времени.

Полезные формулы для расчета временной сложности алгоритма:

Примеры задач

• Асимптотический анализ: Вычислите сложность Big O фрагмента кода, приведенного ниже.

 int main () {int n =  10;  int sum = 0;  float pie = 3,14;  для (int i = 1; i  
 
     
 
 

• Алгоритмы сортировки и поиска: Реализуйте функцию, которая берет два отсортированных массива переменной длины и находит медиану этих двух массивов.

• Алгоритмы построения графиков: Реализуйте функцию, которая возвращает количество узлов на заданном уровне неориентированного графа.

• Жадные алгоритмы: дано бесконечное количество четвертей (25 центов), десятицентовиков (10 центов), пятак (5 центов). центов) и пенни (1 цент), реализуйте функцию для вычисления количества МОНЕТ для представления V центов.

• Алгоритмы динамического программирования : ребенок поднимается по лестнице с n шагами и может перепрыгнуть либо на 1 шаг, либо на 2 шагов или 3 шага за раз. Реализуйте функцию для подсчета количества возможных способов, которыми ребенок может подняться по лестнице.

• Алгоритмы разделения и подчинения : Учитывая двумерный массив из k строк и 4 отсортированных столбца и пустой одномерный выходной массив размером k * n , скопируйте все элементы из k отсортированных массивов в выходной массив k * n с использованием подхода «разделяй и властвуй».

Следующие шаги

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

Лучшее, что вы можете сделать для подготовки, — это попрактиковаться в реализации и вычислении сложность каждой из упомянутых выше алгоритмических парадигм.

Практика — лучший способ закрепить ваши знания алгоритмов. В новом курсе «Алгоритмы для собеседований по программированию на C ++ » от Educative подробно рассматриваются темы, затронутые в этом посте, а также предлагаются реальные задачи и викторины для проверки вашего понимания.

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

Читать далее о подготовке к собеседованию

• Инсайдерское руководство по вопросам рекурсии на собеседовании

• Нотация Big O: учебник для начинающих разработчиков

• Подготовка к собеседованию по Java: 15 вопросов к собеседованию по Java

• Онлайн-курс: Проведение собеседования по программированию