Memoized recursion in Java
Java interview exercise on Algorithms & recursion, difficulty 2 of 3. Solve it in the editor beside a worked example, or cold in Interview mode with the example hidden; the tests run the moment you do.
Write fib(n) returning the nth Fibonacci number as a long (fib(0) = 0, fib(1) = 1) recursively, with a memo (a Map<Integer, Long> or a long[]) so fib(90) answers at once instead of taking longer than the universe. Negative n is an IllegalArgumentException.
Each exercise pairs a worked example with a twin problem to solve in a real editor; the tests run the moment you do. Interview mode hides the example: solve it from memory, without the hint or the solution, and it counts as solved cold. Progress is saved in your browser, and in your account if you sign in.