棘手的谷歌面试问题
棘手的谷歌面试问题
提问于 2011-04-01 04:27:16
我的一个朋友正在面试一份工作。面试中的一个问题让我开始思考，只是想要一些反馈。
有两个非负整数: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尽管我试过了，我还是看不出有什么规律。你的想法是什么？
回答 15
Stack Overflow用户
回答已采纳
发布于 2011-04-01 05:35:56
Dijkstra在“编程的一门学科”中得出了一个雄辩的解决方案。他把这个问题归因于汉明。这是我对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;
}Stack Overflow用户
发布于 2011-04-01 04:30:06
使用最小堆。
放1。
提取-最小值。假设你得到了x。
将2x和5x推入堆中。
重复一遍。
您可以存储(i，j)并使用自定义的比较函数，而不是存储x= 2^i * 5^j。
Stack Overflow用户
发布于 2011-04-01 07:44:19
基于FIFO的解决方案需要较少的存储容量。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))输出：
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5505894
复制相关文章
相似问题
腾讯云开发者
