Большая шпаргалка по алгоритмам с собеседований.

Так уж повелось, что любой уважающий себя работодатель перенимает передовые^✻ методики FAANG — по этой причине практически во всех IT-собесах есть она: секция алгоритмов. Кто-то ей рад, кто-то не очень, но секция есть и уходить пока не планирует. Поэтому нужно закатать рукава и достойно встретить суровую реальность.

При изучении алгоритмов расслабьтесь и получайте удовольствие, ведь есть ненулевая вероятность, что вам понадобятся полученные знания вне собеса. Кто знает, может однажды умение быстро обходить двоичное дерево поможет спасти вам мир (как и знание регулярок):

Большая шпаргалка по алгоритмам с собеседований.

Да и вообще, изучение алгоритмов может быть очень залипательным и полезным; Миша Ломоносов говорит, что это ум в порядок приводит.

Разбор огромного количества вопрос с собеседований Python в моем канале, а здесь собрана целая папка с каналами для подготовки к собеседованиям.

Тема алгоритмов очень велика, так выглядят отдельные области и понятия:

Большая шпаргалка по алгоритмам с собеседований.

Немало всего) Как можно убедиться, тема алгоритмов и правда обширна, поэтому в этой статье коснёмся только самых основных вещей:

Для структур данных и алгоритмов сортировки напишем реализацию на Python, чтобы можно было сразу затестить, как всё это работает

Поехали!

Алгоритмическая сложность и асимптотический анализ

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

Допустим, некоторому алгоритму нужно выполнить 4n^3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n. В этом случае временная сложность этого алгоритма равна О(n^3), т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n).

Встречайте типичных представителей каждого уровня сложности:

Большая шпаргалка по алгоритмам с собеседований.

O(1) — константная сложность

Случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1). Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

Характерные примеры со сложностью O(1): арифметические операции, вызов функции

O(n) — линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

Вот ниже последовательность шагов при поиске числа 47 в отсортированном массиве.

Большая шпаргалка по алгоритмам с собеседований.

O(n^2) — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n*n, т. е. n^2.

В итоге

Лучшие алгоритмы имеют сложность O(1) или O(log n), в этом случае время выполнения разных операций растёт слабо при увеличении количества элементов или вообще постоянно для О(1). Худшие алгоритмы имеют сложность O(n!), O(2^n) или O(n^2), что сильно затрудняет их использование для больших структур данных.

Большая шпаргалка по алгоритмам с собеседований.

Как растёт время выполнения операций в зависимости от размера массива для разных видов сложности.

Большая шпаргалка по алгоритмам с собеседований.

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

Большая шпаргалка по алгоритмам с собеседований.

Временная и пространственная сложность разных методов сортировки:

Большая шпаргалка по алгоритмам с собеседований.

Со сложностями разобрались, поехали к структурам данных!

Структуры данных

В этой статье мы рассмотрим такие структуры данных как:

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

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

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

Связный список — одна из базовых структур данных. Ее часто сравнивают с массивом, так как многие другие структуры можно реализовать с помощью либо массива, либо связного списка.

Связный список состоит из группы узлов, которые вместе образуют последовательность. Каждый узел содержит две вещи: фактические данные, которые в нем хранятся (это могут быть данные любого типа) и указатель (или ссылку) на следующий узел в последовательности. Самый первый элемент списка называют головой (head) односвязного списка, а последний — хвостом (tail). Последний элемент односвязного списка в качестве ссылки содержит null-значение.

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

Также существуют двусвязные списки: в них у каждого узла есть указатель и на следующий, и на предыдущий элемент в списке. Есть ещё кольцевой связный список — у него хвост (последний узел) ссылается на голову (первый узел).

Вот так, например, выглядит удаление узла с числом 99 из односвязного списка:

Большая шпаргалка по алгоритмам с собеседований.

Связные списки могут быть использованы для реализации стека и очереди (здесь вместо связных списков можно использовать и массивы).

Стек

  • это LIFO-структура данных (last in, first out)
  • голова связного списка, лежащего в основе стека, единственное место для вставки и удаления элементов

Очередь

  • это FIFO-структура данных (first in, first out)
  • очередь представляет собой двусвязный список, в котором элементы удаляются из головы, а добавляются в хвост

Алгоритмическая сложность для основных операций со связным списком:

действиесложность
поиск элементаO(n)
добавление элементаO(1)
удаление элементаO(n)
подсчёт элементов, подходящих под условиеO(n)

Вот так можно реализовать связный список на Python:

class Node(object):
# каждый узел содержит данные data и указатель next на следующий узел
def __init__(self, data, next = None):
self.data = data;
self.next = next;

def setData(self, data):
self.data = data;

def getData(self): # функция для получения значения data из узла
return self.data

def setNext(self, next): # функция для создания следующего узла
self.next = next

def getNext(self): # функция для получения следующего узла
return self.next

class LinkedList(object):
def __init__(self): # определяем head в списке
self.head = None

def printLinkedList(self): # печатаем data из связного списка
temp = self.head
while(temp):
print(temp.data, end=' ')
temp = temp.next

def insertAtStart(self, data): # вставка узла в начало
newNode = Node(data)
newNode.next = self.head
self.head = newNode

def insertBetween(self, previousNode, data): # вставка узла после previousNode
if (previousNode.next is None):
print('Previous node should have next node!')
else:
newNode = Node(data)
newNode.next = previousNode.next
previousNode.next = newNode

def insertAtEnd(self, data): # вставка в конец связного списка
newNode = Node(data)
temp = self.head
while(temp.next != None): # get last node
temp = temp.next
temp.next = newNode

def delete(self, data): # удаление элемента по data или key
temp = self.head
if (temp.next is not None): # если data/key найден в первом узле
if(temp.data == data):
self.head = temp.next
temp = None
return
else:
while(temp.next != None): # иначе искать все узлы
if(temp.data == data):
break
prev = temp
temp = temp.next

if temp == None: # если узел не найден
return

