Задачи на Java: урок по Java к собеседованию

Алгоритмическая секция на Java отличается от той же секции на Python деталями: быстрый ввод, переполнение int, сортировка объектов против примитивов, глубина рекурсии. Эти детали и роняют решения, которые «по идее правильные».

Шаблон решения

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine().trim());
        StringTokenizer st = new StringTokenizer(in.readLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());

        StringBuilder out = new StringBuilder();
        // ... решение, результат в out
        System.out.print(out);
    }
}

Scanner удобен, но медленный: на 10⁵ чисел он тратит заметную долю лимита. BufferedReader плюс StringTokenizer (или StreamTokenizer) быстрее в разы.
Вывод копим в StringBuilder и печатаем один раз. Тысячи вызовов System.out.println на больших ответах тормозят.
Класс называется Main, без package.

Числа

int до ~2.1·10⁹. Сумма 10⁵ чисел по 10⁹, произведение двух чисел по 10⁵ и количество пар среди 10⁵ элементов уже не влезают. Правило: суммы и счётчики пар сразу в long.
Переполнение молчит. Если сомневаетесь, Math.addExact и Math.multiplyExact бросят исключение.
Середина в бинарном поиске: lo + (hi - lo) / 2 или (lo + hi) >>> 1.
Компаратор (a, b) -> a - b переполняется на больших значениях. Пишите Integer.compare(a, b) или Comparator.comparingInt.
Целое деление округляет к нулю: -7 / 2 == -3, а -7 % 2 == -1. Для неотрицательного остатка есть Math.floorMod.
Больше 64 бит: BigInteger и BigDecimal. Они неизменяемы, результат операции надо присваивать.

Сортировка

Arrays.sort(int[]) для примитивов использует быструю сортировку с двумя опорными (Dual-Pivot Quicksort): O(n log n) в среднем, не стабильна (для примитивов это неважно).
Arrays.sort(Object[]) и List.sort используют TimSort: стабильная, O(n log n) гарантированно.
Сортировать Integer[] медленнее, чем int[]: упаковка и косвенные обращения. Если нужен порядок по ключу, иногда выгодно упаковать пару в long.

Структуры данных из JDK

Нужно	Брать
стек, очередь, дек	`ArrayDeque`
куча	`PriorityQueue` (минимум сверху, для максимума `Comparator.reverseOrder()`)
ближайший больший или меньший	`TreeMap.floorKey/ceilingKey`, `TreeSet.floor/ceiling`
подсчёт частот	`HashMap.merge(k, 1, Integer::sum)` или массив на алфавит
порядок вставки без дублей	`LinkedHashSet`

Для BFS по сетке быстрее очередь на массиве int[] с индексом r * m + c, чем ArrayDeque<int[]>.

Рекурсия

Стек потока по умолчанию порядка мегабайта: рекурсивный DFS на 10⁵-10⁶ уровней упадёт со StackOverflowError. Варианты: итеративный обход с явным стеком или запуск в потоке с большим стеком new Thread(null, task, "main", 1 << 26). На собесе лучше сразу писать итеративно и сказать, почему.

Как вести себя на live coding

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

Что спросят на собесе

Почему Scanner медленный и чем заменить?
Где в вашем решении может переполниться int?
Чем сортировка int[] отличается от сортировки Integer[]?
Почему рекурсивный DFS может упасть и что с этим делать?
Какую сложность имеет ваше решение и можно ли лучше?

Задачи на Java: live coding и контест