棘手的谷歌面试问题

小开

使用最小堆。

输入1。

如果你得到 x。

把2倍和5倍放进堆里。

重复。

您可以存储(i，j)并使用自定义比较函数，而不是存储 x = 2 ^ i * 5 ^ j。

小开

你必须记住它们的个别指数，以及它们的总和是多少

从 f(0,0) --> 1开始现在你必须增加其中一个:

f(1,0) = 2
f(0,1) = 5

所以我们知道2是下一个-，我们也知道我们可以增加 i 的指数，直到和大于5。

你一直这样来回跑直到达到你想要的回合数。

小开

计算结果并将它们与 i和 j的值一起放在一个排序列表中

小开

使用动态编程，你可以用 O (n)表示。基本事实是 i 和 j 的值都不能给出0，要得到1，两个值都必须是0;

TwoCount[1] = 0
FiveCount[1] = 0


// function returns two values i, and j
FindIJ(x) {
if (TwoCount[x / 2]) {
i = TwoCount[x / 2] + 1
j = FiveCount[x / 2]
}
else if (FiveCount[x / 5]) {
i = TwoCount[x / 2]
j = FiveCount[x / 5] + 1
}
}

无论何时调用这个函数，都要检查 i 和 j 是否设置，如果它们不为空，则填充 TwoCount和 FiveCount

