我的一个 friend 正在面试一份工作。其中一个面试问题让我开始思考,只是想要一些反馈。
有 2 个非负整数:i 和 j。给定以下等式,找到一个(最佳)解决方案以对输出进行排序的方式迭代 i 和 j。
2^i * 5^j
所以前几轮看起来像这样:
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
尽我所能,我看不到规律。你的想法?
最佳答案
Dijkstra 在“A Discipline of Programming”中推导出了一个 Eloquent 解决方案。他将问题归咎于汉明。 这是我对 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;
}
关于algorithm - 棘手的谷歌面试问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5505894/