Какую коллекцию лучше использовать для кэширования вычислений факториала в Java

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

Замечаете ли вы особенности конкретной задачи, а не отвечаете шаблоном «кэш значит HashMap». Факториал удобен тем, что ключи здесь плотные целые числа от нуля, а значения быстро выходят за пределы типов. Следом спрашивают про переполнение и потокобезопасность.

Как отвечать

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

Дальше важно посчитать границы:

• long: вмещает факториалы только до 20!, а 21! уже переполняет тип. Значит, весь кэш это static final long[] из 21 элемента, заполненный один раз в статическом инициализаторе. После инициализации класса такой массив безопасно читать из любого числа потоков без синхронизации;
• BigInteger: если нужны большие n, храните ArrayList<BigInteger> и достраивайте его итеративно по формуле f(n) = n * f(n - 1), начиная с последнего посчитанного значения. Для многопоточного доступа достаточно синхронизировать метод достройки;
• ограничение размера: у 10 000! уже десятки тысяч цифр, поэтому кэш на BigInteger полезно ограничить сверху.

Если интервьюер настаивает на мапе, ConcurrentHashMap допустим, но без рекурсии внутри computeIfAbsent. Контракт метода запрещает менять ту же мапу из функции вычисления: в Java 8 это могло зациклиться, в более новых версиях обычно заканчивается IllegalStateException: Recursive update. У HashMap в той же ситуации с Java 9 летит ConcurrentModificationException.

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

Пишут рекурсивный вызов factorial(n - 1) прямо внутри cache.computeIfAbsent(n, ...). Код выглядит изящно, но нарушает контракт метода и падает или зависает.

Не проверяют переполнение. long после 20! молча уходит в мусорные значения, в том числе отрицательные, и кэш аккуратно хранит неправильные ответы. Для явной ошибки есть Math.multiplyExact.

Считают рекурсивно без ограничения глубины. Для больших n это StackOverflowError, тогда как итеративный цикл с кэшем от размера стека не зависит.