Question difficile pour l'entretien avec Google

Question

Un de mes amis passe un entretien pour un emploi. Une des questions de l'entretien m'a fait réfléchir, je voulais juste avoir un retour.

Il y a 2 entiers non négatifs : i et j. Étant donné l'équation suivante, trouvez une solution (optimale) pour itérer sur i et j de manière à ce que la sortie soit triée.

2^i * 5^j

Donc les premiers tours ressembleraient à ça :

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25

J'ai beau essayer, je ne vois pas de modèle. Vous en pensez quoi ?

Answer 1

Dijkstra a trouvé une solution éloquente dans "A Discipline of Programming". Il attribue le problème à Hamming. Voici mon implémentation de la solution de Dijkstra.

int main()
{
    const int n = 20;       // Generate the first n numbers

    std::vector<int> v(n);
    v[0] = 1;

    int i2 = 0;             // Index for 2
    int i5 = 0;             // Index for 5

    int x2 = 2 * v[i2];     // Next two candidates
    int x5 = 5 * v[i5];

    for (int i = 1; i != n; ++i)
    {
        int m = std::min(x2, x5);
        std::cout << m << " ";
        v[i] = m;

        if (x2 == m)
        {
            ++i2;
            x2 = 2 * v[i2];
        }
        if (x5 == m)
        {
            ++i5;
            x5 = 5 * v[i5];
        }
    }

    std::cout << std::endl;
    return 0;
}

Answer 2

Voici une façon plus raffinée de le faire (plus raffinée que ma réponse précédente, bien sûr) :

imaginez que les chiffres sont placés dans une matrice :

     0    1    2    3    4    5   -- this is i
----------------------------------------------
0|   1    2    4    8   16   32
1|   5   10   20   40   80  160
2|  25   50  100  200  400  800
3| 125  250  500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical

ce que vous devez faire est de "marcher" sur cette matrice, en commençant à (0,0) . Vous devez également garder une trace de vos prochains mouvements possibles. Lorsque vous commencez à (0,0) vous n'avez que deux options : soit (0,1) o (1,0) puisque la valeur de (0,1) est plus petit, vous le choisissez. puis faites de même pour votre choix suivant (0,2) o (1,0) . Jusqu'à présent, vous avez la liste suivante : 1, 2, 4 . Votre prochain mouvement est (1,0) puisque cette valeur est inférieure à (0,3) . Cependant, vous avez maintenant trois Vous avez le choix pour votre prochain mouvement : soit (0,3) ou (1,1) ou (2,0) .

Vous n'avez pas besoin de la matrice pour obtenir la liste, mais vous devez garder une trace de tous vos choix (c'est-à-dire que lorsque vous arriverez à 125+, vous aurez 4 choix).

Answer 3

Utilisez un Min-heap.

Mettez 1.

extraire-Min. Disons que vous obtenez x.

Poussez 2x et 5x dans le tas.

Répète.

Au lieu de stocker x = 2^i * 5^j, vous pouvez stocker (i,j) et utiliser une fonction de comparaison personnalisée.

Answer 4

Une solution basée sur la FIFO nécessite moins de capacité de stockage. Code Python.

F = [[1, 0, 0]]             # FIFO [value, i, j]
i2 = -1; n2 = n5 = None     # indices, nexts
for i in range(1000):       # print the first 1000
    last = F[-1][:]
    print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
    if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
    if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
    F.append(min(n2, n5))

sortie :

  0.                     1 = 2^0 * 5^0
  1.                     2 = 2^1 * 5^0
  2.                     4 = 2^2 * 5^0
 ...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17

Answer 5

C'est très facile à faire O(n) dans les langages fonctionnels. La liste l de 2^i*5^j peuvent être définis simplement comme suit 1 et ensuite 2*l y 5*l fusionné. Voici comment cela se présente en Haskell :

merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)   
  | a < b   = a : (merge as (b:bs))
  | a == b  = a : (merge as bs)
  | b > a   = b : (merge (a:as) bs)

xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)

En merge vous donne une nouvelle valeur en temps constant. Il en va de même pour map et donc aussi l .