Java. Алгоритмы и Лайв кодинг

Всем привет, ну что сегодня немного порешаем задачки по SQL - это отличный шанс проверить себя по базе:

Есть:

orders
------
id
user_id
status
amount
created_at

Найти пользователей, у которых:
- минимум 5 заказов;
- минимум 3 заказа со статусом SUCCESS;
- сумма успешных заказов > 50 000;
- последний успешный заказ был совершен в последние 30 дней.

Вывести:
- user_id
- orders_count
- success_count
- success_amount
-last_success_date

Нам будут нужны 4 агрегата:
orders_count
success_count
success_amount
last_success_date

Так как нам нужно в условии задачи найти пользователей, то мы используем GROUP BY по пользователю, после отработки у нас останется одна строка на пользователя.

Дальше мы считаем показатели внутри этой группы:
- COUNT(*) FILTER (WHERE status = 'SUCCESS') - только успешные заказы
- SUM(amount) FILTER (WHERE status = 'SUCCESS') - сумма успешных заказов
- MAX(created_at) FILTER (WHERE status = 'SUCCESS') - последний успешный заказ
- фильтруем пользователей через HAVING
HAVING COUNT(*) >= 5
AND COUNT(*) FILTER (WHERE status = 'SUCCESS') >= 3
AND SUM(amount) FILTER (WHERE status = 'SUCCESS') > 50000
AND MAX(created_at) FILTER (WHERE status = 'SUCCESS')
>= CURRENT_DATE - INTERVAL '30 days'

Получаем полный вариант:
SELECT
user_id,
COUNT(*) AS orders_count,
COUNT(*) FILTER (WHERE status = 'SUCCESS') AS success_count,
SUM(amount) FILTER (WHERE status = 'SUCCESS') AS success_amount,
MAX(created_at) FILTER (WHERE status = 'SUCCESS') AS last_success_date
FROM orders
GROUP BY user_id
HAVING COUNT(*) >= 5
AND COUNT(*) FILTER (WHERE status = 'SUCCESS') >= 3
AND SUM(amount) FILTER (WHERE status = 'SUCCESS') > 50000
AND MAX(created_at) FILTER (WHERE status = 'SUCCESS')
>= CURRENT_DATE - INTERVAL '30 days';

Всем привет! У каждого из нас есть тот самый собес. Тот, воспоминания о котором заставляют рефлекторно дергаться глаз даже спустя годы.

У меня такой был лет 10 назад. Я тогда уверенно шел на Senior Java в одну ИТишную компанию.
Итак, идет собес:
- Алгоритмы? Легко.
- Разбор многопоточности с мониторами и `volatile`? На пальцах.
- Рассказ про то, как GC эвакуирует старый обьект — вообще полжизни об этом рассказываю.

И финалочка. Фраза: "Давайте порешаем задачки по SQL"

Банальнейшая задача: *«Есть таблица заказов и пользователей. Выведите имена всех юзеров, которые никогда ничего не покупали»*.

Я, матерый джавист, смотрю на это свысока. Ну окей, думаю, сейчас я вам покажу красоту Stream API... Стоп. Мы же в базе.

SELECT u.name FROM users u
WHERE u.id NOT IN (SELECT user_id FROM orders);

Интервьюер спрашивает: «А что будет, если в колонке `user_id` хотя бы раз встретится один-единственный `NULL`?»

💀 Мой мозг Senior-разраба впал в жесткий клинч. В Java `null` бросит `NPE`, мы его боимся и прячем за `Optional`. А в SQL... в SQL предикат `NOT IN (1, 2, NULL)` всегда вернет `UNKNOWN` (ложь). ВСЕГДА. Ни одна строка не пройдет фильтр.
Мой запрос молча вернул пустоту вместо правильного ответа. Логично - оффера не было.

Тот фейл научил меня простой вещи: база данных живет по своим законам. Она не кидает эксепшены тебе в лицо, она просто возвращает неверные данные, и твой идеально спроектированный сервис падает уже где-то далеко на проде со статусом 500.

К чему я это:) думая над контентом и развитием канала и пользе от него я решил миксовать темы.

Раз в неделю здесь будут выходить посты «SQL Fridays». Будем брать классические задачи, которые дают алгоритмистам, и раскладывать их.

3. Использовать стек вместо очереди. Если случайно написать `new Stack<>()` или использовать `LinkedList` через `addFirst/pollLast`, получится DFS. Путь найдется, но он будет самым длинным и извилистым.
4. Путаница с индексацией строк и столбцов. Часто пишут `grid[col][row]` вместо `grid[row][col]`. Держите в голове: первый индекс — это скан сверху вниз (Y), второй — слева направо (X).

### Мини-чеклист для распознавания такой задачи:

