Профессия:
Задачи с собеседований на Java-разработчика: Stream API и Collectors, многопоточность с AtomicInteger и BlockingQueue, воспроизведение deadlock, коллекции и ConcurrentModificationException, equals и hashCode, LRU-кеш, алгоритмы на строках и массивах. У каждой задачи есть разбор с рабочим кодом.
Подсчёт частоты слов с Stream API
Это классическая задача на собеседовании, которая проверяет понимание Stream API, особенно groupingBy() коллектора.
Решение
import java.util.Map;
import java.util.stream.Collectors;
import java.util.Arrays;
public class WordFrequency {
public static void main(String[] args) {
String text = "java is great and java is fun";
Map<String, Long> frequency = Arrays.stream(text.split(" "))
.map(String::toLowerCase)
.collect(Collectors.groupingBy(
word -> word,
Collectors.counting()
));
System.out.println(frequency);
// Вывод: {java=2, is=2, and=1, great=1, fun=1}
}
}
Разбор решения пошагово
text.split(" ") // Массив строк
// ["java", "is", "great", "and", "java", "is", "fun"]
Найти ошибку: иерархия catch блоков
Этот вопрос проверяет понимание иерархии исключений в Java и правил обработки исключений. Это очень распространенная ошибка, которую делают начинающие разработчики.
Анализ проблемы
1. Скомпилируется ли этот код?
Нет, этот код НЕ скомпилируется. Компилятор Java выдаст ошибку:
error: exception FileNotFoundException has already been caught
2. Почему это происходит?
Проблема в иерархии исключений. FileNotFoundException является подклассом IOException:
Throwable
└─ Exception
└─ IOException
└─ FileNotFoundException
Когда catch блок ловит IOException, он ловит все исключения, которые являются IOException или его подклассами. Это включает и FileNotFoundException.
Поэтому второй catch блок для FileNotFoundException никогда не будет достигнут — он "недостижимый код" (unreachable code).
Визуализация проблемы
ConcurrentModificationException при итерации ArrayList
Ответ
Программа выбросит: ConcurrentModificationException
Почему возникает исключение?
Это происходит из-за механизма fail-fast итератора, встроенного в ArrayList. Когда вы изменяете размер списка во время итерации, итератор обнаруживает это и выбрасывает исключение.
Как это работает под капотом
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
for (String s : list) { // for-each использует итератор
if (s.equals("b")) {
list.add("d"); // ОШИБКА! Модифицируем список напрямую
}
}
// java.util.ConcurrentModificationException
Внутреннее представление
// Примерно вот что происходит при for-each:
Iterator<String> iterator = list.iterator();
int modCount = list.modCount; // Сохраняем начальное значение
Two Sum: нахождение двух чисел с заданной суммой
Суть задачи
Это классическая задача на хеширование и поиск. Нужно найти два элемента массива, которые в сумме дают целевое число, и вернуть их индексы.
Подходы решения
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{}; // нет решения
}
Сложность: O(n²) — очень медленно при больших массивах.
Идея: Проходим массив один раз. Для каждого числа проверяем, есть ли в HashMap число, которое в сумме с текущим даст target.
Подход
Итерируем от 1 до 100. Для каждого числа проверяем делимость: сначала на 15 (FizzBuzz), затем на 3 (Fizz), затем на 5 (Buzz), иначе выводим само число. Порядок проверки важен.
Решение
Потокобезопасный счётчик с AtomicInteger
Проблема обычного int++ в многопоточной среде
Операция counter++ выглядит как одна команда, но на самом деле это три операции:
// counter++; эквивалентно:
int temp = counter; // 1. Читаем значение (READ)
temp = temp + 1; // 2. Увеличиваем (COMPUTE)
counter = temp; // 3. Записываем (WRITE)
Проблема: race condition
Когда несколько потоков выполняют эти операции одновременно:
Поток 1: READ(100) -> COMPUTE(101) -> WRITE(101)
Поток 2: READ(100) -> COMPUTE(101) -> WRITE(101)
Поток 3: READ(100) -> COMPUTE(101) -> WRITE(101)
Желаемый результат: 103
Фактический результат: 101 (потеряли 2 инкремента!)
Это потому, что все потоки прочитали значение 100 перед тем, как кто-то его изменил.
Решение 1: synchronized
Реализация простого REST API с Spring Boot
Это задача, которая проверяет владение Spring Boot и умение создавать производственный код с правильной обработкой ошибок, валидацией и правильными HTTP статусами.
Структура проекта
src/main/java/
├── com.example.todo/
│ ├── controller/
│ │ └── TodoController.java
│ ├── service/
│ │ └── TodoService.java
│ ├── repository/
│ │ └── TodoRepository.java
│ ├── entity/
│ │ └── Todo.java
│ ├── dto/
│ │ ├── CreateTodoRequest.java
│ │ ├── UpdateTodoRequest.java
│ │ └── TodoResponse.java
│ └── Application.java
1. Сущность Todo
package com.example.todo.entity;
import jakarta.persistence.*;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
Определить цикл в LinkedList
Это классическая задача на определение цикла в связном списке. Её часто задают на собеседованиях, так как она требует понимания работы указателей и демонстрирует элегантное решение через алгоритм Флойда (Floyd's Cycle Detection).
Алгоритм Флойда: "Черепаха и заяц"
Идея очень простая: используем два указателя, которые движутся по списку с разной скоростью:
Если в списке есть цикл, эти два указателя в конце концов встретятся. Если список заканчивается (fast или fast.next становится null), цикла нет.
Структура ListNode
public class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
Решение: определение наличия цикла
Подход
Используем арифметические операции для обмена значений без вспомогательной переменной. При сложении и вычитании сохраняем информацию о обеих значениях в одной переменной.
Решение
Проверка на анаграмму в Java
Объяснение задачи
Анаграмма — это слово или фраза, составленные из тех же букв, что и исходное слово, но в другом порядке. Например, "listen" и "silent" содержат одинаковый набор букв: l, i, s, t, e, n.
Решение 1: С использованием массива (O(n))
Это оптимальное решение по времени. Подсчитываем частоту каждого символа:
public class AnagramChecker {
public static boolean isAnagram(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
int[] charCount = new int[26];
for (int i = 0; i < str1.length(); i++) {
charCount[str1.charAt(i) - 'a']++;
charCount[str2.charAt(i) - 'a']--;
}
for (int count : charCount) {
if (count != 0) {
return false;
}
}
return true;
}
}
Решение 2: С HashMap (более универсальное)
Подход
Одновременно отслеживаем первое и второе наибольшее число при проходе по массиву. За один проход обновляем обе переменные, учитывая повторяющиеся значения. Используем Integer.MIN_VALUE для инициализации.
Решение
Stream API: фильтрация, сортировка и сбор данных
Это классическая задача, демонстрирующая мощь Stream API в Java для функционального преобразования данных. Давайте разберёмся пошагово.
Полное решение в одну цепочку
List<String> topNames = employees.stream()
.filter(emp -> emp.age > 30) // шаг 1: фильтрация
.sorted(Comparator.comparingDouble(Employee::getSalary).reversed()) // шаг 2: сортировка
.limit(3) // шаг 3: топ-3
.map(emp -> emp.name) // шаг 4: извлечение имён
.collect(Collectors.toList()); // шаг 5: сбор в список
Полный рабочий пример
import java.util.*;
import java.util.stream.Collectors;
Бинарный поиск
Суть алгоритма
Бинарный поиск — это быстрый алгоритм поиска элемента в отсортированном массиве за O(log n). Работает по принципу деления промежутка пополам.
Как работает
Итеративная реализация
Подход
Проходим по строке, подсчитываем частоту каждого символа с помощью HashMap. Затем фильтруем результат, оставляя только символы с частотой больше 1. Выводим в порядке убывания частоты.
Решение
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;
Deadlock: воспроизведение и решение
Deadlock — это ситуация, когда два или более потока ждут друг друга бесконечно, так как каждый удерживает ресурс, который нужен другому. Это один из самых коварных багов в многопоточных приложениях — он может не проявляться месяцами, а затем неожиданно заморозить систему.
1. Воспроизведение Deadlock
Producer-Consumer паттерн с BlockingQueue
Это один из самых важных паттернов для многопоточного программирования. BlockingQueue автоматически управляет синхронизацией между производителями и потребителями.
Основное решение
import java.util.concurrent.*;
public class ProducerConsumerExample {
private static final int QUEUE_SIZE = 10;
private static final int ITEMS_TO_PRODUCE = 100;
private static final Integer POISON_PILL = -1; // Сигнал завершения
public static void main(String[] args) throws InterruptedException {
// Ограниченная очередь размером 10
BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(QUEUE_SIZE);
// ExecutorService для управления потоками
ExecutorService executorService = Executors.newFixedThreadPool(3);
try {
// Запуск 1 Producer
executorService.submit(new Producer(queue, ITEMS_TO_PRODUCE));
Подход
Разделяем строку на слова, приводим их к нижнему регистру и подсчитываем частоту каждого слова с помощью HashMap. Используем метод getOrDefault() для элегантного обновления счётчика.
Решение
import java.util.HashMap;
import java.util.Map;
Реализация LRU Cache
Объяснение задачи
LRU Cache (Least Recently Used) — это кэш, который автоматически удаляет наименее недавно используемый элемент при достижении максимальной ёмкости.
Основные операции:
get(key) — O(1) получить значениеput(key, value) — O(1) добавить/обновитьРешение 1: LinkedHashMap (элегантное и простое)
LinkedHashMap поддерживает режим access-order:
import java.util.LinkedHashMap;
import java.util.Map;
Найти i-й элемент с конца LinkedList за один проход
Это классическая задача, которая проверяет понимание работы с указателями и оптимизацию алгоритмов. Ключ к решению — использование двух указателей с фиксированным расстоянием между ними.
Подход: Two Pointers (Два указателя)
Идея в том, что мы используем медленный и быстрый указатели с расстоянием в i элементов между ними.
Алгоритм:
Полное решение с обработкой ошибок
Преобразование строки в целое число без parseInt()
Это классическая задача на собеседованиях, которая проверяет понимание работы с символами, обработку исключений и граничные случаи. Решение требует реализации алгоритма парсинга с нуля.
Пошаговый алгоритм
Основное решение
Угол между стрелками часов
Это интересная геометрическая задача, которая часто встречается на собеседованиях. Ключ к решению — понимание того, как движутся часовая и минутная стрелки.
Основные принципы
Минутная стрелка:
minutes * 6Часовая стрелка:
(hours % 12) * 30 + minutes * 0.5Угол между стрелками:
|minuteAngle - hourAngle|360 - angleРешение
Произведение элементов массива кроме текущего
Это классическая задача, требующая логического мышления и оптимизации. Запрет на деление усложняет задачу, но открывает возможность использования префиксного и суффиксного произведения.
Решение 1: Префиксное и суффиксное произведение — O(n) время, O(n) память
Основная идея: для каждого элемента вычислить произведение всех элементов слева и произведение всех элементов справа, затем перемножить их.
Сравнение строк: == vs equals()
Это один из самых частых вопросов на собеседованиях Java-разработчиков, и ответ требует глубокого понимания того, как Java работает со строками. Давайте разберёмся с примерами.
Результаты выполнения кода
String s1 = "Hello";
String s2 = "Hello";
String s3 = new String("Hello");
String s4 = new String("Hello");
System.out.println(s1 == s2); // true ✅
System.out.println(s1 == s3); // false ❌
System.out.println(s1.equals(s3)); // true ✅
System.out.println(s3 == s4); // false ❌
System.out.println(s3.equals(s4)); // true ✅
Почему такие результаты?
s1 == s2 → trueОбе переменные указывают на один и тот же объект в String Pool:
┌─────────────────────────┐
│ String Pool (Heap) │
├─────────────────────────┤
│ "Hello" (объект) │◄─── s1
└─────────────────────────┘ s2
Удаление дубликатов из отсортированного массива на месте
Эта классическая задача на two-pointer техники демонстрирует, как эффективно работать с отсортированными данными. Ключевая идея — использовать два указателя: один для позиции записи, другой для сканирования массива.
Основная идея
Так как массив отсортирован, все дубликаты расположены рядом:
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
↑ ↑ ↑ ↑ ↑ ↑
дубликаты находятся рядом
Мы используем:
Алгоритм:
Решение
Поворот массива на K позиций
Объяснение задачи
Нужно повернуть массив вправо на k позиций на месте (in-place), без использования дополнительной памяти.
Пример: [1, 2, 3, 4, 5, 6, 7] при k=3 становится [5, 6, 7, 1, 2, 3, 4]
Решение 1: Метод трёх разворотов (самое оптимальное)
Идея: развернуть три части массива в определённом порядке:
Поиск максимальной прибыли от акций
Это одна из самых популярных задач на собеседованиях. Ее красота в простоте подхода и эффективности: одиночный проход по массиву дает оптимальное решение.
Решение 1: Однопроходный алгоритм — O(n) время, O(1) пространство
Основная идея: отслеживаем минимальную цену, встреченную до текущего момента, и вычисляем прибыль для текущей цены.
Реализация структуры данных Stack
Стек — это одна из фундаментальных структур данных в компьютерной науке. Он используется везде: от обработки выражений и алгоритмов рекурсии до undo-функций в текстовых редакторах. Рассмотрим две основных реализации: на основе массива и на основе связного списка.
Stack на основе массива (ArrayList)
import java.util.ArrayList;
Подход
Преобразуем строку в нижний регистр, удаляем все не-буквенные символы и пробелы. Затем используем двойной указатель для проверки с обоих концов - если символы совпадают до середины, это палиндром.
Решение
Проверка сбалансированности бинарного дерева
Сбалансированное бинарное дерево (Balanced Binary Tree) — это дерево, в котором для каждого узла разница в глубинах между левым и правым поддеревьями не превышает 1.
Определение структуры узла
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
Основное решение (рекурсивное)
Минимальный неблокирующий стек на AtomicReference
Эта задача требует создания lock-free структуры данных с использованием атомарных операций для безопасной работы в многопоточной среде без явных блокировок.
Основные концепции
Lock-free означает, что потоки не блокируют друг друга явно (synchronized, lock). Вместо этого используется optimistic locking с помощью Compare-And-Set (CAS) операций.
CAS операция:
Реализация Lock-Free стека
import java.util.concurrent.atomic.AtomicReference;
Поиск максимальной подстроки-палиндрома
Это классическая задача из категории строковых алгоритмов, которая требует рассмотрения нескольких подходов. Ключ к решению — понимание того, что палиндромы бывают нечетной и четной длины.
Решение 1: Расширение от центра — O(n²) время, O(1) пространство
Основная идея: для каждой возможной позиции центра разверните палиндром во все стороны.
Извлечение имён из массива объектов
Суть задачи
Преобразовать массив объектов Person в массив строк (имён). Это базовая операция трансформации данных, которая в Java решается несколькими способами.
Определение класса Person
public class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
Способ 1: Традиционный цикл for
Подход
Реализуем три варианта: рекурсивный (базовый), рекурсивный с мемоизацией (оптимизированный) и итеративный (самый эффективный). Для рекурсии используем Map для кеширования результатов.
Решение
import java.util.HashMap;
import java.util.Map;
Реализация equals() и hashCode()
Это один из самых важных контрактов в Java — правильная реализация equals() и hashCode() критична для корректной работы с коллекциями, особенно с HashMap и HashSet.
Правильная реализация
import java.util.Objects;
Потокобезопасный Singleton с double-checked locking
1. Есть ли проблема в исходном коде?
ДА, ЕСТЬ СЕРЬЁЗНАЯ ПРОБЛЕМА! Код содержит классическую ошибку инициализации, связанную с переупорядочением инструкций компилятором и процессором.
Проблема в следующем:
При выполнении instance = new Singleton(); происходит несколько шагов:
instanceОднако из-за оптимизаций компилятора и CPU, шаги 2 и 3 могут быть переупорядочены. Это означает, что instance может быть установлена на объект ДО завершения его инициализации.
Сценарий критической ошибки:
Поток 1:
1. Вошёл в synchronized блок
2. Выделил память для объекта
3. Установил instance (ОШИБКА: ещё не инициализирован!)
4. Инициализирует объект
Предсказать вывод: передача строки в метод
Ответ
Программа выведет: HelloHello
Почему именно HelloHello?
Это один из ключевых вопросов, тестирующих понимание:
Объяснение шаг за шагом
void foo() {
String m = "Hello"; // m указывает на объект "Hello"
System.out.print(m); // Выводит: Hello
bar(m); // Передаём ССЫЛКУ на m
System.out.print(m); // Выводит: Hello (не изменилось!)
}
void bar(String m) {
m += " World!"; // m ПЕРЕАССОЦИИРУЕТСЯ на новый объект
}
Ключевой момент: в методе bar() строка m переассоциируется на новый объект, созданный операцией конкатенации. Но это не влияет на переменную m в методе foo().
Внутреннее представление в памяти
Найти дублированный элемент в массиве
Объяснение задачи
Дан массив с числами от 1 до 100, где ровно один элемент повторяется один раз. Нужно найти это число за O(n) время и O(1) память.
Решение 1: Использование суммы (самое элегантное)
Идея: сумма чисел от 1 до n = n*(n+1)/2. Вычисляем разницу между фактической суммой и математической.
public class DuplicateFinder {
/**
* Находит дублированный элемент через сумму
* Время: O(n), Память: O(1)
*/
public static int findDuplicate(int[] arr) {
int n = arr.length - 1; // Количество уникальных чисел
// Математическая сумма от 1 до n
long expectedSum = (long) n * (n + 1) / 2;
// Фактическая сумма массива
long actualSum = 0;
for (int num : arr) {
actualSum += num;
}
return (int) (actualSum - expectedSum);
}
}
Поиск среднего элемента LinkedList за один проход
Суть задачи
Нужно найти средний элемент односвязного списка за один проход, не зная заранее длины списка. Классическое применение техники двух указателей (Two Pointers).
Техника двух указателей
Идея: Используем два указателя:
Когда fast достигнет конца списка, slow будет находиться в середине.
Почему это работает
Список: 1 → 2 → 3 → 4 → 5 → null
Шаг 1: slow=1, fast=1
Шаг 2: slow=2, fast=3
Шаг 3: slow=3, fast=5
Шаг 4: slow=3, fast=null → fast достиг конца
Ответ: slow указывает на 3 (середину)
По математике: когда fast дойдет до конца, slow будет ровно в середине.
Реализация
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
Сжатие строки методом Run-Length Encoding (RLE)
Run-Length Encoding — это простой, но эффективный алгоритм сжатия данных, который замещает последовательные одинаковые символы на сам символ и количество его повторений.
Алгоритм
Основное решение
Капитализация первых букв слов в строке
Объяснение задачи
Нужно преобразовать каждое слово в строке так, чтобы первая буква была заглавной, а остальные — прописные. Например, "hello WORLD" → "Hello World".
Решение 1: StringBuilder (процедурный подход)
Это классический и эффективный способ:
Реализация паттерна Singleton
Singleton — это один из самых известных и часто обсуждаемых паттернов проектирования. Он гарантирует, что класс имеет только один экземпляр в течение всего жизненного цикла приложения. Рассмотрим 5 различных способов реализации, от простейшего к самому продвинутому.
1. Eager Initialization (энергичная инициализация)
Экземпляр создаётся при загрузке класса:
public class SingletonEager {
// Экземпляр создаётся сразу при загрузке класса
private static final SingletonEager instance = new SingletonEager();
// Приватный конструктор
private SingletonEager() {
}
// Статический метод доступа
public static SingletonEager getInstance() {
return instance;
}
}
Плюсы:
Развёртывание LinkedList
Суть задачи
Преобразовать порядок элементов в списке на противоположный: первый становится последним, второй — предпоследним и т.д. Это делается путём изменения направления указателей next.
Идея решения
У каждого узла есть указатель next. Нужно развернуть эти указатели в противоположном направлении:
Исходный список: 1 → 2 → 3 → null
Развёрнутый: null ← 1 ← 2 ← 3
Итеративная реализация (O(1) память)
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
Поиск дубликатов в массиве
Это классическая задача на собеседованиях, проверяющая понимание структур данных и сложности алгоритмов. Рассмотрим несколько подходов с разной эффективностью.
Решение 1: HashSet (оптимальное) — O(n) время, O(n) память
Самое быстрое и популярное решение — использовать HashSet, который проверяет наличие элемента за O(1):
Подход
Проходим по строке символ за символом, добавляя в StringBuilder только те символы, которые не являются пробелами. Используем StringBuilder для эффективного конкатенирования.
Решение
Группировка объектов по полю с Collectors
Эта задача демонстрирует один из самых полезных паттернов в Stream API — группировку данных по ключам с агрегацией значений. Это идеален для обработки различных бизнес-сценариев: финансовые отчёты, аналитика, трансформация данных.
Решение
class Transaction {
String type; // "DEPOSIT", "WITHDRAWAL", "TRANSFER"
double amount;
public Transaction(String type, double amount) {
this.type = type;
this.amount = amount;
}
public String getType() {
return type;
}
public double getAmount() {
return amount;
}
}
Валидация скобочной последовательности
Это классическая задача на использование Stack (стека) — одной из фундаментальных структур данных в программировании. Идея решения очень простая: мы проходим по каждому символу и либо добавляем открывающую скобку в стек, либо проверяем, что закрывающая скобка соответствует последней открывающей.
Алгоритм
(, {, [ — добавляем её в стекРеализация на Java
import java.util.Stack;
Подход
Будем проходить по строке с обоих концов навстречу друг другу, обменивая символы местами. Используем массив char для прямого манипулирования символами и двойной указатель.
Решение
Поиск максимальной подстроки без повторяющихся символов
Это классическая задача на применение техники Sliding Window (скользящее окно). Алгоритм позволяет эффективно найти требуемую подстроку за линейное время O(n).
Алгоритм: Sliding Window
Идея очень простая:
left и right, которые образуют «окно»Строка: "abcabcbb"
Шаг 1: окно [a] → max = 1
Шаг 2: окно [ab] → max = 2
Шаг 3: окно [abc] → max = 3
Шаг 4: встречаем 'a' (повтор) → удаляем слева [bca]
Шаг 5: окно [bcab] → видим 'b' повторяется → [cab]
Шаг 6: окно [cabc] → видим 'c' повторяется → [abc]
...
Решение с HashSet
Предсказание вывода: абстрактный класс с конструктором
Результат выполнения
Программа выведет:
This is abstract class constructor
This is demo class constructor
Почему так?
Это классический пример иерархии конструкторов в наследовании. При создании объекта дочернего класса Java автоматически вызывает конструктор родительского класса.
Порядок вызова конструкторов
OurAbstractClass) — выводит "This is abstract class constructor"OurDemoClass) — выводит "This is demo class constructor"Это происходит, потому что компилятор Java автоматически добавляет вызов super() в конструктор дочернего класса:
class OurDemoClass extends OurAbstractClass {
public OurDemoClass() {
super(); // ← вызов конструктора родителя (компилятор добавляет автоматически)
System.out.println("This is demo class constructor");
}
}
Сортировка массива методом пузырька
Bubble Sort — один из самых простых, но наименее эффективных алгоритмов сортировки. Несмотря на его неэффективность для больших данных, он остаётся важным в обучении, так как демонстрирует базовые принципы алгоритмов сортировки.
Почему "пузырька"?
Алгоритм называется "пузырьковой сортировкой" потому, что большие элементы "всплывают" (bubble up) к концу массива подобно пузырькам воздуха, поднимающимся в воде. На каждом проходе наибольший элемент "поднимается" на свою финальную позицию.
Базовый алгоритм