Шпаргалка для технического собеседования

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

Основы структур данных

Массив

Определение:

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

Что вам нужно знать:

Массив оптимален для индексирования; плох для поиска, вставки и удаления (если не делать этого в самом конце массива).
Основная разновидность — линейные массивы, или одноразмерные.
Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер.
Динамические массивы подобны линейным, но в них зарезервировано пространство для дополнительных элементов.
При заполнении динамического массива его содержимое копируется в массив большего размер.
Двумерные массивы имеют два индекса x и y, как сетки или вложенные массивы.

Эффективность («О» большое):

Индексирование: линейный массив — O(1), динамический массив — O(1).
Поиск: линейный массив — O(n), динамический массив — O(n).
Оптимизированный поиск: линейный массив — O(log n), динамический массив — O(log n).
Вставка: линейный массив — недопустимо, динамический массив — O(n).

Связный список

Определение:

Данные хранятся в узлах, указывающих на другие узлы.
Узел содержит один элемент данных и одну ссылку (на другой узел).Связный список соединяет узлы друг с другом с помощью ссылок от одного узла к другому.

Что вам нужно знать:

Связный список разработан для оптимизирования вставки и удаления. Медленно работает при индексировании и поиске.
Двусвязный список содержит узлы, которые ссылаются на предыдущие узлы.
Кольцевой связный список — это простой связный список, хвосткоторого (последний узел) ссылается на голову (первый узел).
Стек обычно реализуется с помощью связных списков, но может быть создан и из массивов.
Стеки — это LIFO-структуры данных (last in, first out).Голова связного списка, лежащего в основе стека, единственное место для вставки и удаления элементов.
Очереди тоже могут быть реализованы с помощью связного списка или массива.
Очереди — это FIFO-структуры данных (first in, first out).Очередь представляет собой двусвязный список, в котором элементы удаляются из головы, а добавляются в хвост.

Эффективность («О» большое):

Индексирование: связный список — O(n).
Поиск: связный список — O(n).
Оптимизированный поиск: связный список — O(n).
Вставка: связный список — O(1).

Хэш-таблица

Определение:

Данные хранятся в виде пар ключ-значение.
Хэш-функции принимают ключ и возвращают выходные данные, соответствующие только этому ключу.
Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных.Хэш-функции возвращают для данных уникальные адреса в памяти.

Что вам нужно знать:

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

Эффективность («О» большое):

Индексирование: хэш-таблицы — O(1).
Поиск: хэш-таблицы — O(1).
Вставка: хэш-таблицы — O(1).

Двоичное дерево

Определение:

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

Что вам нужно знать:

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

Эффективность («О» большое):

Индексирование: двоичное дерево поиска — O(log n).
Поиск: двоичное дерево поиска — O(log n).
Вставка: двоичное дерево поиска — O(log n).

Поиск

Поиск в ширину

Определение:

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

Что вам нужно знать:

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

Эффективность («О» большое):

Поиск: поиск в ширину — O(|E| + |V|).
E — количество рёбер (граней?).
V — количество вершин.

Поиск в глубину

Определение:

Поиск в глубину — это алгоритм, ищущий по дереву (или графу) сначала в глубину начиная с корня.
Алгоритм идёт по дереву, переходя между уровнями по левым дочерним узлам, пока не дойдёт до самого низа.Завершив проход по ветви, алгоритм возвращается обратно, просматривая правые дочерние узлы этой ветви. Причём, если возможно, выбирает самые левые из узлов, расположенных справа от предыдущего маршрута.Завершив просмотр всей ветви, алгоритм переходит к узлу, расположенному справа от корня, и снова идёт по левым дочерним узлам до самого дна.Последним анализируется крайний правый узел (расположенный справа от всех своих предшественников).

Что вам нужно знать:

Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.
Для работы алгоритма используется стек.
Поскольку стек является LIFO-структурой, ему не нужно отслеживать указатели узлов, поэтому потребляется меньше памяти, чем в случае с поиском в ширину.Когда алгоритм не может дальше идти по левой стороне, он начинает анализировать стек.

Эффективность («О» большое):

Поиск: поиск в глубину — O(|E| + |V|).
E — количество рёбер (граней?).
V — количество вершин.

Сравнение поисков в ширину и в глубину

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

Нюансы:

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

