Implement the Fibonacci sequence with O(n)

Question

Anonymous · Accepted Answer

Python:

def iterative_fib(n):
    last_1 = 0;
    last_2 = 1;
    for i in range(1, n):
        fib = last_1 + last_2
        last_1 = last_2
        last_2 = fib
    return fib

The recursive solution IS NOT O(n)!

The recursuve solution is O(n)... · Answer

...if you use a hash map to save every previous (number, fib(number)) couple.

Anonymous · Answer

Recursively.

Indeed

Indeed interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?