C + + 回答。对不起，编码风格不好，但我赶时间: (

#include <cstdlib>
#include <iostream>
#include <vector>


int * TwoCount;
int * FiveCount;


using namespace std;


void FindIJ(int x, int &i, int &j) {
if (x % 2 == 0 && TwoCount[x / 2] > -1) {
cout << "There's a solution for " << (x/2) << endl;
i = TwoCount[x / 2] + 1;
j = FiveCount[x / 2];
} else if (x % 5 == 0 && TwoCount[x / 5] > -1) {
cout << "There's a solution for " << (x/5) << endl;
i = TwoCount[x / 5];
j = FiveCount[x / 5] + 1;
}
}


int main() {
TwoCount = new int[200];
FiveCount = new int[200];


for (int i = 0; i < 200; ++i) {
TwoCount[i] = -1;
FiveCount[i] = -1;
}


TwoCount[1] = 0;
FiveCount[1] = 0;


for (int output = 2; output < 100; output++) {
int i = -1;
int j = -1;
FindIJ(output, i, j);
if (i > -1 && j > -1) {
cout << "2^" << i << " * " << "5^"
<< j << " = " << output << endl;
TwoCount[output] = i;
FiveCount[output] = j;
}
}
}

显然，您可以使用数组以外的数据结构来动态增加存储等。这只是用来证明它有效的素描。

小开

由 Edsger Dijkstra ( http://www.cs.utexas.edu/users/ewd/ewd07xx/ewd792.pdf )实现的 user515430算法可能是你能得到的最快速度。我把每一个 2^i * 5^j形式的数字称为“特殊数字”。现在 vads 的答案应该是 O(i*j)，但是使用了一个双重算法，一个生成特殊数字 O(i*j)，另一个对它们进行排序(根据链接的文章也是 O(i*j))。

但是让我们检查一下 Dijkstra 的算法(见下文)。在这种情况下，n是我们正在生成的特殊数字的数量，因此等于 i*j。我们循环一次，1 -> n，在每个循环中我们执行一个恒定的动作。所以这个算法也是 O(i*j)。还有一个非常快的常数。

我用 GMP (C + + 包装器)在 C + + 中的实现，以及对 boost::lexical_cast的依赖，尽管这可以很容易地删除(我很懒，谁不用 Boost?).与 g++ -O3 test.cpp -lgmpxx -o test一起编译。在 Q6600 Ubuntu 10.10 time ./test 1000000上给出了 1145ms。

#include <iostream>
#include <boost/lexical_cast.hpp>
#include <gmpxx.h>


int main(int argc, char *argv[]) {
mpz_class m, x2, x5, *array, r;
long n, i, i2, i5;


if (argc < 2) return 1;


n = boost::lexical_cast<long>(argv[1]);


array = new mpz_class[n];
array[0] = 1;


x2 = 2;
x5 = 5;
i2 = i5 = 0;


for (i = 1; i != n; ++i) {
m = std::min(x2, x5);


array[i] = m;


if (x2 == m) {
++i2;
x2 = 2 * array[i2];
}


if (x5 == m) {
++i5;
x5 = 5 * array[i5];
}
}


delete [] array;
std::cout << m << std::endl;


return 0;
}

小开

这里有一个更精确的方法(比我之前的答案更精确) :

想象这些数字被放置在一个矩阵中:

     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

你需要做的是“走”这个矩阵，从 (0,0)开始。你还需要跟踪你下一步可能采取的行动。当您从 (0,0)开始时，您只有两个选项: (0,1)或 (1,0): 因为 (0,1)的值较小，所以您选择它。然后对你的下一个选择 (0,2)或者 (1,0)做同样的事情。到目前为止，您有以下列表: 1, 2, 4。您的下一步是 (1,0)，因为那里的值小于 (0,3)。但是，您现在有 (0,0)3的选择为您的下一步: 要么 (0,3)，或 (0,0)1，或 (0,0)2。

你不需要矩阵来得到列表，但是你需要跟踪你所有的选择(也就是说，当你达到125 + ，你将有4个选择)。

小开

为什么不试着从另一个角度看这个问题。使用计数器对照原始公式测试可能的答案。对不起，伪代码。

for x = 1 to n
{
i=j=0
y=x
while ( y > 1 )
{
z=y
if y divisible by 2 then increment i and divide y by 2
if y divisible by 5 then increment j and divide y by 5


if y=1 then print i,j & x  // done calculating for this x


if z=y then exit while loop  // didn't divide anything this loop and this x is no good
}
}

小开

这个是 OEIS 的相关条目。

比如说，通过生成前几个项来获得有序序列似乎是可能的

1245

然后，从第二项开始，乘以4和5得到接下来的2

1245810

12 45810

124 58101620 25

诸如此类。

从直觉上看，这似乎是正确的，但当然缺少一个证明。

小开

最佳答案

Dijkstra 在《程序设计学》一书中提出了一个雄辩的解决方案，他把这个问题归咎于 Hamming。下面是 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;
}

小开

你知道 log _ 2(5) = 2.32，从这里我们可以看出2 ^ 2 < 5和2.3 > 5。

现在看一下可能答案的矩阵:

j/i  0   1   2   3   4   5
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 ...

现在，对于这个例子，按顺序选择数字，顺序是:

j/i  0   1   2   3   4   5
0   1   2   3   5   7  10
1   4   6   8  11  14  18
2   9  12  15  19  23  27
3  16  20  24...

请注意，每一行在开始的行后面开始2列。例如，i = 0 j = 1紧跟在 i = 2 j = 0之后。

因此，我们可以从这个模式推导出一个算法(假设 j > i) :

int i = 2;
int j = 5;
int k;
int m;


int space = (int)(log((float)j)/log((float)i));
for(k = 0; k < space*10; k++)
{
for(m = 0; m < 10; m++)
{
int newi = k-space*m;
if(newi < 0)
break;
else if(newi > 10)
continue;
int result = pow((float)i,newi) * pow((float)j,m);
printf("%d^%d * %d^%d = %d\n", i, newi, j, m, result);
}
}

注意: 这里的代码将 i 和 j 的指数值大写为小于10。您可以轻松地扩展这个算法，以适应任何其他任意的界限。

注意: 这个算法的运行时间对于前 n 个答案是 O (n)。

注意: 该算法的空间复杂度为 O (1)

小开

这在函数式语言中非常容易实现 O(n)。2^i*5^j编号的列表 l可以简单地定义为 1，然后 2*l和 5*l合并。以下是哈斯克尔的情况:

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)

merge函数在恒定的时间内给你一个新的值。 map也是如此，l也是如此。

小开

基于 FIFO 的解决方案需要更少的存储容量。

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

小开

