Hi everyone,

Today I’m gonna share the solution for one of the most famous programming interview problems, given a number n, write a program to get the nth element of the Fibonacci sequence.

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, … where the first two numbers are 0 and 1, and each subsequent number is the sum of the previous two.

Here there’s an obvious recursive solution:

int fibo(n)
{
if n<=2:
return 1;
else:
return fibo(n-1) + fibo(n-2);
}

it works fine for a very small n ( <= 30), but what if we need to compute the 10,000th element of the sequence?

Solution:

First of all I want to explain why the above algorithm doesn’t work for a big n, let’s illustrate how it works as a recursion tree:

let’s say we need to get the 5th element of the sequence, so we have:

As you can see, there are a bunch of overlapping calls to fibo, actually this algorithm is O(2^n) in time complexity because to get the nth element of the sequence we need to compute all the n-1 elements and for each one we have two recursive calls… it’s just too slow!

Now, with a very small modification we can improve the efficiency of this program, it’s basically adding a “cache” table for our “already known” results, let’s take a look at the code (in Python):

#!/usr/bin/python -tt
memo = {}
def main():
f = open("data.in","r")
for line in f:
print fibo(int(line))
def fibo(n):
if n <= 2:
return 1
if n in memo:
return memo.get(n)
memo[n] = fibo(n - 1) + fibo(n - 2)
return memo[n]
if __name__ == '__main__':
main()

memo is a hashtable where we store the results for each fibo function call, so if we compute fibo(5), we don’t need to re-compute fibo(5) in the future because we already have the result in our memo table 🙂 so now we can compute fibo(10000) in just fractions of millisecond and this is because now our program runs in O(n).

### Like this:

Like Loading...

*Related*