Рекурсивный обход цепочки из 100 000 элементов падает со StackOverflowError — перепишите его без рекурсии

ЗадачаMiddleЧасто

Проверила команда СопроводОбновлено

Короткий ответ

Каждый рекурсивный вызов кладет кадр в стек потока, а размер стека на Linux x64 по умолчанию 1 МБ: на 100 000 вызовах он кончается. Хвостовую рекурсию Java не оптимизирует, поэтому перепишите обход циклом: идите по ссылке previous, пока она не станет null, и считайте шаги. Дополнительная память выйдет O(1). Для дерева заведите явный стек на ArrayDeque.

Почему этот вопрос задают

Вопрос связывает устройство JVM с повседневным кодом. По ответу видно, понимаете ли вы, что такое кадр стека, почему флаг -Xss не решает проблему и умеете ли превращать рекурсию в цикл.

Условие задачи

Онлайн-редактор сохраняет версию документа после каждой правки, и каждая версия хранит ссылку на предыдущую: record Version(String id, Version previous). У регламента службы поддержки, который правят каждый день, за три года набралось 100 000 версий. Их число считал рекурсивный метод depth(v): он возвращает 1, если предыдущей версии нет, иначе 1 + depth(v.previous()). На этом регламенте метод падает со StackOverflowError. Перепишите подсчет без рекурсии, для этой цепочки он должен вернуть 100000.

Как подойти к решению

  1. Объясните, откуда ошибка: каждый вызов depth добавляет кадр в стек потока
  2. Замените рекурсию циклом, который идет по ссылке previous до null
  3. Держите в цикле только текущую версию и счетчик шагов
  4. Проверьте крайние случаи: первая версия без предыдущей дает 1, null на входе дает 0

Решение

Цикл не создает новых кадров, поэтому длина цепочки ограничена только кучей: время O(n), дополнительная память O(1). Для null метод вернет 0, это совпадает со смыслом «версий нет». Цепочку для проверки строит цикл в main: каждая новая версия ссылается на предыдущую.

Java
public class Main {
    public static void main(String[] args) {
        Version last = new Version("v1", null);
        for (int i = 2; i <= 100_000; i++) last = new Version("v" + i, last);
        System.out.println(chainLength(last));
    }

    static int chainLength(Version version) {
        int length = 0;
        for (Version v = version; v != null; v = v.previous()) length++;
        return length;
    }
}

record Version(String id, Version previous) {}
Вывод
100000

Что спросят следом

  • Как без рекурсии обойти дерево версий, где от одной версии отходит несколько веток?

  • Что делать, если из-за ошибки в данных цепочка замкнулась в кольцо?

  • Почему Java не оптимизирует хвостовую рекурсию?

Доступно по подписке

Ответы на эти вопросы

Частые ошибки

  • «Увеличу стек через -Xss, и все заработает»

    Это только отодвигает предел. На JDK 21 под Linux x64 со стеком по умолчанию 1 МБ рекурсия на 100 000 падает, с -Xss8m проходит и снова падает на миллионе версий

  • «Распечатаю last, чтобы посмотреть цепочку в отладке»

    Сгенерированный toString() записи рекурсивно печатает всю цепочку и сам падает со StackOverflowError уже на нескольких тысячах версий. hashCode() и equals() у такой записи тоже рекурсивны

  • «Рекурсия здесь естественнее, цикл — преждевременная оптимизация»

    Для связного списка цикл читается так же просто, а на длинной цепочке рекурсия упадет. Рекурсию оставьте для структур с небольшой известной глубиной, например для сбалансированного дерева

  • «Соберу цепочку в ArrayList и возьму size()»

    Рекурсии тут нет, но вы потратите O(n) памяти на список, который нужен лишь для счета. Счетчик в цикле дает тот же ответ при O(1) памяти

Сигналы для интервьюера

Сильный ответ

Связывает ошибку с размером стека потока, сравнивает память рекурсивного и итеративного решений и объясняет выбор