如果你画一个矩阵，i 作为行，j 作为列，你可以看到模式。从 i = 0开始，然后遍历矩阵，向上2行向右1列，直到到达矩阵的顶部(j > = 0)。然后执行 i + 1，等等。.

所以对于 i = 7，你是这样旅行的:

7, 0 -> 5, 1 -> 3, 2 -> 1, 3

I = 8:

8, 0 -> 6, 1 -> 4, 2 -> 2, 3 -> 0, 4

这是 Java 中的 i = 9。它打印矩阵位置(i，j)和值。

for(int k = 0; k < 10; k++) {


int j = 0;


for(int i = k; i >= 0; i -= 2) {


int value = (int)(Math.pow(2, i) * Math.pow(5, j));
System.out.println(i + ", " + j + " -> " + value);
j++;
}
}

小开

我的执行工作基于以下想法:

使用两个队列 Q2和 Q5，都用1初始化。我们将保持两个队列的排序顺序。
在每个步骤中，从 Q2或 Q5中取出最小数元素 MIN 并打印出来。如果 Q2和 Q5都有相同的元素-删除它们。打印这个号码。这基本上是合并两个排序的数组-在每一步选择最小的元素和前进。
排队 MIN * 2至 Q2及 MIN * 5至 Q5。这个改变并没有打破 Q2/Q5排序的不变式，因为 MIN 比以前的 MIN 数要高。

例如:

Start with 1 and 1 (to handle i=0;j=0 case):
Q2: 1
Q5: 1
Dequeue 1, print it and enqueue 1*2 and 1*5:
Q2: 2
Q5: 5
Pick 2 and add 2*2 and 2*5:
Q2: 4
Q5: 5 10
Pick 4 and add 4*2 and 4*5:
Q2: 8
Q5: 5 10 20
....

Java 代码:

public void printNumbers(int n) {
Queue<Integer> q2 = new LinkedList<Integer>();
Queue<Integer> q5 = new LinkedList<Integer>();
q2.add(1);
q5.add(1);
for (int i = 0; i < n; i++) {
int a = q2.peek();
int b = q5.peek();
int min = Math.min(a, b);
System.out.println(min);
if (min == a) {
q2.remove();
}
if (min == b) {
q5.remove();
}
q2.add(min * 2);
q5.add(min * 5);
}
}

小开

我的直觉 :

如果初始值为1，其中 i = 0，j = 0，那么我可以创建下一个数字为(2 ^ 1) < em > (5 ^ 0), (2 ^ 2) (5 ^ 0) ，(2 ^ 0) * (5 ^ 1) ，... 即2,4,5. .

假设我的数字是 x，那么我可以用下面的方法创建下一个数字:

X * 2
X * 4
X * 5

解说 :

Since new numbers can only be the product with 2 or 5.
But 4 (pow(2,2)) is smaller than 5, and also we have to generate
Numbers in sorted order.Therefore we will consider next numbers
be multiplied with 2,4,5.
Why we have taken x*4 ? Reason is to pace up i, such that it should not
be greater than pace of j(which is 5 to power). It means I will
multiply my number by 2, then by 4(since 4 < 5), and then by 5
to get the next three numbers in sorted order.

测试运行

We need to take an Array-list of Integers, let say Arr.


Also put our elements in Array List<Integers> Arr.
Initially it contains Arr : [1]

让我们从 x = 1开始。

接下来的三个数字是1 * 2,1 * 4,1 * 5[2,4,5] ; Arr [1,2,4,5]
现在 x = 2

接下来的三个数字是[4,8,10]{由于4已经出现，我们将忽略它}[8,10] ; Arr [1,2,4,5,8,10]
现在 x = 4

接下来的三个数字[8,16,20]{8已经出现，忽略它}[16,20] [1,2,4,5,8,10,16,20]
X = 5

接下来的三个数字[10,20,25]{10,20}已经加上了[25] [1,2,4,5,8,10,16,20,25]

终止条件

 Terminating condition when Arr last number becomes greater
than (5^m1 * 2^m2), where m1,m2 are given by user.

分析

 Time Complexity : O(K) : where k is numbers possible between i,j=0 to