* Есть поле (матрица/лабиринт)?
* У каждого хода одинаковая цена (обычно 1)?
* Вопрос звучит как «сколько минимум» или «кратчайший»?

Если три ответа «Да» — открывайте шаблон BFS.

**BFS: Уровень 2. Shortest Path (Кратчайший путь)**

Если мы читаем в условиях задачи «Найти кратчайший путь», «минимальное количество ходов», «за сколько шагов» и если каждый шаг стоит одинаково (+1), это почти всегда BFS.

### Почему здесь не работает DFS? - DFS уйдет в самую глубокую ветку слева, пройдет там до конца, вернется, упадет в следующую... это долго и не эффективно.

BFS действует иначе. Представьте таблицу `int[][] grid`, каждая клетка — это вершина графа, ребра соединяют её с соседями сверху, снизу, слева и справа, и мы двигаемся волнами.
Сначала проверяем всё на расстоянии 1 от старта, потом всё на расстоянии 2.

Идея алгоритма

1. Кладем в очередь не просто узел, а массив координат `{row, col}`.

2. Чтобы не ходить кругами, заводим массив или сет `visited` (посещенные клетки). Поставили ногу на клетку — пометили её грязной. Второй раз не наступаем.

3. Достаем позицию из очереди.

4. Смотрим на 4 соседа (вверх, вниз, влево, вправо).

5. Если сосед — стена (`#`) или уже посещен — игнорируем.

6. Если сосед — выход (`E`) — возвращаем текущую дистанцию + 1.

7. Иначе помечаем соседа как посещенный и кладем его в очередь с увеличенной дистанцией.

### Код

// Направления движения: вверх, вниз, влево, вправо
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int findShortestPath(char[][] grid) {
if (grid == null || grid.length == 0) return -1;

int rows = grid.length;
int cols = grid[0].length;

boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new ArrayDeque<>();

// Ищем точку старта S
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 'S') {
queue.offer(new int[]{r, c});
visited[r][c] = true;
}
}
}

int steps = 0;

while (!queue.isEmpty()) {
// Обрабатываем весь текущий слой целиком
int size = queue.size();

for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int row = curr[0], col = curr[1];

// Нашли выход
if (grid[row][col] == 'E') {
return steps;
}

// Проверяем соседей
for (int[] d : dirs) {
int nextRow = row + d[0];
int nextCol = col + d[1];

// Валидность: внутри границ, не стена, не были тут раньше
if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
if (!visited[nextRow][nextCol] && grid[nextRow][nextCol] != '#') {
visited[nextRow][nextCol] = true;
queue.offer(new int[]{nextRow, nextCol});
}
}
}
}
// Закончили слой — сделали один шаг
steps++;
}

// Если очередь опустела, а E не найден
return -1;
}

Разбор кода:
* Очередь объектов vs примитивов: Здесь используется `ArrayDeque<int[]>`. Это быстро и экономит память на создании кастомных классов вроде `class Cell { int x, y; }`.
* Цикл `for (int i = 0; i < size; i++)`: Самая важная деталь для задач на шаги. Мы фиксируем размер очереди в начале итерации. Все элементы, добавленные внутрь этого цикла, попадут в обработку только на следующем шаге (`steps++`).
Без этой обертки счетчик шагов будет расти слишком быстро.
* Массив `visited`: Критически важная деталь. Без него алгоритм свалится в бесконечный цикл, гоняя одну и ту же волну по кругу между двумя пустыми клетками.

Типичные ловушки новичков
1. Забыть про границы массива. Обращение к `grid[-1][0]` выбросит `ArrayIndexOutOfBoundsException`. Всегда проверяйте `nextRow >= 0 && nextRow < rows`.
2. Пометить клетку посещенной слишком поздно. Если сначала добавить в очередь, а пометить `visited` только при извлечении (`poll`), одна и та же клетка попадет в очередь десять раз от разных родителей. Очередь раздуется, сложность ухудшится.

Рассмотрим базовую задачу на поиск BFS: Binary Tree Level Order Traversal — на LeetCode это задача №102.

