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

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

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

Массив

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

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

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

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

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