i=m1,j=m2.
Space Complexity : O(K)

小开

只是好奇下周会发生什么，发现了这个问题。

我想，这个概念是2 ^ i 增加不像5 ^ j 那么大。所以只要下一个 j-step 不会变大，i 就会增大。

C + + 中的例子(Qt 是可选的) :

QFile f("out.txt"); //use output method of your choice here
f.open(QIODevice::WriteOnly);
QTextStream ts(&f);


int i=0;
int res=0;
for( int j=0; j<10; ++j )
{
int powI = std::pow(2.0,i );
int powJ = std::pow(5.0,j );
while ( powI <= powJ  )
{
res = powI * powJ;
if ( res<0 )
break; //integer range overflow


ts<<i<<"\t"<<j<<"\t"<<res<<"\n";
++i;
powI = std::pow(2.0,i );


}
}

输出:

i   j   2^i * 5^j
0   0   1
1   1   10
2   1   20
3   2   200
4   2   400
5   3   4000
6   3   8000
7   4   80000
8   4   160000
9   4   320000
10  5   3200000
11  5   6400000
12  6   64000000
13  6   128000000
14  7   1280000000

小开

这是我的解决办法

#include <stdio.h>
#include <math.h>
#define N_VALUE 5
#define M_VALUE  5


int n_val_at_m_level[M_VALUE];


int print_lower_level_val(long double val_of_higher_level, int m_level)
{
int  n;
long double my_val;




for( n = n_val_at_m_level[m_level]; n <= N_VALUE; n++) {
my_val =  powl(2,n) * powl(5,m_level);
if(m_level != M_VALUE && my_val > val_of_higher_level) {
n_val_at_m_level[m_level] = n;
return 0;
}
if( m_level != 0) {
print_lower_level_val(my_val, m_level - 1);
}
if(my_val < val_of_higher_level || m_level == M_VALUE) {
printf("    %Lf n=%d m = %d\n", my_val, n, m_level);
} else {
n_val_at_m_level[m_level] = n;
return 0;
}
}
n_val_at_m_level[m_level] = n;
return 0;
}




main()
{
print_lower_level_val(0, M_VALUE); /* to sort 2^n * 5^m */
}

结果:

1.000000 n = 0 m = 0
2.000000 n = 1 m = 0
4.000000 n = 2 m = 0
5.000000 n = 0 m = 1
8.000000 n = 3 m = 0
10.000000 n = 1 m = 1
16.000000 n = 4 m = 0
20.000000 n = 2 m = 1
25.000000 n = 0 m = 2
32.000000 n = 5 m = 0
40.000000 n = 3 m = 1
50.000000 n = 1 m = 2
80.000000 n = 4 m = 1
100.000000 n = 2 m = 2
125.000000 n = 0 m = 3
160.000000 n = 5 m = 1
200.000000 n = 3 m = 2
250.000000 n = 1 m = 3
400.000000 n = 4 m = 2
500.000000 n = 2 m = 3
625.000000 n = 0 m = 4
800.000000 n = 5 m = 2
1000.000000 n = 3 m = 3
1250.000000 n = 1 m = 4
2000.000000 n = 4 m = 3
2500.000000 n = 2 m = 4
3125.000000 n = 0 m = 5
4000.000000 n = 5 m = 3
5000.000000 n = 3 m = 4
6250.000000 n = 1 m = 5
10000.000000 n = 4 m = 4
12500.000000 n = 2 m = 5
20000.000000 n = 5 m = 4
25000.000000 n = 3 m = 5
50000.000000 n = 4 m = 5
100000.000000 n = 5 m = 5

小开

我知道我可能错了，但这里有一个非常简单的启发式方法，因为它不涉及很多数字，如2,3,5。我们知道对于任何 i，j 2 ^ i * 5 ^ j 下一个序列是2 ^ (i-2) * 5 ^ (j + 1)。作为一个谷歌 q 它必须有一个简单的解决方案。

def func(i, j):
print i, j, (2**i)*(5**j)


imax=i=2
j=0
print "i", "j", "(2**i)*(5**j)"