Тревожный сигнал

Предлагает обернуть вызов в try и при StackOverflowError вернуть запасное значение вместо исправления обхода

Красный флаг

Путает StackOverflowError с OutOfMemoryError и всерьез предлагает поднять размер кучи через флаг -Xmx

Как еще могут спросить

  • Что такое StackOverflowError и когда он возникает?
  • Как переписать рекурсию через цикл в Java?
  • Почему глубокая рекурсия падает в Java и как это исправить?
  • Что делать, если рекурсивный метод падает на больших данных?

Похожие вопросы

ЗнаниеJuniorЧасто

Чем стек отличается от кучи в Java и что хранится в каждой области?

Стек есть у каждого потока: в нем лежат кадры вызванных методов с параметрами, локальными переменными примитивных типов и ссылками. Куча одна на всю JVM: в ней живут все объекты и массивы, и ее чистит сборщик мусора. Локальная переменная хранит в стеке ссылку, сам объект лежит в куче. Аргументы Java передает по значению: копируется число или ссылка.

  • JVM
  • память
244
ЗнаниеSeniorЧасто

Как найти утечку памяти в Java-приложении, которое падает с OutOfMemoryError: Java heap space?

Сначала отличите утечку от нехватки памяти: при утечке занятая куча после каждой полной сборки растет и не возвращается. Включите -XX:+HeapDumpOnOutOfMemoryError, чтобы получить дамп в момент падения, или снимите его через jcmd. В Eclipse MAT найдите в дереве доминаторов объект, который держит больше всего памяти, и пройдите путь до корня: он покажет, чья ссылка не отпускает объекты.

  • JVM
  • память
248
ЗнаниеJuniorЧасто

Чем ArrayList отличается от LinkedList и когда LinkedList действительно быстрее?

ArrayList хранит элементы в массиве: доступ по индексу за O(1), вставка в конец в среднем тоже, вставка в середину сдвигает хвост. LinkedList — двусвязный список: get(i) идет по узлам от ближнего края, зато вставка и удаление через итератор, который уже стоит на месте, занимают O(1). На практике почти всегда быстрее ArrayList, а для очереди берут ArrayDeque.

  • коллекции
  • Java Core
273
ЗадачаJuniorЧасто

Посчитайте выручку трех филиалов параллельно в пуле потоков через Callable и выведите ее в порядке филиалов

Опишите подсчет выручки филиала как Callable<Integer>: в отличие от Runnable, он возвращает результат. Отправьте три задачи через submit в Executors.newFixedThreadPool(3) и сложите полученные Future в список в порядке филиалов. Потом вызовите get() у каждого по очереди, и вывод совпадет с порядком отправки. Пул закройте через try-with-resources (Java 19+) или shutdown().

  • Многопоточность
  • ExecutorService
254

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

Фиксированного числа нет: оно зависит от размера стека, числа локальных переменных метода и от того, успел ли JIT его скомпилировать. На JDK 21 под Linux x64 с настройками по умолчанию простая рекурсия из этой задачи проходит 10 000 вызовов и падает на 20 000. На собеседовании назовите порядок и объясните, от чего он зависит.

В вопросах про области памяти JVM: у каждого потока свой стек с кадрами и локальными переменными, объекты лежат в общей куче. Отсюда вопросы, почему переполнение стека и нехватка кучи — разные ошибки и почему тысячи платформенных потоков съедают память даже без объектов.

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

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

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

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

Хватит двух-трех сильных сторон, которые нужны на этой работе, если к каждой есть пример: что сделали и какой был результат. Берите качества из текста вакансии, а не из списка «ответственный, коммуникабельный». Без опыта примеры ищите в учебе, практике и подработке. Говорите спокойно, без лишней скромности и без хвастовства.

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

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

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

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

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

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

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

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

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

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

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

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

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

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

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

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

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

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

  • цели
  • планирование
227