You only have free questions left (including this one) .
Write a function fib that takes an integer n and returns the n th 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
We'll never post on your wall or message your friends.
Where do I enter my password?
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?
It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.
Start your free trial!
Log in or sign up with one click to get immediate access to free mock interview questions
We'll never post on your wall or message your friends.
Where do I enter my password?
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?
It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.
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
We'll never post on your wall or message your friends.
Where do I enter my password?
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?
It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.
Editor
Reset editor
vim/emacs?
regular
vim
emacs
Run
{"id":36280109,"username":"2024-11-21_10:07:23__nlah$","email":null,"date_joined":"2024-11-21T10:07:23.706753+00:00","first_name":"","last_name":"","full_name":"","short_name":"friend","is_anonymous":true,"is_on_last_question":false,"percent_done":0,"num_questions_done":0,"num_questions_remaining":46,"is_full_access":false,"is_student":false,"first_payment_date":null,"last_payment_date":null,"num_free_questions_left":3,"terms_has_agreed_to_latest":false,"preferred_content_language":"","preferred_editor_language":"","is_staff":false,"auth_providers_human_readable_list":"","num_auth_providers":0,"auth_email":""}
×
“ Thanks to your site, I have offers from Apple, Facebook and Google. That's a hell of an ROI! I didn't go to school for computer science, and now I have multiple senior engineering offers from the world's best tech companies.
—
Rich
. . .