for k in range(20):
func(i,j)
j=j+1; i=i-2
if(i<0):
i = imax = imax+1
j=0

产出如下:

i j (2**i)*(5**j)
2 0 4
0 1 5
3 0 8
1 1 10
4 0 16
2 1 20
0 2 25
5 0 32
3 1 40
1 2 50
6 0 64
4 1 80
2 2 100
0 3 125
7 0 128
5 1 160
3 2 200
1 3 250
8 0 256
6 1 320

小开

如果你根据表达式 2^i * 5^j中 i 或 j 增量时的实际情况，你要么乘以另一个2，要么乘以另一个5。如果我们将问题重述为-给定 i 和 j 的特定值，您将如何找到下一个更大的值，解决方案就变得明显了。

以下是我们可以直观列举的规则:

如果在表达式中有一对2(i > 1) ，我们应该用一个5来代替它们，以得到下一个最大的数。因此，i -= 2和 j += 1。
否则，如果有一个5(j > 0) ，我们需要用三个2来代替它，所以 j -= 1和 i += 3。
否则，我们只需要提供另外的2，以增加价值的最低限度。

下面是 Ruby 中的程序:

i = j = 0
20.times do
puts 2**i * 5**j


if i > 1
j += 1
i -= 2
elsif j > 0
j -= 1
i += 3
else
i += 1
end
end

小开

如果允许我们使用 java 集合，那么我们可以在 O (n ^ 2)中得到这些数字

public static void main(String[] args) throws Exception {
int powerLimit = 7;
int first = 2;
int second = 5;
SortedSet<Integer> set = new TreeSet<Integer>();


for (int i = 0; i < powerLimit; i++) {
for (int j = 0; j < powerLimit; j++) {
Integer x = (int) (Math.pow(first, i) * Math.pow(second, j));
set.add(x);
}
}


set=set.headSet((int)Math.pow(first, powerLimit));


for (int p : set)
System.out.println(p);
}

在这里，powerLimit 必须非常小心地初始化! ! 取决于您需要多少个数字。

小开

以下是我对 Scala 的尝试:

case class IndexValue(twosIndex: Int, fivesIndex: Int)
case class OutputValues(twos: Int, fives: Int, value: Int) {
def test(): Boolean = {
Math.pow(2,  twos) * Math.pow(5, fives) == value
}
}


def run(last: IndexValue = IndexValue(0, 0), list: List[OutputValues] = List(OutputValues(0, 0, 1))): List[OutputValues] = {
if (list.size > 20) {
return list
}


val twosValue = list(last.twosIndex).value * 2
val fivesValue = list(last.fivesIndex).value * 5


if (twosValue == fivesValue) {
val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex + 1)
val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.fivesIndex).fives + 1)
run(lastIndex, list :+ outputValues)
} else if (twosValue < fivesValue) {
val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex)
val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.twosIndex).fives)
run(lastIndex, list :+ outputValues)
} else {
val lastIndex = IndexValue(last.twosIndex, last.fivesIndex + 1)
val outputValues = OutputValues(value = fivesValue, twos = list(last.fivesIndex).twos, fives = list(last.fivesIndex).fives + 1)
run(lastIndex, list :+ outputValues)
}
}


val initialIndex = IndexValue(0, 0)
run(initialIndex, List(OutputValues(0, 0, 1))) foreach println

产出:

OutputValues(0,0,1)
OutputValues(1,0,2)
OutputValues(2,0,4)
OutputValues(0,1,5)
OutputValues(3,0,8)
OutputValues(1,1,10)
OutputValues(4,0,16)
OutputValues(2,1,20)
OutputValues(0,2,25)
OutputValues(5,0,32)
OutputValues(3,1,40)
OutputValues(1,2,50)
OutputValues(6,0,64)
OutputValues(4,1,80)
OutputValues(2,2,100)
OutputValues(0,3,125)
OutputValues(7,0,128)
OutputValues(5,1,160)
OutputValues(3,2,200)
OutputValues(1,3,250)
OutputValues(8,0,256)