Дано бинарное дерево:
3
/ \
9 20
/ \
15 7
В представлении LeetCode оно задано как: root = [3,9,20,null,null,15,7]
Нужно выполнить обход дерева по уровням и вернуть значения каждого уровня отдельным списком: [[3], [9,20], [15,7]]
На вход приходит структура TreeNode, содержащая значение и ссылки на левого и правого потомка:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode() {}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
В качестве результата ожидаем:
List<List<Integer>>
Решение
1. Создадим список результатов:
List<List<Integer>> res = new ArrayList<>();
2. Проверим граничный случай — если дерево пустое, сразу возвращаем пустой результат:
if (root == null) {
return res;
}
3. Для последовательной обработки вершин нам подходит очередь. Помещаем в неё корневую вершину:
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
Подготовительные работы закончены. Теперь начинается основная логика.
4. Пока очередь не пуста, обрабатываем дерево уровень за уровнем:
while (!queue.isEmpty()) {
Но здесь есть важный момент.
В начале каждой итерации запоминаем размер очереди:
int size = queue.size();
Почему это важно?
Допустим, сейчас в очереди:
[9, 20]
Значит, текущий уровень содержит 2 вершины.
Во время их обработки мы добавим в очередь 15 и 7. Но они уже относятся к следующему уровню.
Поэтому size позволяет отделить текущий уровень от следующего.

4.1. Создаём список для значений текущего уровня:
List<Integer> level = new ArrayList<>();
4.2. Обрабатываем ровно size вершин:
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();

level.add(curr.val);

if (curr.left != null) {
queue.offer(curr.left);
}

if (curr.right != null) {
queue.offer(curr.right);
}
}
То есть при обработке: [3]
в очередь попадут: [9, 20]
На следующей итерации size = 2, поэтому обрабатываем только 9 и 20.
После этого очередь становится:
[15, 7]
И так продолжаем, пока очередь не опустеет.

5. После обработки текущего уровня добавляем его в результат:
res.add(level);
Полный код:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();

if (root == null) {
return res;
}

Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);

while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();

for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
level.add(curr.val);

if (curr.left != null) {
queue.offer(curr.left);
}

if (curr.right != null) {
queue.offer(curr.right);
}
}

res.add(level);
}

return res;
}
}
Сложность:
Время: O(n) — каждую вершину посещаем один раз.

Память: O(n) — в худшем случае очередь может содержать до n вершин.

Главная идея задачи — не просто использовать Queue, а запоминать queue.size() перед обработкой уровня. Именно это позволяет обычный BFS превратить в обход дерева по уровням.

BFS: встречается на 60% алгоритмических собеседованиях, но как научиться видеть этот алгоритм в задачах

BFS — один из тех алгоритмов, который легко понять, но сложно научиться узнавать в новых задачах.

Поэтому не будем начинать с определения, начнем с простой задачи.
Есть дерево:
1
/ \
2 3
/ \ \
4 5 6

Нужно получить значения по уровням:
1
2 3
4 5 6

Как это сделать?

Нам нужно сначала обработать 1.
Только после этого перейти к 2 и 3.
И только потом к 4, 5, 6.

То есть мы двигаемся слой за слоем - это и есть основная идея BFS.

Как это реализовать? Лучшая структура данных - очередь.
Сначала кладем туда корень:
Queue:
[1]
Достаем 1.
Добавляем его детей:
[2, 3]
Достаем 2.
Добавляем его детей:
[3, 4, 5]
Достаем 3.
Получаем:
[4, 5, 6]

И так продолжаем, пока очередь не станет пустой. Реализация на Java имеет вид:

Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Node child : current.children) {
queue.offer(child);
}
}