prev.next = temp.next
return

# итеративный поиск
def search(self, node, data):
if node == None:
return False
if node.data == data:
return True
return self.search(node.getNext(), data)

if __name__ == '__main__':
List = LinkedList()
List.head = Node(1) # создаём первый узел - head
node2 = Node(2)
List.head.setNext(node2) # создаём второй узел --> node2
node3 = Node(3)
node2.setNext(node3) # после node2 идёт node3
List.insertAtStart(4) # вставляем node4 вначало, сейчас: 4 1 2 3
List.insertBetween(node2, 5) # вставляем node5 после node2, сейчас: 4 1 2 5 3 6
List.insertAtEnd(6) # вставляем 6 в конец
List.printLinkedList()

List.delete(3) # удаляем 3, получаем: 4 1 2 5 6
List.printLinkedList()

print(List.search(List.head, 1))

Стек

Стек
Стек

Стек — базовая структура данных, которая позволяет добавлять или удалять элементы только в ее начале. Она похожа на стопку книг: если вы хотите взглянуть на книгу в середине стека, сперва придется убрать лежащие сверху.

Стек организован по принципу LIFO (Last IFirst Out, “последним пришел — первым вышел”) , то есть элементы кладутся наверх и сверху же берутся. Последний элемент, который вы добавили в стек, первым выйдет из него.

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

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

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

Алгоритмическая сложность для основных операций с элементами стека:

действиесложность
добавление элемента в вершину стека (push)O(1)
удаление элемента из вершины стека (pop)O(1)
возврат верхнего элемента без его удаления (peek)O(1)
проверка стека на пустоту (isEmpty)O(1)

Смоделировать стек в Python, используя список в качестве резервного хранилища, мы можем так (здесь аннотации типов, если кто не в теме):

from typing import TypeVar, Generic, List
T = TypeVar('T')

class Stack(Generic[T]):
def __init__(self) -> None:
self._container: List[T] = []
def push(self, item: T) -> None:
self._container.append(item)

def pop(self) -> T:
return self._container.pop()

def __repr__(self) -> str:
return repr(self._container)

Стеки идеально подходят для задачи о ханойских башнях. Для того чтобы переместить диск на башню, мы можем использовать операцию push. Для того чтобы переместить диск с одной башни на другую, мы можем вытолкнуть его с первой (pop) и поместить на вторую (push). Определим башни как объекты Stack и заполним первую из них дисками:

num_discs: int = 3
tower_a: Stack[int] = Stack()
tower_b: Stack[int] = Stack()
tower_c: Stack[int] = Stack()
for i in range(1, num_discs + 1):
tower_a.push(i)

Ну и вот так может выглядеть функция hanoi(), отвечающая за перемещение дисков с одной башни на другую, используя третью временную башню:

def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None:
if n == 1:
end.push(begin.pop())
else:
hanoi(begin, temp, end, n — 1)
hanoi(begin, end, temp, 1)
hanoi(temp, end, begin, n - 1)

После вызова функции hanoi() можно проверить башни tower_atower_b и tower_c, и убедиться, что диски были успешно перемещены.

Очередь

Очередь
Очередь

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

Очередь устроена по принципу FIFO (First IFirst Out, “первый пришел — первый вышел”). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.

Основные операции:

  • Добавление элемента в конец (enqueue)
  • Удаление первого элемента (dequeue)

Алгоритмическая сложность:

АлгоритмСреднее значениеХудший случай
ПоискO(n)O(n)
ВставкаO(1)O(1)
УдалениеO(1)O(1)

Очередь можно реализовать так:

from typing import TypeVar, Generic, Deque
T = TypeVar('T')

class Queue(Generic[T]):
def __init__(self) -> None:
self._container: Deque[T] = Deque()

@property
def empty(self) -> bool:
return not self._container # не равно True для пустого контейнера

def push(self, item: T) -> None:
self._container.append(item)

def pop(self) -> T:
return self._container.popleft() # FIFO

def __repr__(self) -> str:
return repr(self._container)

Кстати, в этой реализации очереди Queue в качестве резервного хранилища применяется deque, а не list. Это связано с тем, откуда извлекаются данные в процессе операции pop. В стеке мы помещаем элементы с правого конца и извлекаем их тоже справа. В очереди мы помещаем элементы справа, а извлекаем слева. Структура данных list в Python имеет эффективный метод pop для извлечения справа, но не слева. Структура данных deque позволяет эффективно извлекать данные с любой стороны, например, есть встроенный метод popleft(), у которого нет эквивалента в list.

Множество

Большая шпаргалка по алгоритмам с собеседований.

Множество хранит значения данных без определенного порядка (не везде, в C++ упорядоченное множество), не повторяя их (есть ещё мультимножество, там могут быть повторы). Оно позволяет не только добавлять и удалять элементы: есть еще несколько важных функций, которые можно применять к двум множествам сразу.

  • Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов)
  • Пересечение анализирует два множества и  создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах
  • Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом
  • Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества

Алгоритмическая сложность для основных операций с элементами множества:

действиесложность
поиск элементаO(1)
добавление элементаO(1)
удаление элемента (для неупорядоченного множества)O(1)

Работать с множествами в Python просто и приятно:

a = set([1, 2, 1, 3, 4])
b = {4, 4, 5, 6}
c = {1, 2}

print(a, b, c)
# {1, 2, 3, 4} {4, 5, 6} {1, 2}

print(c.issubset(a), c <= a)
# True True

print(a.union(b), a | b)
# {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6}

print(a.intersection(b), a & b)
# {4} {4}

print(a.difference(b), a - b)
# {1, 2, 3} {1, 2, 3}

print(c) # {1, 2}
c.add(3)
print(c) # {1, 2, 3}
c.remove(2)
print(c) # {1, 3}
c.pop()
print(c) # {3}
c.clear()
print(c) # set()

Map (словарь, ассоциативный массив)

Map
Map

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