Эффективная сортировка

Сортировка слиянием

Определение:

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

Что вам нужно знать:

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

Эффективность («О» большое):

Наилучший вариант сортировки: сортировка слиянием — O(n).
Средний вариант сортировки: сортировка слиянием — O(n log n).
Худший вариант сортировки: сортировка слиянием — O(n log n).

Быстрая сортировка

Определение:

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

Что вам нужно знать:

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

Эффективность («О» большое):

Наилучший вариант сортировки: быстрая сортировка — O(n).
Средний вариант сортировки: быстрая сортировка — O(n log n).
Худший вариант сортировки: быстрая сортировка — O(n^2).

Пузырьковая сортировка

Определение:

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

Что вам нужно знать:

Алгоритм очень прост в реализации, но наименее эффективен из всех трёх, описанных здесь.
Сравнив два значения и переместив наименьшее влево, алгоритм переходит на одну позицию вправо.

Эффективность («О» большое):

Наилучший вариант сортировки: пузырьковая сортировка — O(n).
Средний вариант сортировки: пузырьковая сортировка — O(n^2).
Худший вариант сортировки: пузырьковая сортировка — O(n^2).

Сравнение алгоритмов сортировки слиянием и быстрой сортировки

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

Основные типы алгоритмов

Рекурсивные алгоритмы

Определение:

Как следует из определения, этот алгоритм вызывает самого себя.
Рекурсивный сценарий — когда условный оператор используется для запуска рекурсии.Базовый сценарий — когда условный оператор используется для прерывания рекурсии.

Что вам нужно знать:

Слишком глубокий уровень стека и переполнение стека.
Если при работе рекурсивного алгоритма вы столкнулись с чем-то из перечисленного, значит, вы всё испортили.Это означает, что базовый сценарий не был ни разу запущен из-за ошибок, либо проблема была столь серьёзной, что у вас кончилась память, прежде чем рекурсия была прервана.Знание того, сможете ли вы достичь базового сценария, является неотъемлемой частью правильного использования рекурсии.Такие алгоритмы часто используются при поиске в глубину.

Итеративные алгоритмы

Определение:

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

Что вам нужно знать:

Обычно итерации представлены в виде циклов, выражений for, while и until.
Итерация — это однократный проход по набору данных.
Такие алгоритмы часто применяются для обработки массивов.

Сравнение рекурсивности и итеративности

Отличить рекурсивность от итеративности бывает сложно, поскольку обе они используются для реализации друг друга. Однако:
Рекурсивность обычно более выразительна и проста в реализации.Итеративность потребляет меньше памяти.
Функциональные языки склонны к использованию рекурсивности (например, Haskell).
Императивные языки склонны к использованию итеративности (например, Ruby).
Больше информации вы можете получить из поста на Stack Overflow.

Псевдокод прохождения по массиву (вот почему для этого применяется итеративность)

Рекурсивность                     | Итеративность
----------------------------------|----------------------------------
recursive method (array, n)       | iterative method (array)
  if array[n] is not nil          |   for n from 0 to size of array
    print array[n]                |     print(array[n])
    recursive method(array, n+1)  |
  else                            |
    exit loop                     |

Жадные алгоритмы

Определение:

Жадными называют алгоритмы, выбирающие только ту информацию, которая удовлетворяет определённым критериям.
Жадный алгоритм содержит пять основных компонентов:
Набор кандидатов (candidate set), на основе которого создаётся решение.Функция выбора, которая решает, какой лучший кандидат будет добавлен в решение.Функция обоснования (feasibility function), которая решает, может ли кандидат внести вклад в решение.Целевая функция (objective function), которая присваивает значение решению или частичному значению.Функция решения (solution function), которая сигнализирует о том, что мы нашли полное решение.

Что вам нужно знать:

Жадные алгоритмы используются для поиска оптимального решения данной проблемы.
Обычно они применяются к наборам данных, в которых лишь небольшая порция обработанной информации даёт желаемый результат.
Часто жадные алгоритмы могут помочь в уменьшении «О» большого другого алгоритма.

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

greedy algorithm (array)
  var largest difference = 0
  var new difference = find next difference (array[n], array[n+1])
  largest difference = new difference if new difference is > largest difference
  repeat above two steps until all differences have been found
  return largest difference

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