Структуры данных и алгоритмы

Сеньеры рассказали, что надо знать для собеседования по теме „Структуры данных“. Примечательно, что все четверо опрошенных назвали одинаковые темы, к которым я подобрал короткие ответы. Получилось типа cheat sheet. Код не мой, источник указан либо не указан.

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

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

Массивы - используются нечасто, когда нужно достичь высокой скорости работы. Поддерживают все списковые методы - индексация, срезы, умножения, итерации и т. д. Размер и тип элемента в массиве определяется при его создании и может принимать значения int и float. Создание: (1) вложенные списки, создаются циклами и генераторами (2) import numpy as np; a = np.array([1,2,3,4,5]).

Списки - одна из из четырёх встроенных стр. д. (+ кортеж, множество, словарь). Последовательность, упорядоченный изменяемый набор элементов в [].

Деревья — вид графов. Встр. деревьев нет, но есть во внешних модулях, например collections и anytree. Можно реализовать самому.

Простейшее:

>>> T = [["a", "b"], ["c"], ["d", ["e", "f"]]]

>>> T[0][1]

'b'

>>> T[2][1][0]

'e'

Посложнее:

class Tree(object):
    def __init__(self):

        self.left = None

        self.right = None

        self.data = None

root = Tree()

root.data = "root"

root.left = Tree()

root.left.data = "left"

root.right = Tree()

root.right.data = "right"

Двоичное дерево поиска - У каждого узла не более двух потомков. Любое значение меньше значения узла становится левым потомком или потомком левого потомка.

Любое значение больше или равное значению узла становится правым потомком или потомком правого потомка.

Очереди — коллекция, устроенная по принципу FIFO. Пример — буфер. Также существует часто используемая двухсторонняя очередь.

Стек — коллекция устроенная по принципу LIFO. Есть доступ только к последнему элементу. Нет итератора и методов списка, только push и pop. Стек и очередь можно переделать из стандартного списка, переопределив методы.

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

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

Обычно все операции выполняются за время О(1), т. е. очень быстро.

Алгоритмы сортировки — метод пузырька, сортировка Хоара (quick sort), сортировка слиянием. Необходимо понимание и способность объяснить, как работает каждый из алгоритмов.Код для трёх первых алгоритмов взят тут, там же хорошая визуализация.

Сортировка выбором

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

def ssort(array):

    for i in range(len(array)):

        indxMin = i

        for j in range(i+1, len(array)):

            if array[j] < array[indxMin]:

                indxMin = j

                tmp = array[indxMin]

                array[indxMin] = array[i]

                array[i] = tmp

    return a

Метод пузырька

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

def bubble_sort(array):

    a = array

    for i in range(len(a),0,-1):

        for j in range(1, i):

            if a[j-1] > a[j]:

                tmp = a[j-1]

                a[j-1] = a[j]

                a[j] = tmp

                print a

    return a

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

Выбирается опорный элемент, относительно которого будет происходит сортировка. Равные и бОльшие элементы помещаются справа, меньшие – слева. Затем к полученным подмассивам рекурсивно применяются два первых пункта.

def QuickPas(s, aL, aR):

    l, r=aL, aR

    mid = (s[l]+s[(l+r)/2]+s[r])/3

    while lmid:
        r-=1

            if l<=r:

                if s[l]>s[r]:

                    s[l], s[r] = s[r], s[l]

                    l+=1

                    r-=1

    if r>aL:
        QuickPas(s, aL, r)

    if l<aR:
        QuickPas(s, l, aR)

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

Это рекурсивный алгоритм, который постоянно разбивает список пополам. Если список пуст или состоит из одного элемента, то он отсортирован (базовый случай). Если длина списка>1, мы разбиваем его и рекурсивно вызываем сортировку слиянием для каждой из половин. После того как они отсортированы, выполняется слияние - комбинирование двух меньших сортированных списков в один новый, но тоже отсортированный.

def mergeSort(alist):

    print("Splitting ",alist)

    if len(alist)>1:

        mid = len(alist)//2

        lefthalf = alist[:mid]

        righthalf = alist[mid:]

        mergeSort(lefthalf)

        mergeSort(righthalf)

        i=0

        j=0

        k=0

        while i<len(lefthalf) and j<len(righthalf):

            if lefthalf[i]<righthalf[j]:

                alist[k]=lefthalf[i]

                i=i+1

            else:

                alist[k]=righthalf[j]

                j=j+1

                k=k+1

        while i<len(lefthalf):

            alist[k]=lefthalf[i]

            i=i+1

            k=k+1

        while j<len(righthalf):

            alist[k]=righthalf[j]

            j=j+1

            k=k+1

    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

Алгоритмы поиска — линейный и бинарный (метод деления пополам).

Линейный (последовательный) поиск является простейшим алгоритмом поиска и не накладывает никаких ограничений на функцию, имеет простейшую реализацию. Oсуществляется сравнением очередного значения и, если значения совпадают, то считается завершённым.

def linearSearch(li, x):

    i = 0

    length = len(li)

    while i<length and x<> li[i]:

        i+=1

    return i if i<length else None

Двоичный (бинарный) поиск классический алгоритм поиска элемента в отсортированном массиве (векторе).

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

1. Находится средний элемент последовательности.

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

3. Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.

4. Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется.

Переменные i и j содержат, соответственно, левую и правую границы отрезка массива, где находится нужный элемент.

def BinSearch(li, x):

    i = 0

    j = len(li)-1

    m = int(j/2)

    while li[m] != x and i < j:

        if x > li[m]:

             i = m+1

        else:

            j = m-1

        m = int((i+j)/2)

    if i > j:

        return 'Нет такого'

    else:

         return m

Сложность алгоритмов и стандартных операций (доступ, вставка, удаление, поиск элементов) структур данных.

Наглядные картинки

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

Вводится понятие 'мат. нотации', в данном случае 'О большое'.
Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n).
Выглядит как таблица, где по вертикали структуры данных (например - массив, стек, очередь), а по вертикали виды операций (например - доступ, поиск, вставка), а в ячейках их сложность (например - О(1), O(n), O(log(n)). 
Также может быть таблицей, где по вертикали стоит 'сложность' (n, n^2, n^3, n^5, 2^n, 3^n), а по горизонтали 'размер' (10, 20, 30).

O(1) - константный алгоритм (т.е. сложность не зависит от размера данных)
O(n) - линейная сложность
O(log n) - логарифмическая сложность
O(n^2) - квадратичная сложность
и т.д.

Также есть понятия 'лучшего', 'среднего' и 'худшего' сценариев.