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

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

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

Массив

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

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

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

• Массив оптимален для индексирования; плох для поиска, вставки и удаления (если не делать этого в самом конце массива).
• Основная разновидность — линейные массивы, или одноразмерные.
  • Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер.
• Динамические массивы подобны линейным, но в них зарезервировано пространство для дополнительных элементов.
  • При заполнении динамического массива его содержимое копируется в массив большего размер.
• Двумерные массивы имеют два индекса 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

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

Автор: Barrayar

Источник