棘手的谷歌面试问题 [英] Tricky Google interview question

问题描述

我的一个朋友正在找工作面试的。其中一个面试问题让我思考，只是想一些反馈。

A friend of mine is interviewing for a job. One of the interview questions got me thinking, just wanted some feedback.

有2个非负整数：i和j。给出下面的等式，找到一个（最佳）溶液来迭代i和j在这样一种方式，输出的排序

There are 2 non-negative integers: i and j. Given the following equation, find an (optimal) solution to iterate over i and j in such a way that the output is sorted.

2^i * 5^j

所以前几轮应该是这样的：

So the first few rounds would look like this:

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

尝试，因为我可能，我不能看到一个模式。你的想法吗？

Try as I might, I can't see a pattern. Your thoughts?

推荐答案

Dijkstra算法得出的A学科规划雄辩的解决方案。他的属性问题，以海明。 下面是我的实现Dijkstra的解决方案。

Dijkstra derives an eloquent solution in "A Discipline of Programming". He attributes the problem to Hamming. Here is my implementation of Dijkstra’s solution.

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;
}

这篇关于棘手的谷歌面试问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！