Вопрос
Does Python int overflow? How can you roughly estimate how much memory n! needs without computing the factorial?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Python ints are arbitrary precision, so they do not overflow like fixed 64-bit ints. Memory grows with bit length, roughly log2(n!), which can be estimated by Stirling.
Полный разбор
Python int is arbitrary precision. Arithmetic does not overflow at 32 or 64 bits; instead, the object allocates more machine words as the value grows. Eventually you can still run out of memory or time.
To estimate memory for n!, estimate the number of bits rather than the numeric value itself. The bit length is floor(log2(n!)) + 1. Using Stirling, log2(n!) is approximately n log2(n) - n log2(e) plus a smaller term from sqrt(2 pi n). Divide by 8 for bytes and remember that Python object overhead means the actual memory is higher.
This is the key reasoning move in the interview: switch from the magnitude of n! to the logarithm of n!, because storage is proportional to digits or bits.
Теория
Large integer storage is proportional to bit length; logs convert products into sums.
Типичные ошибки
- Say Python int can never fail.
- Estimate bytes from the decimal value instead of digit count.
- Forget interpreter object overhead.
Как отвечать на собеседовании
- Use bit_length as the practical Python API.
- Use Stirling only for rough order-of-magnitude reasoning.