Skip to content

Latest commit

 

History

History
205 lines (142 loc) · 28.6 KB

algorithms.md

File metadata and controls

205 lines (142 loc) · 28.6 KB
Raw

Вопросы для собеседования

Алгоритмы

Big O

Концепция Big O показывает, какое количество шагов (тактов процессора) необходимо сделать, чтобы полностью завершить алгоритм.

Big O показывает верхную границу зависимости между входными параметрами функции и количеством операций, которые выполнит процессор. Т.е. описывается только скорость роста функции. Если алгоритм описывается как O(2N), он все равно будет O(n), посколько константы можно отбросить. Не важно, сколько раз будет повторятся алгоритм - бесконечность (n) или две бесконечности (2n) - это все равно будет бесконечность.

Концепция Big O помогает видеть и исправлять неоптимальный код.

   
время
   .          
  / \       /
   |       /
   |      /  O(n)
   |     /
   |    /
   |   /
   |  /
   |-/------------------- O(1)
   |/
   |
   o——————————————————> 
                кол-во бит

O(n) - Больше байт - дольше передавать. Зависимость от количества элементов. В функции это кол-во вызовов функции внутри себя

О(1) - Размер файла не важен, скорость постоянна

Рекурсивная функция: функция вызывает сама себя. Чем больше n, тем больше раз функция вызовет сама себя.

int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}

Линейная функция: кол-во выполнений функции зависит от n.

int pairSunSequence(int n) {
    int sum = 0:
    for (int i = 0; i < n; i++) {
        sum += pairSum(i, i + 1);
    }
    return sum;
}

int pairSum(int a, int b) {
    return a + b;
}

Отбрасывание неважной сложности: если одно значение n значительно (в 2 раза) меньше другого значения n^2, то меньшуу n можно отбросить, т.к. она слабо влияет на рост скорости фукнции.

O(n^2 + n) = O(n^2)

O(n + log n) = O(n), т.к log(n) меньше n

O(5 * 2^n + 10 * n^100) = O(2^n)

O(n^2 + b) = O(n^2 + b), мы не может упростить, пока ничего не знаем о b. Оно может быть <, > или = n

Сложение и умножение сложностей: Если функции вызываются последовательно, то сложности складываются (они не зависят друг от друга). Если функции выполняются одна в другой (зависят друг от друга) то сложности умножаются.

Log n - для алгоритма, где на каждой итерации берется половина элементов - сложность будет включать O(log n).

ArrayList vs LinkedList

Класс        Получение    Поиск     Вставка     Удаление

ArrayList       O(1)       O(n)   O(n) / O(1)      O(n)
LinkedList      O(n)       O(n)       O(1)         O(1)

ArrayList реализован внутри в виде обычного массива. Поэтому при вставке элемента в середину, приходится сначала сдвигать на один все элементы после него, а уже затем в освободившееся место вставлять новый элемент. ОДНАКО вставка в конец списка в среднем производится так же за постоянное время. В среднем потому, что массив имеет определенный начальный размер n (в коде это параметр capacity), по умолчанию n = 10, при записи n+1 элемента, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент. В итоге получаем, что при добавлении элемента при необходимости расширения массива, время добавления будет значительно больше, нежели при записи элемента в готовую пустую ячейку. Удаление последнего элемента происходит за константное время.

Зато в нем быстро реализованы взятие и изменение элемента – операции get, set, так как в них мы просто обращаемся к соответствующему элементу массива.

LinkedList реализован в виде двусвязного списка: набора отдельных элементов, каждый из которых хранит ссылку на следующий и предыдущий элементы. Чтобы вставить элемент в середину такого списка, достаточно поменять ссылки его будущих соседей. А вот чтобы получить элемент с номером 130, нужно пройтись последовательно по всем объектам от 0 до 130. Другими словами операции set и get тут реализованы очень медленно.

Если вставлять (или удалять) в середину коллекции много элементов, то лучше использовать LinkedList. Во всех остальных случаях – ArrayList. LinkedList занимает в памяти разрозненные ячейки, а значения ArrayList в памяти хранятся единым массивом.

Устройство HashMap

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

Внутри HashMap содержатся массив Bucket (по умолчанию их 16, коэфицент заполнения 0,75 - указывает, когда нужно увеличить массив бакетов). Они используется для хранения узлов (Nodes). Два или более узла могут иметь один и тот-же bucket.

Node представляет класс, содержащий следующие объекты:

  • int — хэш
  • K — ключ
  • V — значение
  • Next — следующий элемент

При добавление ключ-значения в хешмапу проверяем существует ли ключ. Если ключ не существует (null), значение помещается в таблицу на нулевую позицию, потому что хеш-код для значения null, это – всегда 0. Дальше высчитывается хеш-код ключа. Ключ делится на количество бакетов, остаток от деления будет номером бакета, куда кладется этот ключ-значение. Ключ-значение оборачивается в Node. Если Node добавляется в бакет, в котором уже есть другая Node, они сравнивают ключи по hashCode() и equals(). Если ключи идентичны - перезаписываются, если нет - новая Node добавляется в начало цепочки и в ней создается ссылка на старую Node и они образуют односвязный список. При этом если Node будут записываться только в один бакет, хешмапа выродится в связный список.

