recursion · Problem 1 of 1
Fibonacci with Memoisation
medium
Amazon
AmazonReturn the nth Fibonacci number, where fib(0) = 0 and fib(1) = 1.
fib(10) -> 55Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| fib(0) | base zero | 0 | — |
| fib(1) | base one | 1 | — |
| fib(10) | small | 55 | — |
| fib(30) | larger | 832040 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(n)
Without the cache this is O(2^n) — fib(50) would take longer than the exercise timeout. The cache is the entire difference.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left