Нередко под капотом у Map хеш-таблица, поэтому можно рассматривать Map как обёртку над более общими хеш-таблицами, о которых поговорим ниже.

Алгоритмическая сложность для основных операций с элементами Map (в случае реализации на хеш-таблицах):

действиесложность
добавление нового элемента с уникальным ключомО(1)
удаление элемента по ключуО(1)
изменение значения по ключуО(1)
получение значения по ключуО(1)

Хеш-таблица

хеш-таблица
хеш-таблица

Хеш-таблица — структура, которая содержит пары ключ/значение. Она использует хеш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти желаемое значение. Хеш-таблицы часто используются для реализации Map (словарей).

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

Когда вы вводите пару ключ/значение в хеш-таблицу, ключ проходит через хеш-функцию, функция возвращает число. В дальнейшем это число используется как фактический ключ, который соответствует определенному значению. Когда вы снова введете тот же ключ, хеш-функция обработает его и вернет такой же числовой результат. Затем этот результат будет использован для поиска связанного значения. Это позволяет мгновенно извлекать элементы с минимальной сложностью O(1).

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

Сложность для основных операций с элементами хеш-таблицы:

действиесложность
добавление нового элемента с уникальным ключомО(1)
удаление элемента по ключуО(1)
изменение значения по ключуО(1)
получение значения по ключуО(1)

Вот так может выглядеть простая реализация хеш-таблицы со самыми важными методами:

class HashTable:
def __init__(self):
self.hashTable = [[],] * 10

def checkPrime(self, n):
if n == 1 or n == 0:
return 0
for i in range(2, n//2):
if n % i == 0:
return 0
return 1

def getPrime(self, n):
if n % 2 == 0:
n = n + 1
while not self.checkPrime(n):
n += 2
return n

def hashFunction(self, key):
capacity = self.getPrime(10)
return key % capacity

def insertData(self, key, data):
index = self.hashFunction(key)
self.hashTable[index] = [key, data]
def removeData(self, key):
index = self.hashFunction(key)
self.hashTable[index] = 0

def __str__(self):
return str(self.hashTable)


hash_table = HashTable()

hash_table.insertData(123, "apple")
hash_table.insertData(432, "mango")
hash_table.insertData(213, "banana")
hash_table.insertData(654, "guava")

print(hash_table)
hash_table.removeData(123)
print(hash_table)

# [[], [], [123, 'apple'], [432, 'mango'], [213, 'banana'], [654, 'guava'], [], [], [], []]# [[], [], 0, [432, 'mango'], [213, 'banana'], [654, 'guava'], [], [], [], []]

Отлично, поехали к следующей структуре — двоичному дереву

Двоичное (бинарное) дерево

Большая шпаргалка по алгоритмам с собеседований.

Дерево — структура данных, состоящая из узлов. Ей присущи следующие свойства:

  • Каждое дерево имеет корневой узел (вверху)
  • Корневой узел имеет 0 или более дочерних узлов
  • Каждый дочерний узел имеет 0 или более дочерних узлов, и т.д.

У двоичного дерева поиска есть 2 дополнительных свойства:

  • Каждый узел имеет до 2 дочерних узлов (потомков)
  • Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого

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

Алгоритмическая сложность операций над двоичным деревом:

действиесложностьсложность в худшем случае
поиск элементаO(log n)O(n)
вставка элементаO(log n)O(n)
удаление элементаO(log n)O(n)

Что ж, напишем реализацию двоичного дерева:

class BinaryTreeNode:
def __init__(self, value, parent=None):
self.left = None # ссылка на левый дочерний узел
self.right = None # ссылка на правый дочерний узел
self.parent = parent # ссылка на родителя
self.value = value # полезная нагрузка

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

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

    def find_node(root, value):
node = self
while node:
if value == node.value:
return node
if value < node.value:
node = node.left
if value > node.value:
node = node.right
return None

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

  • если это так, сравниваем значение со вставляемым. По результату сравнения проводим проверку для правого или левого поддеревьев
  • если узел пуст, создаем новый и заполняем ссылку на текущий узел в качестве родителя

Операция вставки использует рекурсивный подход аналогично операции поиска:

    def insert_node(self, value):
return self._insert_node(value, self)

def _insert_node(self, value, parent_node):
if value < parent_node.value:
if parent_node.left is None:
parent_node.left = BinaryTreeNode(value, parent_node)
else:
self._insert_node(value, parent_node.left)
elif value > parent_node.value:
if parent_node.right is None:
parent_node.right = BinaryTreeNode(value, parent_node)
else:
self._insert_node(value, parent_node.right)

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

Если необходимо удалить корневой узел или промежуточные вершины и сохранить структуру бинарного дерева поиска, выбирают один из следующих двух способов:

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

Оба варианта подходят для нашего дерева. Реализуем в коде второй вариант:

    def remove_node(self, value):
return self._remove_node(value, self)

def _remove_node(self, value, node):
if node is None:
return None

if value < node.value:
node.left = self._remove_node(value, node.left)
return node
elif value > node.value:
node.right = self._remove_node(value, node.right)
return node
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
original = node
node = node.right
while node.left:
node = node.left
node.right = self._remove_min(original.right)
node.left = original.left
return node

Обход деревьев. Когда мы поработали с деревом и нам нужно его сохранить в файл или вывести в печать, нам больше не нужен древовидный формат. Здесь мы прибегаем к обходу дерева — последовательное единоразовое посещение всех вершин дерева.

Существуют такие 3 варианта обхода деревьев:

  • Прямой обход (КЛП): корень → левое поддерево → правое поддерево
  • Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево
  • Обратный обход (ЛПК): левое поддерево → правое поддерево → корень

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

Большая шпаргалка по алгоритмам с собеседований.

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

    def traverse_recursive(node):
if node is not None:
print(f"node = {node.value}")
traverse_recursive(node.left)
traverse_recursive(node.right)

def traverse_with_stack(root):
stack = [] stack.append(root)
while len(stack) > 0:
current_node = stack.pop()
print(f"node = {current_node.value}")
if current_node.right is not None:
stack.append(current_node.right)
if current_node.left is not None:
stack.append(current_node.left)

def traverse_with_queue(root):
queue = [] queue.append(root)
while len(queue) > 0:
current_node = queue.pop(0)
print(f"node = {current_node.value}")
if current_node.left:
queue.append(current_node.left)
if current_node.right:
queue.append(current_node.right)

Вот мы и реализовали двоичное дерево со всеми важными методами, переходим к следующей структуре — префиксному дереву.

Префиксное дерево (бор)

(в каждом узле хранится только по 1 букве, слова тут для наглядности)

Большая шпаргалка по алгоритмам с собеседований.

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

Каждый узел в языковом префиксном дереве содержит 1 букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.

Префиксное дерево можно использовать для разных задач:

  • хранение строк: если есть много повторяющихся длинных префиксов, то бор может занимать гораздо меньше места, чем массив или set строк
  • сортировка строк: по построенному бору можно пройтись DFS-ом и вывести все строки в лексикографическом порядке
  • просто как множество строк: в бор легко добавлять и удалять слова, а также делать проверки вхождения

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

Большая шпаргалка по алгоритмам с собеседований.

Здесь не без ложки дёгтя, вот 2 недостатка использования бора в качестве ассоциативного массива:

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

Как-то вот так, не будет тут сильно засиживаться, поехали к двоичной куче)

