Leetcode 238； Product of Array except itself

March 21, 2016

Worked on the algorithm LeetCode 238:

Product of an array
http://juliachencoding.blogspot.ca/2015/07/two-algorithms-questions.html

http://fisherlei.blogspot.ca/2015/10/leetcode-product-of-array-except-self.html

Julia likes to share some tips about writing the code, assuming that you know the optimal solution is using dynamic programming (DP), and extra space is O(N).

For example,

Array: [1, 2, 3 ,4], denoted as arr[].

for each i, i = 0 to 3,
product of i, denoted as P[i],
leftP[i]   = arr[0] *arr[1]*...arr[i-1] = leftP[i-1]*arr[i-1].
rightP[i] = ...
P[i[ = leftP[i] * rightP[i]

write C# code:

1  public static int[] getProduct(int[] arr)   // not A, match description: arr  <- complaint 1, style
2 {
3      if(arr== null || arr.Length ==0) return null;
4
5     int n = arr.Length;
6     int[] res = new int[n];
7
8   int tmp =1;
9    for(int i=0; i< n; i++)
10   {
11       if( i ==0)         // <- complaint 2: 
12            res[0] = 1; // <-  complaint 2: not necessary, remove if clause

}

So, write again starting from line 9. Remember the analysis, only thing you have to do, one multiplication, one extra variable to store previous result - tmp.

Code should match the analysis <-  Julia learned the lesson. 

8    int tmp = 1; 
9    for(int i=0; i< n; i++)
10   {
11       res[i] = tmp;   // it works when i = 0; 
12       tmp *= arr[i];
13   }

    that is the code for leftP[i].

Next practice:
https://www.hackerrank.com/challenges/computing-the-correlation

https://www.hackerrank.com/challenges/unbounded-knapsack

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的电话号码，解开密码的人可以通过此电话留下自己的个人信息，进入谷歌工作。各位读者，你能解开这个密码吗？如果有漂亮的解答，我会在这里贴出来。