Question d'entretien d'embauche Google: Calculate the nth number of t... |

Question d'entretien d'embauche

Entretien de Software Engineer Palo Alto, CA (États-Unis)

Calculate the nth number of the fibonacci series


Réponse de l'entretien

5 réponses


do not use recursion

Candidat à l'entretien, le 26 juin 2010

double fibonacci(double n){
        double x = 0;
        double y = 1;
        double c = 0;
        double temp = 2;

Anonymous, le 5 juil. 2010

That response is in O(n). There is an O(1) solution, as the fibonacci series can be represented in a closed form solution:

As I recall, there are several methods to calculate a closed form solution for recurrent problems, but it's been a long time for me....

somebody, le 16 juil. 2010

You can find the closed form expression f_n by assuming f_n = c * b^n, plug into the recursion equation and solve; similar to solving linear differential equations by assuming f(x) = c * e^(a * x).

Utilisateur anonyme, le 12 sept. 2010

Don't write this function to use a double. Use an unsigned long long, since it will use all 64 bits. A double will only use 53 bits for the mantissa and then waste 11 bits on an unused exponent. If the exponent is ever something other than 0, then you results will not be accurate anyway.

Vagrant, le 6 août 2011

Ajouter des réponses ou des commentaires

Pour commenter ceci, se connecter ou s'inscrire