Двоичная куча (пирамида)

Двоичные кучи с максимальным и минимальным корневым элементом:

Двоичная куча
Двоичная куча

Отображение древовидного представления кучи на его представление в виде массива:

Большая шпаргалка по алгоритмам с собеседований.

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

Двоичная куча может быть минимальной или максимальной. В максимальной куче ключ любого узла всегда больше ключей его потомков или равен им. В минимальной куче все устроено наоборот: ключ любого узла меньше ключей его потомков или равен им.

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне.

Алгоритмическая сложность:

АлгоритмСреднее значениеХудший случай
ПоискO(n)O(n)
ВставкаO(1)O(log n)
УдалениеO(log n)O(log n)

Давайте имплементируем нашу двоичную кучу на Python. Поскольку куча целиком может быть представлена в виде обычного списка, то всё, что нужно сделать, – это инициализировать список и атрибут currentSize, через который отслеживается текущий размер кучи.

Создадим класс BinHeap:

class BinHeap:
def __init__(self):
self.heapList = [0] self.currentSize = 0

Теперь нужно написать метод insert. Простейший и наиболее эффективный способ добавить элемент — просто присоединить его к концу списка. Хорошая новость — таким образом мы поддержим свойство полноты дерева. Плохая — весьма вероятно, что это нарушит структурное свойство кучи. К счастью, существует способ написать метод, позволяющий нам восстановить структуру с помощью сравнения нового элемента с его предком. Если добавляемый элемент меньше родителя, то мы можем просто поменять их местами. Вот тут ниже видно серию перестановок, необходимую для “просачивания” нового элемента на его законное место в дереве:

Большая шпаргалка по алгоритмам с собеседований.

Теперь мы готовы написать метод insert. Большую часть его работы уже делает percUp. После того, как в дерево вставлен новый элемент, percUp позиционирует его как положено:

    def percUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
tmp = self.heapList[i // 2] self.heapList[i // 2] = self.heapList[i] self.heapList[i] = tmp
i = i // 2
    def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)

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

Большая шпаргалка по алгоритмам с собеседований.

Чтобы поддержать свойство упорядоченности, нам надо всего лишь поменять местами корень с меньшим, чем он потомком. После начальной перестановки мы можем повторять процесс для узла и его потомков до тех пор, пока он не переместится на позицию, в которой будет меньше обоих своих детей. Код для “просачивания” узла вниз по дереву можно найти в методах percDown и minChild ниже:

    def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i] self.heapList[i] = self.heapList[mc] self.heapList[mc] = tmp
i = mc

def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2+1]:
return i * 2
else:
return i * 2 + 1

Код для операции delMin ниже. Вся сложная работа снова отдана вспомогательной функции (в данном случае – percDown):

    def delMin(self):
retval = self.heapList[1] self.heapList[1] = self.heapList[self.currentSize] self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval

Ну и в завершение рассмотрим метод, который позволяет построить кучу из списка ключей:

    def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:] while (i > 0):
self.percDown(i)
i = i - 1

На рисунке ниже видно создание кучи из списка [9, 6, 5, 2, 3] при выполнении кода

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
Большая шпаргалка по алгоритмам с собеседований.

Готово, вот мы и реализовали двоичную кучу или пирамиду, можно переходить к следующей структуре)

Граф

Большая шпаргалка по алгоритмам с собеседований.

В простонародье граф — это совокупность узлов (вершин) и связей между ними (рёбер).

Графы можно поделить на 2 типа: ориентированные и неориентированные. У неориентированных графов ребра между узлами не имеют какого-либо направления, тогда как у ребер в ориентированных графах оно есть.

Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.

Матрица смежности
Матрица смежности

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

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

Существуют специальные алгоритмы для просмотра ребер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и поиск в глубину (depth-first search). С их помощью можно, например, определить, насколько близко к корневому узлу находятся те или иные вершины графа.

Для реализации структуры данных “граф” определим вначале класс Edge (связь между 2 вершинами):

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Edge:
u: int # вершина "откуда"
v: int # вершина "куда"

def reversed(self) -> Edge:
return Edge(self.v, self.u)

def __str__(self) -> str:
return f"{self.u} -> {self.v}"

Теперь определим класс Graph с использованием Edge (остальная часть определения ниже):

from typing import TypeVar, Generic, List, Optional
from edge import Edge

V = TypeVar('V') # тип вершин графа

class Graph(Generic[V]):
def __init__(self, vertices: List[V] = []) -> None:
self._vertices: List[V] = vertices
self._edges: List[List[Edge]] = [[] for _ in vertices]

