棘手的谷歌面试问题 [英] 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屋!