Coding Interview Question - Nth Fibonacci

Ace the Programming Interviews with 65 video explanations of popular interview questions. Each question also comes with a workspace where you can code your solutions and run them against custom test cases, with hints, with written solutions in JavaScript, Python, C++, Java, and Go, and with a space-time complexity analysis of the algorithm at hand.

[ericbezault]

There is a small mistake in the video at 18:14. `fib6` should be calling `fib5` and `fib4`, and not `fib5` and `fib5`.

[SaddamHossain-vgqe]

I think, initial value for counter should be 2 and the base case check while returning will be n>=1.

// time: O(n) | space: O(1)
func fib(N int) int {
lastTwo := []int{0, 1}
counter := 2
for counter <= N {
nextFib := lastTwo[0] + lastTwo[1]
lastTwo[0] = lastTwo[1]
lastTwo[1] = nextFib
counter++
}
if N >= 1 {
return lastTwo[1]
}
return lastTwo[0]
}

Thank you very much for the tutorial!

[edwinontiveros]

one may also optimize a little bit in both space and time complexity if you assume any number below or equal to 2, except 0, will always return 1.
fib(int n)
{
if(n == 0) return 0;
else if ( n <= 2) return 1;
else return fib(n-1)+fib(n-2);
}

that way when fib(2) or fib(1) will not go though the subtree and will immediately return the appropriate value. Works with recursive, memoization and lookup table.

[geetusharma]

I code in java, Is java walkthrough also available ??or how can I get idea of java code for ques ? I am confused, please help .

[purpleraccoon]

There is also a very cool O(log n) solution by using matrix exponentiation

[sweatysweatson]

Hey Clement, how is it going? I've been preparing for internships using algoexpert and sometimes there are some questions that I can't find the answer for. I was wondering if there is a facebook group or something so student could ask their question from you or your team?

[alexandernguyen-phuoc]

how does one know to put n ==2 return 1 or n==1 return 0? like was it base on the first two value being 0, 1 and we just gave it the == 1 and 2 based on the fib(n-1) and fib(n-2) in that order?

[farhaadkhan]

Am I the only one who learned this in 9th grade java class but had no idea this could be asked in an real interview?

[in]

Why you define your fibonacci function with n > 2 ? If you check everywhere, the fibonacci sequence is defined with n > 1, so f(1) = 1 and not 0.

[panabogdanliviu]

You know there is a formula for this soo if you would be asked ever to do this (most unlikely) what's stopping you from using the formula? soo you will have a const time :)))

[monkeytrollhunter]

;_; I paid $100 and this video is on Youtube :( But I find the videos to be helpful. can you make more videos pls?

[thomasjust]

This website is a waste of money, save your self some and learn to code by yourself, you don't need these so called experts to help you "ace" the interview, if you know how to code, your knowledge will come thru