Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

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!

Log in or sign up with one click to get immediate access to free mock interview questions

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

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?

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Reset editor

Powered by qualified.io

. . .