faangmaster

Posted on Dec 21, 2023

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

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

Two pointers

Смотрите, например, задачи:
Проверка на палиндром
Проверка на палиндром, усложненная версия
Удалить n-й элемент с конца в односвязном списке

Binary Search (Бинарный поиск)

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

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

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)

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))

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)

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 (Деревья)

Алгоритмы обхода двоичных деревьев

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

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

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

Post-order

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

Pre-order

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)

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

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 (Поиск в глубину)

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

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

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);
        }
    }
}

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

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 (Поиск в ширину)

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

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);
            }
        }
    }
}

Топологическая сортировка

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

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;
}

DEV Community

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

Two pointers

Binary Search (Бинарный поиск)

MergeSort

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

QuickSelect

Trees (Деревья)

Алгоритмы обхода двоичных деревьев

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

Graphs (Графы)

DFS (Поиск в глубину)

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

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

BFS (Поиск в ширину)

Топологическая сортировка

Top comments (0)

Read next

Idea: Make Apache Flight (gRPC) work over HTTP/3 (QUIC) and make use of RDMA (fast memory transfer). All made in Rust

Test Cases: A Comprehensive Guide

Hello World from PodExtra

Migrating from nvm to mise