棘手的Google面试问题

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

有2个非负整数:我和j。 给定以下等式,find一个(最优)解决scheme来迭代i和j,使得输出被sorting。

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在“编程学科”中得出了一个雄辩的解决scheme。 他把这个问题归咎于海明。 这是我实施Dijkstra的解决scheme。

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

这是一个更精细的做法(比我以前的答案更精致):

想象一下数字被放置在一个matrix中:

  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 

你需要做的是“走”这个matrix,从(0,0) 。 你还需要跟踪你可能的下一步行动。 从(0,0)开始时,只有两个选项: (0,1)(1,0) :由于(0,1)值较小,所以select该选项。 然后为你的下一个select(0,2)(1,0)做同样的事情。 到目前为止,您有以下列表: 1, 2, 4 。 你的下一步是(1,0)因为那里的值小于(0,3) 。 然而,你现在有三个select你的下一步: (0,3)(1,1)(2,0)

你不需要matrix来获取列表,但是你需要跟踪所有的select(例如,当你达到125+,你将有4个select)。

使用最小堆。

把1

提取民。 说你得到x。

将2x和5x推入堆中。

重复。

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

基于FIFO的解决scheme需要更less的存储容量。 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 

O(n)在函数式语言中很容易做到。 2^i*5^j个数的列表l可以简单地定义为1 ,然后2*l5*l合并。 下面是它在Haskell中的样子:

 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) 

mergefunction在一段时间内为您提供了一个新的值。 所以map ,因此也是如此。

你必须跟踪他们的个人指数,以及他们的总和

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

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

所以我们知道2是下一个 – 我们也知道我们可以增加我的指数,直到总和超过5。

你一直这样来回奔跑,直到你处于被摧残的数轮。

使用dynamic编程,您可以在O(n)中执行此操作。 事实是,我和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是否设置,如果它们不为null,那么填充TwoCountFiveCount


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

显然你可以使用数组以外的数据结构来dynamic增加你的存储等。这只是一个草图,以certificate它的工作原理。

为什么不尝试从另一个方向看这个呢? 使用计数器来testing可能的答案对原始公式。 对不起,伪代码。

 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的相关条目。

看起来有可能通过生成前几个术语来获得有序序列,比如说

1 2 4 5

然后从第二项开始,再乘以4和5得到下两项

1 2 4 5 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

等等…

直觉上,这似乎是正确的,但当然缺less一个certificate。

你知道log_2(5)= 2.32。 由此我们注意到2 ^ 2 <5和2 ^ 3> 5。

现在看一个可能的答案matrix:

 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 ... 

现在,对于这个例子,按顺序select数字。 有订购将是:

 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。

因此,我们可以从这个模式导出一个algorithm(假设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.您可以很容易地扩展此algorithm以适应任何其他任意的边界。

注意:对于前n个答案,此algorithm的运行时间为O(n)。

注意:这个algorithm的空间复杂度是O(1)

我的实现基于以下想法:

  • 使用两个队列Q2和Q5,都用1初始化。我们将按照sorting顺序保留两个队列。
  • 在每一步中,从Q2或Q5出列最小数目的元素MIN并打印出来。 如果Q2和Q5都有相同的元素 – 删除两个。 打印这个号码。 这基本上是合并两个sorting的数组 – 在每一步select最小的元素和前进。
  • 将MIN * 2排到Q2和MIN * 5到Q5。 这个改变不会破坏sorting的Q2 / Q5的不variables,因为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); } } 

计算结果并将它们与ij的值一起放入sorting列表中

由Edsger Dijkstra(http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF)由user515430执行的algorithm可能会尽可能地快。; 我把每一个数字都叫做2^i * 5^j一个“特殊数字”。 现在vlads的答案是O(i*j)但有一个双重algorithm,一个生成特殊数字O(i*j)和一个sorting他们(根据链接的文章也O(i*j)

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

我在C ++中使用GMP(C ++ wrapper)实现,依赖于boost::lexical_cast ,虽然这可以很容易地删除(我很懒,谁不使用Boost?)。 用g++ -O3 test.cpp -lgmpxx -o test编译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; } 

如果用i作为行,j作为列绘制matrix,则可以看到该模式。 从i = 0开始,然后遍历matrix,向上移动2行,右移1列,直到达到matrix顶部(j> = 0)。 然后去我+ 1等…

所以对于我= 7你这样旅行:

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

而对于我= 8:

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

这里是在Java中上升到i = 9。它打印matrix的位置(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++; } } 

我的直觉

(2 ^ 1) (5 ^ 0),(2 ^ 2) (5 ^ 0),(2 ^ 0) *(5 ^ 1),…即2,4,5 ..

在任何时候说我的号码是x。 那么我可以通过以下方式创build下一个数字:

  • 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. 

testing运行

 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]; 编曲[1,2,4,5]

  • 现在x = 2

    接下来的三个数字是[4,8,10] {因为4已经发生,我们将忽略它} [8,10]; 编曲[1,2,4,5,8,10]

  • 现在x = 4

    接下来的三个数字[8,16,20] {8已经发生忽略它} [16,20] Arr [1,2,4,5,8,10,16,20]

  • x = 5

    接下来的三个数字[10,20,25] {10,20}已经如此[25]被joinArr [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) 

只是好奇下周会发生什么,并已经find了这个问题。

我认为,这个想法是2 ^我不像5 ^ j那样大步增加。 所以只要下一个j步骤不会更大,就增加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 ); } } 

输出:

 ij 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 

这是我的解决scheme

 #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=%dm = %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它必须有一个简单的解决scheme。

 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 

这产生的输出为:

 ij (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 

如果当我们在expression式2^i * 5^j递增i或j时,发生了什么事情,那么要么乘以另一个2或另一个5.如果我们将问题重述为 – 给定i和j的特定值,你如何find下一个更大的价值,解决scheme变得明显。

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

  • 如果expression式中有一对2( i > 1 ),我们应该用5replace它们以获得下一个最大的数字。 因此, i -= 2j += 1
  • 否则,如果有一个5​​( j > 0 ),我们需要用三个2来代替它。 所以j -= 1i += 3
  • 否则,我们只需要提供另一个2来增加最小值。 i += 1

这是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必须非常小心的初始化! 取决于你想要多less个数字。

这是我与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)