DEV Community

faangmaster
faangmaster

Posted on

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

Данная шпаргалка включает все основные алгоритмы, необходимые для успешного прохождения собеседования по решению алгоритмических задач. Данная статья не включает детальный разбор этих алгоримов, а лишь реализации на языке 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;
}
Enter fullscreen mode Exit fullscreen mode

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++];
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

Post-order

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

Pre-order

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

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();
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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

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);
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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

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;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Read next

anshul_kichara profile image

Quantum Computing : What’s the Buzz All bout

Anshul Kichara -

jetthoughts_61 profile image

Who is to blame when a project fails?

JT Dev -

saim_ansari profile image

Learn how to use x-show in AlpineJS

saim -

josmel profile image

Exploring the New Frontier: ChatGPT-4o Unveiled

Josmel Noel -