## Get a free weekly practice problem!

Keep that axe sharp.

### You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

Write a function fib that takes an integer n and returns the nth Fibonacci number.

Let's say our Fibonacci series is 0-indexed and starts with 0. So:

fib(0); // => 0 fib(1); // => 1 fib(2); // => 1 fib(3); // => 2 fib(4); // => 3 ...

Our solution runs in n time.

There's a clever, more mathy solution that runs in time, but we'll leave that one as a bonus.

If you wrote a recursive function, think carefully about what it does. It might do repeat work, like computing fib(2) multiple times!

We can do this in space. If you wrote a recursive function, there might be a hidden space cost in the call stack!

### Start your free trial!

time and space.

• If you're good with matrix multiplication you can bring the time cost down even further, to . Can you figure out how?