Что выполняет этот код:
- Создаётся очередь (интерфейс Queue) с конкретной реализацией ArrayDeque
- Очередь будет хранить узлы типа Node
- В очередь помещается корневой узел дерева (если он не null, иначе позже будет NullPointerException).
- while (!queue.isEmpty()) { Пока очередь не пуста, выполняется цикл. Это означает, что есть узлы, которые нужно посетить (offer добавляет элемент в конец очереди и возвращает true)
- Node current = queue.poll(); -Извлекается и удаляется первый элемент из очереди (голова).
- Для каждого дочернего узла текущего узла (предполагается, что у Node есть поле children — коллекция или массив) выполняется offer, т.е. все дети добавляются в конец очереди


Вот и весь базовый BFS, но как понять, что в задаче нужен BFS? Вот это гораздо важнее самого кода.

Можно выделить несколько сигналов:
1. Нужно пройти по уровням
Например, вывести дерево по уровням.→ BFS
2. Нужно найти ближайший объект
Например, найти ближайшую клетку с выходом.→ скорее всего BFS
3. Нужно найти минимальное количество шагов
Например, за сколько ходов можно попасть из точки A в точку B? Если каждый переход имеет одинаковую стоимость:
→ BFS
Почему? Потому что BFS сначала проверяет расстояние 1, потом 2, потом 3 и так далее.
Первый найденный путь будет кратчайшим.

А теперь интереснее
Допустим, у нас есть лабиринт:
S . . #
# . . #
# . . E
Нужно найти кратчайший путь от S до E.
Мы можем идти:
S
↓
1 шаг
↓
2 шага
↓
3 шага
...
BFS будет распространяться от S одновременно во все доступные стороны.
Как только дойдет до E — мы нашли минимальное количество шагов.

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

Это называется: Multi-Source BFS.
Именно так решается, например, задача Rotting Oranges.

Как учить BFS на практике?
Не нужно решать 30 одинаковых задач.
Лучше идти по нарастающей:

1. Binary Tree Level Order Traversal
Учимся самому BFS.

2. Shortest Path
BFS + расстояние.

3. Rotting Oranges
Multi-Source BFS.

4. Word Ladder
BFS по графу, которого напрямую вообще нет.

И вот здесь начинается самое интересное:
- в задаче с деревом граф очевиден
- в лабиринте граф — это клетки
- в Word Ladder граф — это возможные слова и переходы между ними.

То есть на более сложных задачах сначала нужно увидеть граф.
В следующих постах я детально разберу решение данных задач.

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

Задача: Сжатие строки (String Compression)

Условие:
Дана строка: aaabbccccdd
Необходимо сжать её, заменив последовательность одинаковых символов на: символ + количество повторений
Результат: a3b2c4d2
Если символ встречается один раз: abcd
Результат: abcd (не a1b1c1d1)

Решение:
Первый вопрос, который нужно задать - что выводить, если строка пустая или строка состоит из цифр? - по условию допускаем, что будут только буквы.
Далее идем по условию задачи:
Когда мы понимаем, что серия одинаковых символов закончилась?
Ответ простой — когда встретим другой символ

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

Алгоритм
- Проходим строку слева направо.

- Пока следующий символ совпадает с текущим — увеличиваем счётчик.

- Как только символ изменился:
записываем предыдущий символ;
если счётчик больше 1 — записываем его количество;
начинаем считать новую серию.

После цикла не забываем обработать последнюю группу символов.

public class StringCompression {

public static String compress(String s) {

if (s == null || s.isEmpty()) {
return s;
}

StringBuilder result = new StringBuilder();

int count = 1;

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) == s.charAt(i - 1)) {
count++;
} else {
result.append(s.charAt(i - 1));

if (count > 1) {
result.append(count);
}

count = 1;
}
}

result.append(s.charAt(s.length() - 1));

if (count > 1) {
result.append(count);
}

return result.toString();
}

public static void main(String[] args) {
System.out.println(compress("aaabbccccdd"));
System.out.println(compress("abcd"));
}
}

Время: O(n)
Память: O(n)
(результирующая строка)

Ну что же начинаем, пока формат тектовый, затем планирую добавлять видео с разборов.
Начнем с разбора достаточно популярной задачи:

Условие:
Дана строка s. Найти первый неповторяющийся символ и вернуть его индекс. Если такого нет — вернуть -1.

Пример вывода:
s = "leetcode" → 0 (символ 'l')
s = "loveleetcode" → 2 ('v')
s = "aabb" → -1

Пояснение алгоритма
В первую очередь при решении задач важно определить крайние точки: в нашем случае - что будет если все символы будут повторяться? - это определено в условии - нужно вернуть -1

Важно подобрать верную структуру данных: нам важно чтобы мы могли хранить справочник:
элемент - его количество
Идеально использовать мапу, но популярные HashMap и TreeMap не подходят, использовать LinkedHashMap – он запоминает порядок добавления ключей, а нам нужно первое вхождение.

Сам алгоритм не сложный:
Проходим по строке и складываем каждый символ в мапу:
ключ = символ, значение = счётчик вхождений.

Затем проходим по записям карты (в порядке первого появления) и возвращаем индекс первого символа, у которого счётчик == 1.
Сложность:
O(n) по времени, O(n) по памяти.

Теперь напишем сам код:

public class FirstUniqueChar {
public static int firstUniqChar(String s) {
Map<Character, Integer> counts = new LinkedHashMap<>();

// Шаг 1: подсчёт частот. Проходим по строке и смотри если символ уже есть в мапе прибавляем +1, если нет то добавляем со значением 1
for (char ch : s.toCharArray()) {
counts.put(ch, counts.getOrDefault(ch, 0) + 1);
}

// Шаг 2: поиск первого с частотой 1. Проходим по мапе ищем значение =1
for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
if (entry.getValue() == 1) {
return s.indexOf(entry.getKey()); // можно и хранить индекс отдельно
}
}
return -1;
}

public static void main(String[] args) {
System.out.println(firstUniqChar("leetcode")); // 0
System.out.println(firstUniqChar("loveleetcode")); // 2
System.out.println(firstUniqChar("aabb")); // -1
}
}

Частая причина провала на собесах — это не "я забыл", а "я не могу".
- не можешь написать код,
- не можешь решить задачу
- не можешь объяснить свои мысли.

Этот канал создан для того, чтобы исправить это. Здесь будут:
* Лайв-кодинг сложных задач;
* Разбор типичных ошибок;
* Тренировка навыков устного объяснения решений.

Ставь палец вверх, если тебе знакома эта боль, и подписывайся, чтобы больше никогда ее не испытывать!