Implement the Fibonacci sequence with O(n)

Question

Sigiloso · 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.

Sigiloso · Answer

Recursively.

Indeed

Pergunta de entrevista da empresa Indeed

Respostas da entrevista

Empresas seguidas

Buscas de vagas