Leetcode 238: Product of Array except itself

July 24, 2015

 Introduction

I like to share the article talking about Google interview written in Chinese. The article is called "死理性派教你做谷歌面试题", the link is here. 

The experience of working on Leetcode is so challenging. I fully understand the solution but after a few days, I have no clue how it works. But there are so many good articles to read. 

Leetcode 238 in Chinese

  转载上面网页最后一段.

  不同于上面的“流传”，下面两道是已被确认了的google面试题。

第一题，给你一个长度为 N 的链表。N 很大，但你不知道 N 有多大。你的任务是从这 N 个元素中随机取出 k 个元素。你只能遍历这个链表一次，且必须保证取出的元素是完全随机的（出现概率均等）。

第二题，给你一个数组 A [ 1 .. n ] ，请你在 O ( n ) 的时间里构造一个新的数组 B [ 1 .. n ] ，使得 B [ i ] = A [ 1 ] * A [ 2 ] * ... * A [ n ]／A [ i ] 。你不能使用除法运算。

这两道题目看起来很专业，但有趣的是，即使没有学过信息学的人也可以想到答案。

第一题的意思就是有一大串物品，它们能且仅能逐个经过你眼前一次。你不知道它们的个数，要求你从中随机地抽取 k 个物品，同时必须保证取出的元素是完全随机的（出现概率均等）。

第二题给出了一个数列 A [ 1 .. n ] ，要求在较短的时间内不用除法构造一个新数列 B [ 1 .. n ] ，使得 B [i] = A [ 1 ] * A [ 2 ] * ... * A [ n ]／A [ i ] 。 n是这个数组的长度。而 O ( n ) 是评判计算方法速度的标准。如果一个解答方法在n任意变化的情况下，都能满足总共的计算次数相当于是 n 乘以一个常数C这个条件，那么就称这个解答方法是 O ( n ) 的；如果这个解答方法能满足总共的计算次数是 n ² 乘以常数C，那么这个解答方法就被称作是 O ( n ² ) 的。

第一题没有告诉我们物品的个数N，所以我们没法算出 k／N，连最基本的每样物品被选中的概率都不知道，还怎么继续操作呢？既然我们不知道一共有多少个物品，那我们就应该在所有的物品都经过我们眼前之后再做抉择。当每个物品经过我们眼前的时候，可以设法对应地给它生成一个 0 到 1 之间的随机数。等到我们见过了所有的物品之后，只需要选择对应的随机数最大的前 k 个物品就行了。

第二题不允许用除法增加了不少难度。 B [ i ] 不用除法来表示的话就是： B [ i ] = A [ 1 ] * ... * A [ i - 1 ] * A [ i + 1 ] * ... * A [ n ] 。若按照这个表达式进行计算，生成每个 B[ i ] 的时候要进行n - 1次乘法，这样一来完全生成 B [ 1 .. n ] 就需要 O ( n ² ) 的时间了。我们需要通过减少重复的运算来提高效率。

注意到 B [ i ] 可以看作是两个部分的乘积， A [ 1 ] * ... * A [ i - 1 ] 和 A [ i + 1 ] * ... * A [ n ] 。同理 B [ i + 1 ] 就由 A [ 1 ] * ... * A [ i - 1 ] * A [ i ] 和 A [ i + 2 ] * ... * A [ n ] 组成。计算 B [ i ] 时的许多乘法在计算 B [ i + 1 ] 的时候又进行了一遍，因此可以重复利用上一次运算的结果，以避免无谓的运算。从这点出发，我们构造两个新的数列：

S [ i ] = A [ 1 ] * ... * A [ i – 1 ]
T [ i ] = A [ i + 1 ] * ... * A [ n ]

因为生成完整的 S [ 1 .. n ] 和 T [ 1 .. n ] 都能在 O ( n ) 的时间内完成，那么根据 B [ i ] = S [ i ] * T [ i ] 这条式子，生成整个 B [ 1 .. n ] 便也能够在 O ( n ) 的时间内完成了。

不得不说，谷歌是个很爱玩的公司。它曾在MIT校园内到处张贴着一份密码，据说，这份密码包含了一个Google Jobs的电话号码，解开密码的人可以通过此电话留下自己的个人信息，进入谷歌工作。各位读者，你能解开这个密码吗？如果有漂亮的解答，我会在这里贴出来。