Эта статья была написана Аароном Се и первоначально опубликована на Образование, Инк.
Многие содрогаются при мысли об интервью по кодированию. Это может быть напряженным, изнурительным и сложным занятием. Часто бывает непросто просто знать, какие темы готовить. Однако сегодня вы познакомитесь с основными структурами данных и алгоритмами, которые тестируются на собеседовании по кодированию. Прочитав эту статью, вы должны иметь хорошее представление о том, к чему вам нужно подготовиться, чтобы получить работу своей мечты.
Мы рассмотрим следующее:
- Почему вы должны изучать структуры данных и алгоритмы?
- Понимание обозначения Big O
- Важные структуры данных для изучения
- Важные алгоритмы для изучения
- Другие темы для обсуждения
- Как пройти ваше следующее собеседование по программированию
- Ресурсы
Почему вы должны изучать структуры данных и алгоритмы?
Собеседование по кодированию проверяет ваши способности к решению проблем и понимание концепций информатики. Обычно вам дается от 30 до 45 минут на решение одной сложной проблемы, но иногда вам будет предложено решить несколько более простых технических задач.
Вот тут-то и пригодятся структуры данных и алгоритмы . Эти собеседования проверят вас по таким темам, как связанные списки, очереди, сортировка, поиск и многое другое, поэтому очень важно подготовиться. Компании хотят не только проверить ваши технические знания, но и оценить ваши навыки решения проблем. Если вы получите эту работу, вы часто будете сталкиваться с ошибками, которые вам необходимо исправить, и компании хотят убедиться, что вы сможете преодолеть эти препятствия. Кроме того, вы часто будете использовать определенные структуры данных и алгоритмы для оптимизации своего кода, чтобы он работал максимально эффективно.
Понимание обозначения Big O
Обозначение Big O – это асимптотический анализ, который описывает, сколько времени требуется для выполнения алгоритма. Другими словами, он используется для обсуждения того, насколько эффективен или сложен алгоритм.
Большой O описывает время выполнения или время выполнения алгоритма относительно его входных данных $N$ по мере увеличения входных данных. Хотя мы можем анализировать эффективность алгоритма, используя средний и наилучший варианты, мы обычно используем наихудший вариант с обозначением Big O.
Сегодня вы узнаете о временной сложности, но обратите внимание, что пространственная сложность также является важной концепцией для понимания. Сложность выполнения может быть трудной концепцией для понимания на первый взгляд, поэтому давайте рассмотрим некоторые примеры
$O(1)$
public int findInt(int[] arr) {
return arr[0];
}
$O(1) $ описывает алгоритм, который всегда выполняется в постоянное время независимо от его ввода. Функция будет выполняться одновременно независимо от того, содержит ли массив тысячу целых чисел или одно целое число, потому что он занимает всего один “шаг”.
$O(N)$
public int func(int[] arr) {
for (int i = 1; i <= arr.length; i++) {
System.out.println(i);
}
}
$O(N)$ описывает алгоритм, время выполнения которого будет линейно увеличиваться относительно входного $N$. Приведенная выше функция выполнит $N$ шагов для $N$ значений, хранящихся в массиве. Например, если длина массива равна 1, для запуска функции потребуется 1 “шаг”, тогда как если длина массива равна 1000, для запуска функции потребуется 1000 “шагов”.
В приведенном примере длина массива – это размер входных данных, а количество итераций – время выполнения.
$O(N^2)$
public int func(int[] arr) {
for (int i = 1; i <= arr.length; i++) {
for (int i = 1; i <= arr.length; i++) {
System.out.println(i);
}
}
}
$O(N ^ 2)$ описывает функцию, время выполнения которой пропорционально квадрату входного размера. Эта среда выполнения возникает, когда существует вложенный цикл, так что внешний цикл выполняется $ N$ раз, а внутренний цикл выполняется $ N $ раз для каждой итерации внешнего цикла, так что функция выполняет $ N ^ 2$ шагов.
Некоторые правила, которые нужно запомнить
Игнорировать константы: При использовании обозначения Big O вы всегда отбрасываете константы. Таким образом, даже если сложность выполнения составляет $O(2N) $, мы называем это $O(N)$.
Отбросьте менее доминирующие термины: Вы сохраняете только самый доминирующий термин, когда говорите о Большом О. Например, $O(N ^ 3 + 50N + 17)$ – это просто $O(N ^ 3)$. Вот эмпирическое правило: $O(1) $ < $O(LOGN) $ < $O(N) $ < $O(NlogN) $ < $O(N ^ 2) $ < $O(2 ^ N) $ < $O(N!)$.
Хотите узнать больше о обозначении Big O? Ознакомьтесь с нашим Что такое обозначение Big-O статья.
Важные структуры данных для изучения
Проще говоря, структуры данных – это способы организации и хранения данных на компьютере таким образом, чтобы к ним можно было получить доступ и изменить. Вы изучите основы важных структур данных, которые тестируются на собеседовании по программированию.
Массивы
Массив представляет собой набор элементов одного и того же типа переменной, которые последовательно хранятся в памяти. Это одна из самых популярных и простых структур данных, которая часто используется для реализации других структур данных.
Каждый элемент в массиве индексируется, начиная с 0, и каждый элемент известен как элемент. Также важно отметить, что в Java вы не можете изменить размер массива. Для динамических размеров рекомендуется использовать список.
В приведенном выше примере:
Длина массива составляет 5
Значение в индексе 3 равно 1
В Java все значения в этом массиве должны быть целочисленного типа
Инициализация массива в Java:
int[] intArray = new int[14]; intArray[3] = 5; intArray[4] = 3; intArray[13] = 14; // Indexes with no value are null
Общие вопросы для интервью:
Найти первое неповторяющееся целое число в массиве
Переставить массив в порядке убывания
Вправо поверните массив на один индекс
Подмассив максимальной суммы с использованием разделяй и властвуй
Связанные списки
Связанный список представляет собой линейную последовательность узлов, связанных вместе. Каждый узел содержит значение и указатель на следующий узел в списке. В отличие от массивов, связанные списки не имеют индексов, поэтому вы должны начинать с первого узла и проходить через каждый узел, пока не доберетесь до $n$-го узла. В конце последний узел будет указывать на нулевое значение.
Первый узел называется головным , а последний узел называется хвостовым . Ниже представлен односвязный список.
Связанный список имеет ряд полезных приложений:
Реализовать стеки, очереди и хэш-таблицы
Создание каталогов
Полиномиальное представление и арифметические операции
Динамическое распределение памяти
Базовая реализация связанного списка в Java:
import java.io.*;
// Java program to implement
// a Singly Linked List
public class LinkedList {
Node head; // head of list
// Linked list Node.
// This inner class is made static
// so that main() can access it
static class Node {
int data;
Node next;
// Constructor
Node(int d)
{
data = d;
next = null;
}
}
// Method to insert a new node
public static LinkedList insert(LinkedList list, int data)
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;
// If the Linked List is empty,
// then make the new node as head
if (list.head == null) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
Node last = list.head;
while (last.next != null) {
last = last.next;
}
// Insert the new_node at last node
last.next = new_node;
}
// Return the list by head
return list;
}
// Method to print the LinkedList.
public static void printList(LinkedList list)
{
Node currNode = list.head;
System.out.print("LinkedList: ");
// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");
// Go to next node
currNode = currNode.next;
}
}
// Driver code
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
//
// ******INSERTION******
//
// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);
// Print the LinkedList
printList(list);
}
}
Общие вопросы для интервью:
Перевернуть связанный список
Найдите среднее значение в связанном списке
Удалить цикл в связанном списке
Стеки
Стеки представляют собой линейные структуры данных в порядке LIFO (последний вход, первый выход). Итак, что это значит? Представьте себе стопку тарелок. Последняя тарелка, которую вы кладете поверх стопки, – это первая, которую вы достаете. Стеки работают таким образом: последнее значение, которое вы добавляете, является первым, которое вы удаляете.
Думайте о стеке как о наборе элементов, которые мы можем добавлять и удалять. Наиболее распространенными функциями в стеке являются push, pop, isEmpty и peek.
Стек имеет ряд полезных применений:
Возврат к предыдущему состоянию
Оценка и преобразование выражений
Общие вопросы для интервью:
Используйте стек для проверки сбалансированных скобок
Реализовать два стека в массиве
Следующий больший элемент, использующий стек
Очереди
Очереди очень похожи на стеки в том, что они оба являются линейными структурами данных с динамическим размером. Однако очереди представляют собой структуры данных FIFO (первый вход, первый выход). Чтобы визуализировать эту структуру данных, представьте, что вы выстраиваетесь в очередь на американские горки. Первые люди, которые выстраиваются в очередь, выходят из очереди, чтобы прокатиться.
В этой структуре данных элементы входят “сзади” и выходят “спереди”. Стандартными функциями в очереди являются постановка в очередь, снятие с очереди, задняя, передняя и заполнена.
Очередь имеет ряд полезных приложений:
Когда ресурс совместно используется несколькими потребителями
Создание каталогов
Когда данные передаются асинхронно между двумя ресурсами
Общие вопросы для интервью:
Обратить вспять первые k-е элементы очереди
Генерировать двоичные числа от 1 до n с помощью очереди
Графики
Граф представляет собой набор вершин (узлов), которые соединены ребрами, создавая сеть.
В приведенном выше примере набор вершин равен (12, 2, 4, 18, 23) и края такие (12-2, 12-4, 2-4, 4-18, 4-23, 18-23, 2-18).
Графики – это очень универсальные структуры данных, которые могут решать множество реальных проблем. Графики часто используются в социальных сетях, таких как LinkedIn или Facebook. С развитием GraphQL данные организуются в виде графиков или сетей.
Базовая реализация графа:
import java.util.*;
class Graph {
// A utility function to add an edge in an
// undirected graph
static void addEdge(ArrayList > adj,
int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// A utility function to print the adjacency list
// representation of graph
static void printGraph(ArrayList > adj)
{
for (int i = 0; i < adj.size(); i++) {
System.out.println("\nAdjacency list of vertex" + i);
for (int j = 0; j < adj.get(i).size(); j++) {
System.out.print(" -> "+adj.get(i).get(j));
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
// Creating a graph with 5 vertices
int V = 5;
ArrayList > adj
= new ArrayList >(V);
for (int i = 0; i < V; i++)
adj.add(new ArrayList());
// Adding edges one by one
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj);
}
}
Общие вопросы для интервью:
Найти кратчайший путь между двумя вершинами
Проверьте, существует ли путь между двумя вершинами
Найдите “материнскую вершину” в графике
Хэш-таблицы
Что такое хеширование? Прежде чем мы углубимся в хэш-таблицы, важно понять, что такое хеширование.
Хеширование – это процесс присвоения объекту уникального индекса, известного как ключ. Каждый объект идентифицируется с помощью пары ключ-значение, а коллекция объектов известна как словарь.
Хэш-таблица реализуется путем хранения элементов в массиве и идентификации их с помощью ключа. Хэш-функция принимает ключ и возвращает индекс, для которого хранится значение.
Таким образом, всякий раз, когда вы вводите ключ в хэш-функцию, она всегда будет возвращать один и тот же индекс, который будет идентифицировать связанный элемент. Кроме того, если хэш-функция когда-либо получит уникальный ключ, который возвращает уже использованный индекс, вы можете создать цепочку элементов со связанным списком.
Хэш-таблица имеет ряд полезных применений:
Когда ресурс совместно используется несколькими потребителями
Проверка пароля
Связывание имени файла и пути к нему
Общие вопросы для интервью:
Поиск симметричных пар в массиве
Объединение и пересечение списков с использованием хеширования
Бинарное дерево поиска
двоичное дерево поиска представляет собой двоичную древовидную структуру данных, состоящую из узлов. Узлы расположены со следующими свойствами:
Левый подузел всегда содержит значения меньше, чем родительский узел.
Правый подузел всегда содержит значения, превышающие значения родительского узла.
Оба подузла также будут двоичными деревьями поиска.
Бинарные деревья поиска используются во многих поисковых приложениях, а также используются для определения объектов, которые необходимо визуализировать в 3D-игре. Эта структура данных широко используется в инженерных проектах, поскольку иерархические данные очень распространены.
Общие операции:
Поиск – поиск элемента
Вставить – вставляет элемент в дерево
Обход по предварительному заказу – обход дерева способом предварительного заказа
Обход по порядку – обход дерева по порядку
Обход после заказа – обход дерева способом после заказа
Общие вопросы для интервью:
Найдите k-е максимальное значение в двоичном дереве поиска
Найдите минимальное значение в двоичном дереве поиска
Пройдите по заданному каталогу, используя поиск в ширину
Продолжайте учиться дальше.
Изучите наиболее часто задаваемые вопросы для интервью, не просматривая видео и не просматривая сотни вопросов. Обучающие текстовые курсы легко просматриваются и имеют живую среду кодирования, что делает обучение быстрым и эффективным.
Прохождение собеседования по кодированию: Шаблоны для вопросов по кодированию
Важные алгоритмы для изучения
Рекурсия
Рекурсия – это практика, при которой функция вызывает саму себя прямо или косвенно. Соответствующая вызываемая функция известна как рекурсивная функция . Хотя рекурсия часто ассоциируется с алгоритмом, она может помочь понять ее как способ или методологию решения проблемы.
Так почему же рекурсия полезна? Или что это вообще такое? Давайте рассмотрим, как мы можем использовать рекурсию для вычисления факториалов в качестве примера.
public static long factorial(int number){
//base case - factorial of 0 or 1 is 1
if(number <=1){
return 1;
}
return number*factorial(number - 1);
}
В приведенном выше примере функция начинается с числа $n$. Когда функция вызывается, она вызывает $факториал(n – 1)$. Допустим, значение $n$ равно 4; функция вернет
$4 * факториал(3) -> 4 * 3 * факториал(2) -> 4 * 3 * 2 * факториал(1)$
Один раз $, функция вернет $, и мы получим $факториал(4)$, равный $4 * 3 * 2 * 1$, то есть 24.
Здесь вы можете увидеть силу рекурсии. Это широко используемая практика решения сложной проблемы путем разбиения ее на более мелкие экземпляры до тех пор, пока мы не сможем ее решить. Используя рекурсию, вы можете упростить множество сложных задач, которые в противном случае были бы трудными.
Нужно больше объяснений? Прочитайте наш Что такое рекурсия? Порция эспрессо здесь.
Сортировка пузырьков
Пузырьковая сортировка – это простой алгоритм сортировки, который меняет местами соседние элементы, если они расположены в неправильном порядке. Алгоритм будет повторять массив несколько раз, пока элементы не будут в правильном порядке.
Скажем, у нас есть массив, как показано ниже.
Поскольку алгоритм сканирует массив слева направо для первой итерации, начиная с индекса 0, он сравнивает индекс $i$ с индексом $i + 1$. При индексе 1 он увидит, что 11 больше 6, и поменяет их местами.
Поскольку алгоритм продолжает сканирование для первой итерации, он увидит, что 13 больше 10, и поменяет их местами.
Затем он пройдет через массив для своей второй итерации. Он поменяет местами значения в индексах 2 и 3, когда увидит, что 11 больше 10.
Алгоритм будет сканировать массив для третьей итерации, и поскольку ему больше не нужно делать никаких обменов для третьей итерации, алгоритм завершится.
Как вы можете видеть, сортировка пузырьков может плохо работать при работе с большим количеством элементов, что делает ее в основном используемой просто как образовательный инструмент. Его сложность во время выполнения составляет O ($ n ^ 2$).
Реализация пузырьковой сортировки:
public static void bubble_srt(int array[]) {
int n = array.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (array[i] > array[k]) {
swapNumbers(i, k, array);
}
}
printNumbers(array);
}
}
Сортировка выбора
Сортировка по выбору – это алгоритм, который разбивает коллекцию элементов на сортированные и несортированные. Во время каждой итерации алгоритм находит наименьший элемент в несортированной группе и перемещает его в конец отсортированной группы.
Давайте рассмотрим пример:
Сначала все элементы не сортируются. Для первой итерации алгоритм пройдется по каждому элементу и определит 4 как наименьшее значение. Алгоритм поменяет 11, первый элемент в несортированной группе, на самый низкий элемент в несортированной группе, 4.
Теперь отсортированная группа имеет индекс 0, а несортированная группа имеет индекс от 1 до индекса 3. Для второй итерации алгоритм начнет с индекса 1 и просканирует массив, определив 6 как наименьшее значение в несортированной группе. Он поменяет местами 11 и 6.
Отсортированная группа теперь имеет индекс от 0 до индекса 1, а несортированная группа имеет индекс от 2 до индекса 3. Для третьей итерации алгоритм начнется с индекса 2 и найдет 11 как наименьшее значение. Поскольку 11 уже находится в правильном индексе, он не будет двигаться. На этом алгоритм заканчивается.
Подобно пузырьковой сортировке, сортировка по выбору часто является медленным алгоритмом. Он также имеет сложность выполнения O ($ n ^ 2$).
Реализация сортировки по выбору:
public static int[] doSelectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return arr;
}
}
Сортировка вставки
Сортировка по вставке – это простой алгоритм сортировки, который строит конечный массив путем сортировки элемента по одному за раз. Как это работает?
Проверяет каждый элемент и сравнивает его с отсортированными элементами слева
Вставляет элемент в правильном порядке для отсортированных элементов
Давайте посмотрим на пример .
Алгоритм начинается с индекса 0 со значением 11. Поскольку слева от 11 нет элементов, он остается там, где он есть. Теперь перейдем к индексу 1. Значение слева от него равно 11, что означает, что мы меняем местами 11 и 4.
Опять же, алгоритм выглядит слева от 4. Поскольку слева от 4 нет элемента, он остается там, где он есть. Далее переходим к индексу 2. Элемент со значением 6 смотрит влево. Поскольку сейчас меньше 11, эти двое переключаются.
Элемент 6 снова смотрит влево, но поскольку 4 меньше 6, он остается там, где он есть. Далее мы переходим к элементу с индексом 4. Алгоритм смотрит влево, но поскольку 11 меньше 13, он остается там, где он есть. Теперь алгоритм завершен.
Сортировка по вставке почти всегда более эффективна, чем сортировка по пузырькам и сортировка по выделению, поэтому она чаще используется при работе с небольшим количеством элементов. Подобно двум другим алгоритмам сортировки, сортировка по вставке также имеет квадратичное время выполнения O ($ n ^ 2$).
Реализация сортировки по вставке:
public static int[] doInsertionSort(int[] input){
int temp;
for (int i = 1; i < input.length; i++) {
for(int j = i ; j > 0 ; j--){
if(input[j] < input[j-1]){
temp = input[j];
input[j] = input[j-1];
input[j-1] = temp;
}
}
}
return input;
}
Бинарный поиск
Бинарный поиск является наиболее эффективным алгоритмом поиска для поиска элемента. Алгоритм работает путем сравнения среднего элемента массива или списка с целевым элементом. Если значения совпадают, будет возвращен индекс элемента. Если нет, то список будет сокращен вдвое.
Если бы целевое значение было меньше среднего значения, то новый список был бы левой половиной. Если бы целевое значение было больше среднего значения, то новый список был бы правой половиной.
Этот процесс продолжается, когда вы продолжаете разделять список и искать одну из половин, пока алгоритм поиска не найдет целевое значение и не вернет позицию. Сложность выполнения этого алгоритма составляет $O(log2n)$. Важно отметить, что двоичный поиск работает только в том случае, если список уже отсортирован.
Чтобы визуализировать двоичный поиск, предположим, что у вас есть отсортированный массив из десяти элементов, и вы ищете индекс 33.
Среднее значение этого массива равно 16, и алгоритм сравнивает его с 33. 33 больше 16, поэтому алгоритм разбивает массив и выполняет поиск во второй половине.
Новое среднее значение равно 28. Поскольку 33 больше 28, алгоритм выполняет поиск во второй половине массива.
После того, как массив снова разделен на правую половину, новое среднее значение равно 33. Алгоритм видит, что среднее значение и целевое значение совпадают, и возвращает положение элемента.
Реализация двоичного поиска:
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the
// middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
Другие темы для обсуждения
Имейте в виду, что концепции, которые мы рассмотрели сегодня, являются просто введением. Важно, чтобы вы глубже погрузились в концепции и попрактиковались в вопросах кодирования. Ниже приведены другие темы, с которыми мы предлагаем вам ознакомиться:
Двусвязный список Двусвязный список
Алгоритм Дейкстры
Как пройти ваше следующее собеседование по программированию
Планируйте заранее : Первое, что вы должны сделать, прежде чем что-либо предпринять, – это разработать комплексный план обучения. Определите темы, по которым, по вашему мнению, вам нужно больше практиковаться, и составьте расписание, которого вы можете придерживаться. Вы должны быть готовы учиться последовательно. В целом, четыре-шесть недель – отличный срок для подготовки к собеседованию.
Язык программирования : Выберите язык программирования, который вам удобно использовать. Насколько легко вы могли бы написать решение за 25 или около того минут, используя этот язык? Некоторые популярные языки, которые будут использовать разработчики, – это Java, Python, Javascript или C++.
Компания : Прежде чем идти на какое-либо собеседование, вы должны изучить компанию. Изучение корпоративной культуры и ценностей невероятно важно для того, чтобы убедиться, что вы соответствуете компании, и чтобы вы были более подготовлены к нетехническому аспекту собеседования. Вам также следует изучить общие проблемы, на которые тестируется компания. Делая это, вы можете целенаправленно практиковаться, чтобы подготовиться к собеседованию
Поведенческое интервью : Как бы вам ни казалось, что вы готовы приступить к техническому собеседованию, вы не можете забыть о поведенческом собеседовании. С помощью поведенческого собеседования компании хотят убедиться, что вы хорошо подходите для этой роли и компании. Ознакомьтесь с нашим руководством по поведенческому собеседованию , чтобы должным образом подготовиться к собеседованию.
Теперь у вас должно быть хорошее представление о том, что вам нужно сделать до дня собеседования. Тебе еще многому предстоит научиться, но не беспокойся. Если вы хотите продолжить обучение, ознакомьтесь с ресурсами, предоставленными Собеседование по кодированию или наш Python , Java или Javascript | курсы подготовки к собеседованиям в рамках нашей серии собеседований на языке программирования.
Ресурсы
Вот список ресурсов для вас, касающихся собеседования по программированию и общих тем информатики.
Статьи
- Успешное прохождение собеседования по Javascript : Узнайте, как ответить на главные вопросы собеседования по Javascript
- Поведенческие интервью : Руководство по ответам на поведенческие вопросы в интервью
- Подготовка к собеседованию на Java : Изучите 15 популярных вопросов для собеседования на Java, чтобы лучше подготовиться к следующему собеседованию
Оригинал: “https://dev.to/educative/top-data-structures-and-algorithms-every-developer-must-know-241a”