Здесь список _vertices — это сердце графа. Все вершины сохраняются в списке, а впоследствии мы будем ссылаться на них по их целочисленному индексу в этом списке. Сама вершина может быть сложным типом данных, но ее индекс всегда имеет тип int, с которым легко работать. На другом уровне, между графовыми алгоритмами и массивом _vertices, этот индекс позволяет получить две вершины
с одним и тем же именем в одном графе.

Допишем наше определение класса Graph:

	@property
def vertex_count(self) -> int:
return len(self._vertices) # Количество вершин

@property
def edge_count(self) -> int:
return sum(map(len, self._edges)) # Количество ребер

# Добавляем вершину в граф и возвращаем ее индекс
def add_vertex(self, vertex: V) -> int:
self._vertices.append(vertex)
self._edges.append([]) # Добавляем пустой список для ребер
return self.vertex_count - 1 # Возвращаем индекс по добавленным вершинам

# Это ненаправленный граф,
# поэтому мы всегда добавляем вершины в обоих направлениях
def add_edge(self, edge: Edge) -> None:
self._edges[edge.u].append(edge)
self._edges[edge.v].append(edge.reversed())

# Добавляем ребро, используя индексы вершин (удобный метод)
def add_edge_by_indices(self, u: int, v: int) -> None:
edge: Edge = Edge(u, v)
self.add_edge(edge)

# Добавляем ребро, просматривая индексы вершин (удобный метод)
def add_edge_by_vertices(self, first: V, second: V) -> None:
u: int = self._vertices.index(first)
v: int = self._vertices.index(second)
self.add_edge_by_indices(u, v)

# Поиск вершины по индексу
def vertex_at(self, index: int) -> V:
return self._vertices[index]
# Поиск индекса вершины в графе
def index_of(self, vertex: V) -> int:
return self._vertices.index(vertex)

# Поиск вершин, с которыми связана вершина с заданным индексом
def neighbors_for_index(self, index: int) -> List[V]:
return list(map(self.vertex_at, [e.v for e in self._edges[index]]))

# Поиск индекса вершины; возвращает ее соседей (удобный метод)
def neighbors_for_vertex(self, vertex: V) -> List[V]:
return self.neighbors_for_index(self.index_of(vertex))

# Возвращает все ребра, связанные с вершиной, имеющей заданный индекс
def edges_for_index(self, index: int) -> List[Edge]:
return self._edges[index]
# Поиск индекса вершины; возвращает ее ребра (удобный метод)
def edges_for_vertex(self, vertex: V) -> List[Edge]:
return self.edges_for_index(self.index_of(vertex))

# Упрощенный красивый вывод графа
def __str__(self) -> str:
desc: str = ""
for i in range(self.vertex_count):
desc += f"{self.vertex_at(i)} -> {self.neighbors_for_index(i)}\n"
return desc

Хмм, немало всего. Как видно, большинство методов этого класса существует в 2 версиях. Из определения класса мы знаем, что список _vertices содержит элементы типа V, который может быть любым классом Python. Таким образом, у нас есть вершины типа V, которые хранятся в списке _vertices. Но если мы хотим получить эти вершины и впоследствии ими манипулировать, то нужно знать, где они хранятся в данном списке. Следовательно, с каждой вершиной в этом массиве связан индекс (целое число). Если индекс вершины неизвестен, то его нужно найти, просматривая _vertices. Именно для этого нужны 2 версии каждого метода: одна оперирует внутренними индексами, другая — самим V.

Теперь мы без проблем можем создать граф, написав что-то в духе:

