Привет, будущий Java-гуру! Если ты готовишься к собеседованию на позицию Java-разработчика, то наверняка слышал, что задачи на собеседованиях могут быть не просто сложными, но и достаточно интересными. В этой статье мы разобьём 20 популярных задач для собеседований на Java, которые могут появиться как на начальном уровне, так и на более продвинутом.
Я постараюсь сделать эти задачи понятными для новичков и полезными для более опытных разработчиков. Каждый пример будет с детальным разбором, чтобы ты не только научился решать, но и понял, как думают при решении задачи.
Погнали!
1. Палиндром: Проверка строки на палиндром
Задача
Напиши функцию, которая проверяет, является ли строка палиндромом (слово, которое читается одинаково слева направо и справа налево).
Решение
public class Palindrome {
public static boolean isPalindrome(String str) {
// Убираем пробелы и делаем строку в нижнем регистре
str = str.replaceAll("\\s+", "").toLowerCase();
// Перебираем строку с двух концов
for (int i = 0; i < str.length() / 2; i++) {
if (str.charAt(i) != str.charAt(str.length() - 1 - i)) {
return false; // Если не совпадает, не палиндром
}
}
return true; // Если всё совпало — палиндром
}
public static void main(String[] args) {
System.out.println(isPalindrome("A man a plan a canal Panama")); // true
}
}
Разбор
- Очистка строки — сначала удаляем все пробелы и переводим в нижний регистр для точности.
- Перебор с двух концов — с помощью индексов сравниваем символы, начиная с двух концов строки.
- Если хоть один символ не совпадает — возвращаем false. Если все проверены — true.
2. Поиск дубликатов в массиве
Задача
Напиши функцию, которая находит дубликаты в массиве целых чисел.
Решение
import java.util.HashSet;
public class FindDuplicates {
public static boolean hasDuplicates(int[] nums) {
HashSet<Integer> seen = new HashSet<>();
for (int num : nums) {
if (!seen.add(num)) {
return true; // Если число уже в set, значит оно повторяется
}
}
return false; // Дубликатов нет
}
public static void main(String[] args) {
System.out.println(hasDuplicates(new int[]{1, 2, 3, 4, 5})); // false
System.out.println(hasDuplicates(new int[]{1, 2, 3, 4, 4})); // true
}
}
Разбор
- Используем HashSet, так как он не позволяет добавлять одинаковые элементы.
- Если add возвращает false, это означает, что элемент уже существует в сете, и мы нашли дубликат.
3. Реализовать стек с двумя очередями
Задача
Реализуй структуру данных «Стек» с использованием двух очередей.
Решение
import java.util.LinkedList;
import java.util.Queue;
public class StackWithQueues {
private Queue<Integer> q1 = new LinkedList<>();
private Queue<Integer> q2 = new LinkedList<>();
public void push(int x) {
q1.offer(x); // Добавляем элемент в первую очередь
}
public int pop() {
if (q1.isEmpty()) return -1;
// Перемещаем все элементы в очередь q2, кроме последнего
while (q1.size() > 1) {
q2.offer(q1.poll());
}
int poppedElement = q1.poll(); // Последний элемент, который и будет извлечён
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
return poppedElement;
}
public int top() {
if (q1.isEmpty()) return -1;
while (q1.size() > 1) {
q2.offer(q1.poll());
}
int topElement = q1.poll();
q2.offer(topElement);
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
return topElement;
}
public boolean empty() {
return q1.isEmpty();
}
public static void main(String[] args) {
StackWithQueues stack = new StackWithQueues();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2
System.out.println(stack.top()); // 1
}
}
Разбор
- Для того чтобы реализовать стек с помощью очередей, мы используем два Queue.
- Все элементы, кроме последнего, перемещаем во вторую очередь. Это позволяет нам извлечь последний элемент, что по сути и является операцией "pop".
4. Фибоначчи с мемоизацией
Задача
Напиши функцию для вычисления чисел Фибоначчи с использованием мемоизации (кеширование результатов).
Решение
import java.util.HashMap;
public class Fibonacci {
private static HashMap<Integer, Integer> memo = new HashMap<>();
public static int fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result); // Сохраняем результат
return result;
}
public static void main(String[] args) {
System.out.println(fib(10)); // 55
}
}
Разбор
- Используем HashMap для хранения уже вычисленных значений чисел Фибоначчи.
- Это позволяет избежать излишних вычислений и ускорить процесс для больших чисел.
5. Поиск наибольшего общего делителя (НОД)
Задача
Напиши функцию для вычисления наибольшего общего делителя (НОД) двух чисел.
Решение
public class GCD {
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
System.out.println(gcd(56, 98)); // 14
}
}
Разбор
- Используем Алгоритм Евклида для вычисления НОД.
- Пока остаток от деления не равен нулю, продолжаем вычисления, меняя местами значения.
6. Сортировка массива
Задача
Напиши алгоритм сортировки массива (например, пузырьковая сортировка).
Решение
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
Разбор
- Пузырьковая сортировка — один из самых простых алгоритмов сортировки.
- Идея заключается в том, чтобы пройти по массиву и на каждом шаге менять местами элементы, если они идут в неправильном порядке.
7. Реализовать очередь с двумя стеками
Задача
Реализуй структуру данных "Очередь" с использованием двух стеков.
Решение
import java.util.Stack;
public class QueueWithStacks {
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
public void enqueue(int x) {
stack1.push(x);
}
public int dequeue() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public static void main(String[] args) {
QueueWithStacks queue = new QueueWithStacks();
queue.enqueue(1);
queue.enqueue(2);
System.out.println(queue.dequeue()); // 1
}
}
Разбор
- Чтобы реализовать очередь с помощью стеков, используем два стека.
- Первый стек сохраняет элементы в порядке их добавления, второй — извлекает их в правильном порядке.
8. Реализовать связанный список
Задача
Напиши свою реализацию односвязанного списка.
Решение
public class LinkedList {
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
private Node head;
public LinkedList() {
head = null;
}
// Добавление элемента в конец списка
public void append(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// Печать всех элементов списка
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.value + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // Выведет: 10 -> 20 -> 30 -> null
}
}
Разбор
- Node — элемент списка, который содержит значение и ссылку на следующий элемент.
- Метод append добавляет новый элемент в конец списка.
- Метод printList перебирает все элементы списка и выводит их на экран.
9. Реализовать бинарное дерево поиска (BST)
Задача
Реализуй структуру данных "Бинарное дерево поиска" (Binary Search Tree).
Решение
public class BinarySearchTree {
static class Node {
int value;
Node left, right;
Node(int value) {
this.value = value;
left = right = null;
}
}
private Node root;
public BinarySearchTree() {
root = null;
}
public void insert(int value) {
root = insertRec(root, value);
}
private Node insertRec(Node root, int value) {
if (root == null) {
root = new Node(value);
return root;
}
if (value < root.value) {
root.left = insertRec(root.left, value);
} else if (value > root.value) {
root.right = insertRec(root.right, value);
}
return root;
}
public void inorder() {
inorderRec(root);
}
private void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.value + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
bst.inorder(); // Выведет элементы в отсортированном порядке: 20 30 40 50 60 70 80
}
}
Разбор
- BinarySearchTree хранит корень дерева, и каждый узел дерева имеет два возможных потомка.
- Метод insert рекурсивно добавляет элемент в дерево.
- Метод inorder выводит элементы дерева в отсортированном порядке.
10. Динамическое программирование: Разбиение чисел
Задача
Напиши функцию, которая вычисляет количество способов разбиения числа на сумму меньших целых чисел (за исключением самого числа).
Решение
public class Partition {
public static int partitionCount(int n) {
int[] dp = new int[n + 1];
dp[0] = 1; // Есть один способ разбиения числа 0 (не брать ничего)
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dp[j] += dp[j - i]; // Суммируем все способы для числа j
}
}
return dp[n];
}
public static void main(String[] args) {
System.out.println(partitionCount(5)); // 7
}
}
Разбор
- Мы используем динамическое программирование, чтобы вычислить количество разбиений для каждого числа от 1 до n.
- dp[i] хранит количество способов разбиения числа i на сумму меньших чисел.
11. Поиск первого неповторяющегося символа в строке
Задача
Напиши функцию, которая находит первый неповторяющийся символ в строке.
Решение
import java.util.HashMap;
public class FirstNonRepeatingChar {
public static char firstUniqChar(String s) {
HashMap<Character, Integer> freqMap = new HashMap<>();
// Подсчитываем частоту каждого символа
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
// Находим первый символ с частотой 1
for (char c : s.toCharArray()) {
if (freqMap.get(c) == 1) {
return c;
}
}
return ' '; // Если нет уникальных символов
}
public static void main(String[] args) {
System.out.println(firstUniqChar("swiss")); // 'w'
}
}
Разбор
- Используем HashMap для подсчёта частоты каждого символа в строке.
- Во втором цикле ищем первый символ, встречающийся ровно один раз.
12. Реализовать алгоритм сортировки слиянием (Merge Sort)
Задача
Напиши функцию, которая сортирует массив с помощью алгоритма сортировки слиянием.
Решение
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length <= 1) return;
int mid = arr.length / 2;
int[] left = new int[mid];
int[] right = new int[arr.length - mid];
System.arraycopy(arr, 0, left, 0, mid);
System.arraycopy(arr, mid, right, 0, arr.length - mid);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
Разбор
- Алгоритм сортировки слиянием использует подход "разделяй и властвуй".
- Массив делится на две части, которые сортируются рекурсивно, а затем сливаются обратно в отсортированный массив.
13. Поиск наибольшего элемента в подмассиве
Задача
Напиши функцию, которая находит наибольший элемент в подмассиве заданного размера.
Решение
public class MaxSubArray {
public static int findMaxSubArray(int[] nums, int k) {
if (nums.length < k) return -1; // Если подмассив больше массива
int max = Integer.MIN_VALUE;
int currentMax = 0;
for (int i = 0; i < k; i++) {
currentMax += nums[i];
}
max = currentMax;
for (int i = k; i < nums.length; i++) {
currentMax += nums[i] - nums[i - k];
max = Math.max(max, currentMax);
}
return max;
}
public static void main(String[] args) {
System.out.println(findMaxSubArray(new int[]{1, 2, 3, 4, 5}, 3)); // 12
}
}
Разбор
- Мы сначала вычисляем сумму первых k элементов массива.
- Далее, двигаясь по массиву, мы обновляем сумму, вычитая элемент, который выходит за пределы окна, и добавляем новый элемент.
Заключение
В этой статье мы рассмотрели 20 интересных и сложных задач для собеседования Java. Каждая задача имеет своё решение с разбором, что поможет как новичкам, так и опытным разработчикам улучшить свои навыки в Java.
Для того чтобы стать мастером, нужно не только знать теорию, но и практиковаться, решая задачи. Удачи на собеседованиях!