Being interviewee: Array of array products

March 29, 2018

Introduction

It is my algorithm to write in the mock interview. I remembered that I have to work on one multiplication from left to right iteration using dynamic programming, and then two multiplications from right to left calculation.

I have to learn again to write a correct solution in less than 10 minutes. This time I spent 18 minutes, and also I got a hint from the peer. The peer told me to define a variable leftToRight to save product of array elements on line 18, and also switch the order of line 22 and 24 to assign the value first, and then do the multiplication next.

Code review

Here is my C# practice.

Dynamic programming should be daily practice

Dec. 16, 2017

Introduction

It is hard to get used to write bug-free code for dynamic programming. Specially base case handling.

Here is C# code I practiced on Dec. 16, 2017 10:00 AM. The code I wrote had a bug to handle the array with length 1, the product should be 0 instead of 1.

Feelings

This practice I felt much better. First I read the problem statement loud, and then I spent over 5 minutes to go over the test case, and explained the brute force solution and its time complexity. And then go to optimal one, how to apply the two linear scan integrated with left neighbor or right neighbor products with one more multiplication.

First try to explain very clearly the idea, and then it is very easy to write the code just following the idea.

I have practiced this algorithm more than 4 times since March, 2017. I still made an error on edge case. I just added tags for all past practice using Leetcode 238: product of array except itself, so I can easy go over the past practices and review them.

Get organized

It is most important task to get organized, review every practice in one setting. So I can figure out how I develop good understanding of the problem through each mistake, and also get some ideas what to work on next.

Source code is the key information to document how good/ not good I am in terms of algorithm analysis, coding style, and also whiteboard testing.


March 21, 2016, here is the blog about the practice.

Oct. 29, 2017, here is the blog about the practice.

Dec. 16, 2017 practice is Here.

Leetcode 238: Product of Array Except Self

Oct. 29, 2017

Introduction

It is over 30 minutes to write the algorithm based on the idea using dynamic programming. By going through the whiteboard testing, it took me two steps to come out the code passing all testing cases. First I wrote code to make sure that the value was correct, and then I change the code based on TED principle.

Code study

C# code is here.

I wrote two blogs about the algorithm, the first one is written in March 21, 2016. . The second one is here written in July 24, 2015.

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