city_graph: Graph[str] = Graph(["Seattle", "San Francisco", "LosAngeles", "Riverside", "Phoenix", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston", "Detroit", "Philadelphia", "Washington"])

city_graph.add_edge_by_vertices("Seattle", "Chicago")
city_graph.add_edge_by_vertices("Seattle", "San Francisco")
city_graph.add_edge_by_vertices("San Francisco", "Riverside")
city_graph.add_edge_by_vertices("San Francisco", "Los Angeles")
city_graph.add_edge_by_vertices("Los Angeles", "Riverside")
city_graph.add_edge_by_vertices("Los Angeles", "Phoenix")
city_graph.add_edge_by_vertices("Riverside", "Phoenix")
city_graph.add_edge_by_vertices("Riverside", "Chicago")
city_graph.add_edge_by_vertices("Phoenix", "Dallas")
city_graph.add_edge_by_vertices("Phoenix", "Houston")
city_graph.add_edge_by_vertices("Dallas", "Chicago")
city_graph.add_edge_by_vertices("Dallas", "Atlanta")
city_graph.add_edge_by_vertices("Dallas", "Houston")
city_graph.add_edge_by_vertices("Houston", "Atlanta")
city_graph.add_edge_by_vertices("Houston", "Miami")
city_graph.add_edge_by_vertices("Atlanta", "Chicago")
city_graph.add_edge_by_vertices("Atlanta", "Washington")
city_graph.add_edge_by_vertices("Atlanta", "Miami")
city_graph.add_edge_by_vertices("Miami", "Washington")
city_graph.add_edge_by_vertices("Chicago", "Detroit")
city_graph.add_edge_by_vertices("Detroit", "Boston")
city_graph.add_edge_by_vertices("Detroit", "Washington")
city_graph.add_edge_by_vertices("Detroit", "New York")
city_graph.add_edge_by_vertices("Boston", "New York")
city_graph.add_edge_by_vertices("New York", "Philadelphia")
city_graph.add_edge_by_vertices("Philadelphia", "Washington")
print(city_graph)

# Seattle -> ['Chicago', 'San Francisco']# San Francisco -> ['Seattle', 'Riverside', 'Los Angeles']# Los Angeles -> ['San Francisco', 'Riverside', 'Phoenix']# Riverside -> ['San Francisco', 'Los Angeles', 'Phoenix', 'Chicago']# Phoenix -> ['Los Angeles', 'Riverside', 'Dallas', 'Houston']# Chicago -> ['Seattle', 'Riverside', 'Dallas', 'Atlanta', 'Detroit']# Boston -> ['Detroit', 'New York']# New York -> ['Detroit', 'Boston', 'Philadelphia']# Atlanta -> ['Dallas', 'Houston', 'Chicago', 'Washington', 'Miami']# Miami -> ['Houston', 'Atlanta', 'Washington']# Dallas -> ['Phoenix', 'Chicago', 'Atlanta', 'Houston']# Houston -> ['Phoenix', 'Dallas', 'Atlanta', 'Miami']# Detroit -> ['Chicago', 'Boston', 'Washington', 'New York']# Philadelphia -> ['New York', 'Washington']# Washington -> ['Atlanta', 'Miami', 'Detroit', 'Philadelphia']
Большая шпаргалка по алгоритмам с собеседований.

Кстати, что это за транспортная сеть? Подсказка — что-то, связанное с 700 миль/час, пишите, кто угадал)

Алгоритмы сортировки

Ловите табличку сложности разных алгоритмов сортировки:

Большая шпаргалка по алгоритмам с собеседований.

А вот сравнение разных алгоритмов:

Большая шпаргалка по алгоритмам с собеседований.

Что ж, давайте теперь о каждом алгоритме поподробнее.

Быстрая сортировка (Quick Sort)

Как и сортировка слиянием, быстрая сортировка использует подход «Разделяй и властвуй». Алгоритм чуть сложнее, но в стандартных реализациях он работает быстрее сортировки слиянием, а его сложность в худшем случае достигает O(n^2), но это редкое явление. Quick Sort состоит из 3 этапов:

  1. Выбирается 1 опорный элемент.
  2. Все элементы меньше опорного перемещаются слева от него, остальные — направо. Это называется операцией разбиения.
  3. Рекурсивно повторяются 2 предыдущих шага к каждому новому списку, где новые опорные элементы будут меньше и больше оригинального соответственно.
Большая шпаргалка по алгоритмам с собеседований.
def partition(array, begin, end):  # разделяем массив пополам по опорному элементу
pivot_idx = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot_idx += 1
array[i], array[pivot_idx] = array[pivot_idx], array[i] array[pivot_idx], array[begin] = array[begin], array[pivot_idx] return pivot_idx

def quick_sort_recursion(array, begin, end): # рекурсивно вызываем сортировку подмассивов пока размер подмассива != 1
if begin >= end:
return
pivot_idx = partition(array, begin, end)
quick_sort_recursion(array, begin, pivot_idx-1)
quick_sort_recursion(array, pivot_idx+1, end)

def quick_sort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
return quick_sort_recursion(array, begin, end)
Большая шпаргалка по алгоритмам с собеседований.

Сортировка слиянием (Merge Sort)

Сортировка слиянием — ещё один пример использования подхода «Разделяй и властвуй». Состоит из двух этапов:

  1. Несортированный список последовательно делится на N списков, где каждый включает один «несортированный» элемент, а N — это число элементов в оригинальном массиве.
  2. Списки последовательно сливаются группами по два, создавая новые отсортированные списки до тех пор, пока не появится один финальный отсортированный список.
Большая шпаргалка по алгоритмам с собеседований.
def merge_sort(arr):
# Последнее разделение массива
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# Выполняем merge_sort рекурсивно с двух сторон
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])

# Объединяем стороны вместе
return merge(left, right, arr.copy())


def merge(left, right, merged):

left_cursor, right_cursor = 0, 0
while left_cursor < len(left) and right_cursor < len(right):

# Сортируем каждый и помещаем в результат
if left[left_cursor] <= right[right_cursor]:
merged[left_cursor+right_cursor]=left[left_cursor] left_cursor += 1
else:
merged[left_cursor + right_cursor] = right[right_cursor] right_cursor += 1

for left_cursor in range(left_cursor, len(left)):
merged[left_cursor + right_cursor] = left[left_cursor]
for right_cursor in range(right_cursor, len(right)):
merged[left_cursor + right_cursor] = right[right_cursor]
return merged
Большая шпаргалка по алгоритмам с собеседований.

Сортировка вставками (Insertion Sort)

Большая шпаргалка по алгоритмам с собеседований.

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

def insertion_sort(arr):
for i in range(len(arr)):
cursor = arr[i] pos = i

while pos > 0 and arr[pos - 1] > cursor:
# Меняем местами число, продвигая по списку
arr[pos] = arr[pos - 1] pos = pos - 1
# Остановимся и сделаем последний обмен
arr[pos] = cursor

return arr
Большая шпаргалка по алгоритмам с собеседований.

Сортировка пузырьком (Bubble Sort)

Большая шпаргалка по алгоритмам с собеседований.

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

def bubble_sort(arr):
def swap(i, j):
arr[i], arr[j] = arr[j], arr[i]
n = len(arr)
swapped = True

x = -1
while swapped:
swapped = False
x = x + 1
for i in range(1, n-x):
if arr[i - 1] > arr[i]: # если элементы стоят в неправильном порядке,
swap(i - 1, i) # то меняем их местами, пока не отсортируем arr
swapped = True
Большая шпаргалка по алгоритмам с собеседований.

Сортировка перемешиванием (шейкерная сортировка)

Большая шпаргалка по алгоритмам с собеседований.

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.

Сортировка расчёской

Большая шпаргалка по алгоритмам с собеседований.

Сортировка расчёской — очередное улучшение сортировки пузырьком. Идея в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального. Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1.247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1.247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.

Сортировка выбором (Selection Sort )

Большая шпаргалка по алгоритмам с собеседований.

На каждом i-ом шаге алгоритма находим i-ый минимальный элемент и меняем его местами с i-ым элементом в массиве. Таким образом будет получен массив, отсортированный по неубыванию.

def selection_sort(arr):        
for i in range(len(arr)):
minimum = i