Изменения в Java 8 Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных "связанный список" и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n). Для исправления этой проблемы в Java 8 после достижения определенного порога (если в бакете >= 7 эелементов, а самих бакетов меньше 64. иначе вместо перехода к древовидной структуре будет вызван метод resize() для увеличения размера хеш-таблицы с перераспределением элементов.) Вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).

В итоге

  • Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки;
  • Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n) (все элементы в одной цепочке);

Рекурсия

Рекурсия - метод вызывает сам себя, но может вернуть код другого выражения. Не использует стек.

Хвостовая рекурсия - метод возвращает только сам себя. Используется стек.

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

Рекурсия vs Iterator

Итератор - реализация класса, рекурсия - реализация методом. Итерируем пока не закончится весь список данных, рекурсия существует пока вызывает сама себя.

Рекурсивный метод работает FILO, а итератор FIFO.

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

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

Виды сортировок и их сравнение

Быстрая сортировка - Выбирает из массива элемент, называемый опорным. Это может быть любой из элементов массива. Сравнивает все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на два непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные и большие». Для отрезков «меньших» и «больших» значений выполняет рекурсивно ту же последовательность операций, пока длина отрезка больше единицы. Сложность алгоритма: в среднем O(n log n), в худшем O(n^2)

Сортировка пузырьком - простейший, но эффективен он лишь для небольших массивов. Сложность O(n^2). Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются {\displaystyle N-1}N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).

Шейкерная сортировка - аналогична пузырьковой, но при движении от конца массива к началу минимальный элемент «всплывает» на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо. Кроме того, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, её можно исключить из рассмотрения. Сложность O(n^2)

Сортировка выбором - поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка. Сложность O(n^2)

Сортировка вставками - элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Сложность O(n^2)

Гномья сортировка - похожа на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Сложность O(n^2)

Сортировка слиянием - упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе. Сложность алгоритма:O(n log n)

Виды поиска и их сравнение

Линейный - перебор всех значений. O(n)

Бинарный (двоичный) - берем средний элемент из массива. Если искомый элемент не равен этому среднему, продолжаем поиск - если искомый элемент меньше, идем в левую половину массива, если искомый больше - идем в правую половину O(log n). Там тоже берем средний элемент и сравниваем с искомым. И так до тех пор, пока не найдем искомый элемент или пока не останется последний элемент массива. Если последний элемент не равен искомому, то искомого элемента в данном массиве не существует.

Поиск в ширину - описывается итератором: метод обхода дерева, при котором поиск ведется по линии "ширине", то есть сначала вершина дерева, потом все эелементы слева направо на втором уровне, потом на третьем и т.д.

Поиск в глубинну - описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Идем от вершины по ветке д осамого конца, затем проверяем все ответления в ветке снизу в верх. Если вернулись к вершине - перебираем следующую ветку.

Алгоритм Кнута-Морриса-Пратта - поиск подстроки в строке. Создается шаблон, по которому ищется подстрока по префиксу и суфиксу. Время работы алгоритма линейно зависит от объёма входных данных.

Даны образец (строка) S и строка T. Требуется определить индекс, начиная с которого образец S содержится в строке T. Если S не содержится в T — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число).

Префикс-функция(количество повторений) для строки "abcabcd" равна: [0, 0, 0, 1, 2, 3, 0], что означает:

  • у строки "a" нет нетривиального префикса, совпадающего с суффиксом;
  • у строки "ab" нет нетривиального префикса, совпадающего с суффиксом;
  • у строки "abc" нет нетривиального префикса, совпадающего с суффиксом;
  • у строки "abca" префикс длины 1 совпадает с суффиксом;
  • у строки "abcab" префикс длины 2 совпадает с суффиксом;
  • у строки "abcabc" префикс длины 3 совпадает с суффиксом;
  • у строки "abcabcd" нет нетривиального префикса, совпадающего с суффиксом.

Жадный алгоритм

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

Queue, Deque, Stack, Heap

Queue (очередь) - предназначена для хранения элементов с предопределённым способом вставки и извлечения FIFO (first-in-first-out). PriorityQueue — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering»

Deque (Double Ended Queue) расширяет Queue и согласно документации это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO. ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out)

Stack - предназначена для хранения элементов с предопределённым способом вставки и извлечения FILO, First-In-Last-Out («первым пришел, последним ушел»)

EnumSet

EnumSet - это реализация интерфейса Set для использования с перечислениями (Enum). В структуре данных хранятся объекты только одного типа Enum, указываемого при создании. Для хранения значений EnumSet использует массив битов (bit vector), - это позволяет получить высокую компактность и эффективность. Проход по EnumSet осуществляется согласно порядку объявления элементов перечисления.

Все основные операции выполняются за O(1) и обычно (но негарантированно) быстрей аналогов из HashSet, а пакетные операции (bulk operations), такие как containsAll() и retainAll() выполняются даже горазда быстрей.

Помимо всего EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров.

Бинарное дерево

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

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

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

Красно-черное дерево

Вид бинарных деревьев, у которых присутствует балансировка - за счет дополнительного атрибута - цвета. Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный». КЧД реализованны в TreeMap, TreeSet. При этом:

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

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

Мемоизация

Сохранение результатов выполнения функций для предотвращения повторных вычислений. Перед вызовом функции проверяется, вызывалась ли функция ранее: если не вызывалась, то функция вызывается, и результат её выполнения сохраняется; а если вызывалась, то используется сохранённый результат.