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