for j in range(i + 1, len(arr)):
# находим наименьшее значение
if arr[j] < arr[minimum]:
minimum = j

# помещаем его перед отсортированным концом массива
arr[minimum], arr[i] = arr[i], arr[minimum]
return arr
Большая шпаргалка по алгоритмам с собеседований.

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

Алгоритм Дейкстры

Одна гифка лучше тысячи слов:

Большая шпаргалка по алгоритмам с собеседований.

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

Большая шпаргалка по алгоритмам с собеседований.

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

Псевдокод алгоритма может выглядеть так:

Большая шпаргалка по алгоритмам с собеседований.

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

Будем искать наилучший маршрут между европейскими городами Рейкьявиком и Белградом. Для простоты представим, что все города связаны дорогами (реальный маршрут должен включать как минимум один паром).

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

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

  • Reykjavik \longrightarrow Oslo \longrightarrow Berlin \longrightarrow Belgrade
  • Reykjavik \longrightarrow London \longrightarrow Berlin \longrightarrow Rome \longrightarrow Athens \longrightarrow Belgrade
  • Reykjavik \longrightarrow London \longrightarrow Berlin \longrightarrow Rome \longrightarrow Athens \longrightarrow Moscow \longrightarrow Belgrade

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

Итак, как работает алгоритм Дейкстры?

Сначала инициализируем алгоритм:

  1. Устанавливаем Рейкьявик в качестве начального узла.
  2. Устанавливаем расстояния между Рейкьявиком и всеми другими городами в ∞, за исключением расстояния между Рейкьявиком и самим собой, которое принимаем равным 0.

После этого, итеративно выполняем следующие шаги:

  1. Выбираем узел с наименьшим значением в качестве «текущего узла» и посещаем всех соседей. При посещении каждого соседа, обновляем их ориентировочное расстояние от начального узла.
  2. Как только мы посетим всех соседей текущего узла и обновили их расстояния, помечаем текущий узел как «посещенный»). Отметка узла как «посещенного» означает, что найдена его окончательная ценность.
  3. Возвращаемся к 1 шагу и повторяем до тех пор, пока не посетим все узлы графа.

В нашем примере начинаем с отметки Рейкьявика, поскольку его значение равно 0, как «текущего узла». Далее посетим два соседних узла Рейкьявика: Лондон и Осло. В начале алгоритма их значения устанавливаются на бесконечность, но, когда мы посещаем узлы, то обновляем значение для Лондона до 4 и Осло до 5.

img
img

Затем отмечаем Рейкьявик как «посещенный». Мы знаем, что его окончательная стоимость равна нулю, и нам больше не нужно его посещать. Продолжаем со следующего узла с наименьшим значением, которым является Лондон.

Посещаем все соседние узлы Лондона, которые не помечены как «посещенные». Соседи Лондона — Рейкьявик и Берлин. Но мы игнорируем Рейкьявик, потому что мы уже были в нем. Вместо этого обновляем значение Берлина, добавляя значение ребра, соединяющего Лондон и Берлин (3), к значению Лондона (4), что дает нам значение 7.

img
img

Отмечаем Лондон как посещенный и выбираем следующий узел — Осло. Посещаем соседей Осло и обновляем их ценности. Оказывается, можно лучше добраться до Берлина через Осло (со значением 6), чем через Лондон, поэтому соответствующим образом обновляем его значение. Также обновляем текущее значение Москвы с бесконечности до 8.

img
img

Отмечаем Осло как «посещенный» и обновляем его окончательное значение до 5. Между Берлином и Москвой выбираем Берлин в качестве следующего узла, потому что его значение (6) ниже, чем у Москвы (8). Действуем так же, как и раньше: посещаем Рим и Белград и обновляем их предварительные значения, прежде чем пометить Берлин как «посещенный» и перейти к следующему городу.

img
img

Обратите внимание, что мы уже нашли путь из Рейкьявика в Белград со значением 15. Но лучший ли он?

Не совсем. Опустим нахождение лучшего пути, им оказывается Рейкьявик \longrightarrow Осло \longrightarrow Берлин \longrightarrow Рим \longrightarrow Афины \longrightarrow Белград со значением 11.

Давайте наконец реализуем алгоритм Дейкстры на Python.

Класс Graph. Сначала создадим класс Graph. Этот класс не охватывает никакой логики алгоритма Дейкстры, но сделает реализацию алгоритма более лаконичной.

Реализуем граф как словарь. Ключи словаря будут соответствовать городам, а его значения будут соответствовать рёбрам, где записывают расстояния до других городов на графе:

import sys

class Graph(object):
def __init__(self, nodes, init_graph):
self.nodes = nodes
self.graph = self.construct_graph(nodes, init_graph)

def construct_graph(self, nodes, init_graph):
'''
Этот метод обеспечивает симметричность графика: если существует путь от узла A к B со значением V, должен быть путь от узла B к узлу A со значением V.
'''
graph = {}
for node in nodes:
graph[node] = {}

graph.update(init_graph)

for node, edges in graph.items():
for adjacent_node, value in edges.items():
if graph[adjacent_node].get(node, False) == False:
graph[adjacent_node][node] = value

return graph

def get_nodes(self):
"Возвращает узлы графа"
return self.nodes

def get_outgoing_edges(self, node):
"Возвращает соседей узла"
connections = [] for out_node in self.nodes:
if self.graph[node].get(out_node, False) != False:
connections.append(out_node)
return connections

def value(self, node1, node2):
"Возвращает значение ребра между двумя узлами."
return self.graph[node1][node2]

Реализация самого алгоритма. Начнем с определения функции.

def dijkstra_algorithm(graph, start_node):

Функция принимает два аргумента: graph и start_nodegraph — это экземпляр класса Graph, который мы создали на предыдущем шаге, тогда как start_node — это узел, с которого мы начнем вычисления. Мы вызовем метод get_nodes() для инициализации списка непосещённых узлов:

	unvisited_nodes = list(graph.get_nodes())

