Шпаргалка по основным алгоритмам для алгоритмического собеседования
Published: 2023-12-21 13:54:28

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

## Two pointers

Смотрите, например, задачи:
[Проверка на палиндром](https://dev.to/faangmaster/provierka-na-palindrom-3e7p)
[Проверка на палиндром, усложненная версия](https://dev.to/faangmaster/provierka-na-palindrom-uslozhniennaia-viersiia-3i9p)
[Удалить n-й элемент с конца в односвязном списке](https://dev.to/faangmaster/udalit-k-eliemient-s-kontsa-v-odnosviaznom-spiskie-9gd)

## [Binary Search (Бинарный поиск)](https://dev.to/faangmaster/binarnyi-poisk-binary-search-2lje)

Для отсортированных/упорядоченных массивов.

Time complexity = O(log(n))
Space complexity = O(1)

```java
public static int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            return mid;
        }
        if (array[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}
```

## MergeSort

Time Complexity = O(n*log(n)) (Worst, Average and Best)
Space Complexity = O(n)

```java
public static int[] mergeSort(int[] array) {
    int buffer[] = new int[array.length];
    mergeSort(array, 0, array.length - 1, buffer);
    return array;
}

private static void mergeSort(int[] arr, int left, int right, int buffer[]) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, buffer);
    mergeSort(arr, mid + 1, right, buffer);
    merge(arr, left, mid, right, buffer);
}

private static void merge(int[] arr, int left, int mid, int right, int buffer[]) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] > arr[j]) {
            buffer[k++] = arr[j++];
        } else {
            buffer[k++] = arr[i++];
        }
    }
    while (i <= mid) {
        buffer[k++] = arr[i++];
    }
    while (j <= right) {
        buffer[k++] = arr[j++];
    }
    k = 0;
    for (i = left; i <= right; i++) {
        arr[i] = buffer[k++];
    }
}
```

## QuickSort (Быстрая сортировка)

Average and Best Time complexity = O(n * log(n)) 
Worst Time complexity = O(n^2)
Space complexity = O(log(n))


```java
public static int[] quickSort(int[] array) {
  sort(array, 0, array.length - 1);
  return array;
}
  
private static void sort(int arr[], int start, int end) {
    if (start > end) {
        return;
    }
    int pivot = arr[start];
    int left = start + 1;
    int right = end;
    while (left <= right) {
        if (arr[left] > pivot && arr[right] < pivot) {
            swap(arr, left, right);
            left++;
            right--;
        }
        if (arr[left] <= pivot) {
            left++;
        }
        if (arr[right] >= pivot) {
            right--;
        }
    }
    swap(arr, start, right);
    sort(arr, start, right - 1);
    sort(arr, right + 1, end);
}

private static void swap(int arr[], int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
```

## QuickSelect

Average and Best Time Complexity = O(n)
Worst Time Complexity = O(n^2)
Space Complexity = O(1)

```java
public static int quickselect(int[] array, int k) {
    int start = 0;
    int end = array.length - 1;
    while (true) {
        if (start < end) {
            swap(array, start, ThreadLocalRandom.current().nextInt(start, end));
        }
        int pivot = array[start];
        int left = start + 1;
        int right = end;
        while (left <= right) {
            if (array[left] > pivot && array[right] < pivot) {
                swap(array, left, right);
                left++;
                right--;
            }
            if (array[left] <= pivot) {
                left++;
            }
            if (array[right] >= pivot) {
                right--;
            }
        }
        swap(array, start, right);
        if (right == k - 1) {
            return array[right];
        }
        if (right > k - 1) {
            end = right - 1;
        } else {
            start = right + 1;
        }
    }
}

private static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}
```

## Trees (Деревья)

### [Алгоритмы обхода двоичных деревьев](https://dev.to/faangmaster/alghoritmy-obkhoda-dvoichnogho-dierieva-26l4)

Time complexity = O(n)
Space complexity = O(n) (Для сбалансированных деревьев O(log(n)))

**In-order** (в случае бинарных деревьев поиска (BST) обход дерева будет в порядке возрастания ключей вершин)

```java
public static void dfs(BinaryTree tree) {
    if (tree == null) {
        return;
    }
    dfs(tree.left);
    visit(tree);
    dfs(tree.right);
}
```

**Post-order**

```java
public static void dfs(BinaryTree tree) {
    if (tree == null) {
        return;
    }
    dfs(tree.left);
    dfs(tree.right);
    visit(tree);
}
```

**Pre-order**

```java
public static void dfs(BinaryTree tree) {
    if (tree == null) {
        return;
    }
    visit(tree);
    dfs(tree.left);
    dfs(tree.right);
}
```

## Trie (prefix tree)/Префиксное дерево

Основные методы класса Trie:
1) boolean contains(String str) -> Time complexity O(k), k-длина строки str, Space Complexity O(1)

Основные метода класса TrieNode:
1) void addWord(String word) -> Time complexity O(k), k - длина строки word, Space Complexity O(k)
2) boolean terminates() -> Time and space complexity O(1)
3) TrieNode getChild(char c) -> Time and space complexity O(1)

