write a recursive function that solves the equation X[n] = X[n-1] + X[n-2] where X is an array that contains at least two integer values and the function should solve the question for the 3rd value in the array

Question

C. · Accepted Answer

I'm guessing a key element they want to see in your answer is that you realize there's a lot of recalculating the same values over and over in the recursion process, especially for large values of n.  For example,

x[5] = x[4] + x[3]
    x[4] = x[3] + x[2]
        x[3] = x[2] + x[1]
            x[2] = x[1] + x[0]
                x[1], x[0] are known
            x[1] is known
        x[2] = x[1] + x[0]
            x[1], x[0] are known
    x[3] = x[2] + x[1]
        x[2] = x[1] + x[0]
                x[1], x[0] are known
            x[1] is known

If you cache a couple of values in the recursive function, you can improve performance significantly.  You might also get some points for recognizing this can be used to generate the Fibonacci sequence.

Sigiloso · Answer

yes its a fibonacci series problem solved using recursion and memoization, classic example of dynamic programming. without caching runtime is exponential.

Netflix

Pergunta de entrevista da empresa Netflix

Respostas da entrevista

Empresas seguidas

Buscas de vagas