Pull to refresh
VK
Building the Internet

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

Reading time 8 min
Views 204K


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


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


Массив


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


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

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


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

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

Tags:
Hubs:
+55
Comments 85
Comments Comments 85

Articles

Information

Website
vk.com
Registered
Founded
Employees
5,001–10,000 employees
Location
Россия
Representative
Миша Берггрен