Реализация некоторых методов:

```java
public class Trie {
    ....
    public boolean contains(String str) {
        TrieNode current = root;
        for (char c : str.toCharArray()) {
            current = current.getChild(c);
            if (current == null) {
                return false;
            }
        }
        return current.terminates();
    }
}
```

## Graphs (Графы)

### [DFS (Поиск в глубину)](https://dev.to/faangmaster/dfs-depth-first-searchpoisk-v-ghlubinu-28ea)

Time complexity = O(V + E), V - число вершин, E - число ребер
Space complexity = O(V)

#### Рекурсивная реализация

```java
void dfs(Node root, Set<Node> visited) {
    if (root == null) {
        return;
    }
    visit(root);
    visited.add(root);
    for (Node neighbour : root.getNeighbours()) {
        if (!visited.contains(neighbour)) {
            dfs(neighbour, visited);
        }
    }
}
```

#### Реализация через стек

```java
void dfs(Node root) {
    if (root == null) {
        return;
    }
    Set<Node> visited = new HashSet<>();
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    visited.add(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        visit(node);
        for (Node neighbour : node.getNeighbours()) {
            if (!visited.contains(neighbour)) {
                visited.add(neighbour);
                stack.push(neighbour);
            }
        }
    }
}
```

### [BFS (Поиск в ширину)](https://dev.to/faangmaster/poisk-v-shirinu-breadth-first-search-3kaa)

Time complexity = O(V + E), V - число вершин, E - число ребер
Space complexity = O(V)

```java
void bfs(Node root) {
    if (root == null) {
        return;
    }
    Set<Node> visited = new HashSet<>();
    Queue<Node> queue = new ArrayDeque<>();
    queue.add(root);
    visited.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        visit(node);
        for (Node neighbour : node.getNeighbours()) {
            if (!visited.contains(neighbour)) {
                visited.add(neighbour);
                queue.add(neighbour);
            }
        }
    }
}
```

### [Топологическая сортировка](https://dev.to/faangmaster/topologhichieskaia-sortirovka-4eee)

Time complexity = O(V + E), V - число вершин, E - число ребер
Space complexity = O(V)

```java
public static List<Integer> topologicalSort(List<Integer> jobs, List<Integer[]> deps) {
    //Граф зависимостей
    Map<Integer, Set<Integer>> dependencies = new HashMap<>();
    //Входящие ребра
    Map<Integer, Set<Integer>> incoming = new HashMap<>();
    for (Integer task : jobs) {
        incoming.put(task, new HashSet<>());
        dependencies.put(task, new HashSet<>());
    }
    for (Integer[] dep : deps) {
        Integer from = dep[0];
        Integer to = dep[1];
        dependencies.get(from).add(to);
        incoming.get(to).add(from);
    }
    List<Integer> result = new ArrayList<>();
    List<Integer> independentTasks = null;
    do {
        //получаем список вершин, без входящих зависимостей
        independentTasks = getIndependentTasks(incoming);
        for (Integer task : independentTasks) {
            for (Integer dep : dependencies.get(task)) {
                //для каждой вершины, без входящих зависимостей
                //удаляем ребро исходящее из него
                incoming.get(dep).remove(task);
            }
            result.add(task);
            incoming.remove(task);
        }

    } while (!independentTasks.isEmpty());
    //Если incoming не пустая, то у нас цикл в графе
    return incoming.isEmpty() ? result : new ArrayList<>();
}

private static List<Integer> getIndependentTasks(Map<Integer, Set<Integer>> incoming) {
    List<Integer> result = new ArrayList<>();
    for (Integer task : incoming.keySet()) {
        if (incoming.get(task).isEmpty()) {
            result.add(task);
        }
    }
    return result;
}
```