Затем создадим два словаря, shorttest_path и previous_nodes:

  • Shorttest_path будет хранить наиболее известную стоимость посещения каждого города на графике, начиная с start_node. Вначале стоимость начинается с бесконечности, но мы будем обновлять значения по мере продвижения по графику.
  • previous_nodes будет хранить траекторию текущего наиболее известного пути для каждого узла. Например, если нам известен лучший способ добраться до Берлина через Осло, previous_nodes["Берлин"] вернет «Осло», а previous_nodes[Осло] вернет «Рейкьявик». Мы будем использовать этот словарь, чтобы найти кратчайший путь.
    shortest_path = {}
previous_nodes = {}
# Мы будем использовать max_value для инициализации значения "бесконечности" непосещенных узлов
max_value = sys.maxsize
for node in unvisited_nodes:
shortest_path[node] = max_value
# Однако мы инициализируем значение начального узла 0
shortest_path[start_node] = 0

Теперь можно запустить алгоритм. Помните, что алгоритм Дейкстры выполняется до тех пор, пока не посетит все узлы в графе, поэтому представим это как условие выхода из цикла while.

	while unvisited_nodes:

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

        current_min_node = None
for node in unvisited_nodes: # Iterate over the nodes
if current_min_node == None:
current_min_node = node
elif shortest_path[node] < shortest_path[current_min_node]:
current_min_node = node

После этого алгоритм посещает всех соседей узла, которые еще не посещены. Если новый путь к соседу лучше, чем текущий лучший путь, алгоритм вносит корректировки в словари shorttest_path и previous_nodes.

        # Приведенный ниже блок кода извлекает соседей текущего узла и обновляет их расстояния.
neighbors = graph.get_outgoing_edges(current_min_node)
for neighbor in neighbors:
tentative_value = shortest_path[current_min_node] + graph.value(current_min_node, neighbor)
if tentative_value < shortest_path[neighbor]:
shortest_path[neighbor] = tentative_value
# Мы также обновляем лучший путь к текущему узлу
previous_nodes[neighbor] = current_min_node

После посещения всех его соседей мы можем пометить текущий узел как «посещенный»:

		unvisited_nodes.remove(current_min_node)

Наконец, мы можем вернуть два словаря:

	return previous_nodes, shortest_path

В итоге, весь алгоритм выглядит так:

def dijkstra_algorithm(graph, start_node):
unvisited_nodes = list(graph.get_nodes())

# Мы будем использовать этот словарь, чтобы сэкономить на посещении каждого узла и обновлять его по мере продвижения по графику
shortest_path = {}

# тут храним кратчайший известный путь к найденному узлу
previous_nodes = {}

# инициализируем max_value как ∞ для непосещенных узлов
max_value = sys.maxsize
for node in unvisited_nodes:
shortest_path[node] = max_value
# инициализируем значение начального узла как 0
shortest_path[start_node] = 0

# до тех пор, пока не посетим все узлы
while unvisited_nodes:
# находим узел с наименьшей оценкой
current_min_node = None
for node in unvisited_nodes: # Iterate over the nodes
if current_min_node == None:
current_min_node = node
elif shortest_path[node] < shortest_path[current_min_node]:
current_min_node = node

# извлекаем соседей текущего узла и обновляем их расстояния
neighbors = graph.get_outgoing_edges(current_min_node)
for neighbor in neighbors:
tentative_value = shortest_path[current_min_node] + graph.value(current_min_node, neighbor)
if tentative_value < shortest_path[neighbor]:
shortest_path[neighbor] = tentative_value
# We also update the best path to the current node
previous_nodes[neighbor] = current_min_node

# после посещения соседей отмечаем узел как "посещенный"
unvisited_nodes.remove(current_min_node)

return previous_nodes, shortest_path

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

def print_result(previous_nodes, shortest_path, start_node, target_node):
path = [] node = target_node

while node != start_node:
path.append(node)
node = previous_nodes[node]
# Add the start node manually
path.append(start_node)

print("Найден следующий лучший маршрут {}.".format(shortest_path[target_node]))
print(" -> ".join(reversed(path)))

Теперь посмотрим, как работает алгоритм. Вручную инициализируем узлы и их рёбра.

nodes = ["Reykjavik", "Oslo", "Moscow", "London", "Rome", "Berlin", "Belgrade", "Athens"] 
init_graph = {}
for node in nodes:
init_graph[node] = {}

init_graph["Reykjavik"]["Oslo"] = 5
init_graph["Reykjavik"]["London"] = 4
init_graph["Oslo"]["Berlin"] = 1
init_graph["Oslo"]["Moscow"] = 3
init_graph["Moscow"]["Belgrade"] = 5
init_graph["Moscow"]["Athens"] = 4
init_graph["Athens"]["Belgrade"] = 1
init_graph["Rome"]["Berlin"] = 2
init_graph["Rome"]["Athens"] = 2

Будем использовать эти значения для создания объекта класса Graph.

graph = Graph(nodes, init_graph)

Когда наш граф полностью построен, можно передать его функции dijkstra_algorithm().

previous_nodes, shortest_path = dijkstra_algorithm(graph=graph, start_node="Reykjavik")

А теперь распечатываем результаты:

print_result(previous_nodes, shortest_path, start_node="Reykjavik", target_node="Belgrade")

Готово!

The end

Итак, мы рассмотрели то, что с вероятностью 99% попадётся на алгособесе: асимптотический анализ, основные структуры данных, разные алгоритмы сортировки, ну и алгоритм Дейкстры как бонус.

Вообще, для полной уверенности на собеседовании, можно полистать хотя бы по диагонали вот это:

  • «Теоретический минимум по Computer Science» — Владстон Феррейра Фило, Мото Пиктет
  • конечно же «Грокаем алгоритмы» — Адитья Бхаргава

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

+1
0
+1
5
+1
0
+1
0
+1
0

Ответить

Ваш адрес email не будет опубликован. Обязательные поля помечены *