Как решать задачу оптимизации неэффективного алгоритма

Что проверяют

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

Как отвечать

Каркас в четыре шага:

• зафиксировать поведение: тесты на текущий результат, чтобы оптимизация не сломала логику;
• измерить: профилировщик на реальной нагрузке, например async-profiler или Java Flight Recorder с просмотром в JDK Mission Control. Микробенчмарки только через JMH: он делает прогрев, запускает отдельные форки JVM и защищает от удаления «мёртвого» кода JIT-компилятором;
• снизить сложность: list.contains() в цикле даёт O(n²), HashSet превращает это в O(n) в среднем. Повторные вычисления уходят в кэш или динамическое программирование, пересчёт суммы окна заменяется префиксными суммами или скользящим окном;
• убрать накладные расходы: упаковка в List<Integer> против массива int[], конкатенация строк в цикле вместо StringBuilder, лишние промежуточные коллекции в стримах, LinkedList там, где нужен доступ по индексу.

Параллелизм упоминайте последним и с оговорками: parallelStream() работает в общем ForkJoinPool и окупается только на больших объёмах вычислений без блокирующих вызовов.

Закончите результатом: как изменились время и память на одном и том же профиле нагрузки. Если приводите пример из своего опыта, называйте реальные цифры и способ, которым их получили.

Где спотыкаются

Меряют через System.currentTimeMillis() вокруг одного вызова. Без прогрева вы измеряете интерпретатор и компиляцию, а не код, и цифры скачут от запуска к запуску.

Рассказывают, как написали быструю сортировку вместо пузырьковой. Arrays.sort и List.sort уже работают за O(n log n), а своя быстрая сортировка в худшем случае вырождается в O(n²).

Меняют структуру данных, не проверив hashCode. HashMap с плохой хэш-функцией складывает ключи в одну корзину, и поиск заметно деградирует.