Leetcode 18: 4 Sum

Nov. 4, 2017

Introduction

It is such a great mock interview this morning starting from 10:00 am. I had to work on the algorithm Leetcode 18: 4 sum in the time limit of 35 minutes. I did a few things to make the mock interview great learning experience. I wrote an algorithm, passed the compiling and then passed all test cases without any bug. The algorithm has optimal time complexity although extra space is needed.

Here are highlights:

 1. I chose the algorithm using time complexity O(n²). Two sum pairs are saved to the dictionary for lookup later on.

 2. Whiteboard testing was very helpful, I chose the easy one [3, 2, 1, 4, 5] and the given 4 sum is 12 = 1 + 2 + 4 + 5. Compared to the test case given in the problem statement, this one is easy to follow.

3. Through whiteboard testing, I found a bug in my design. The array may have duplicate numbers, and then I spent extra 5 minutes to change the design, in line 78, I added two extra elements in the array to save index number of the array.
newList.Add(new int[]{no1, no2, i, j})

4. Through the whiteboard testing, I modified the code to make it more easy to follow. I added var no1, no2, no3, no4, assuming that no1 <= no2 <= no3 <= no4, and the index of four numbers in sorted array is in ascending order.

5. I spent less than 3 minutes to fix all compiling errors.

6. The code runs and pass all test cases without any bug.

Code review

The code I wrote in mock interivew in C# is here to view.

Based on my last practice on Leetcode 18: 4 sum in August 2017, I worked on the feedback. I need to write a run-through code, I have to simplify the solution in order to fit in 30 - 35 minutes.

A few things I did are very helpful to expedite the process this time. The most simple test case is chosen to do whiteboard testing; the whiteboard testing is not a fake one, in the process of testing, I found a bug first, and then came out the fix, and in-between I added a few more variables to make code more easy to follow, avoid bugs.

Feedback from the peer

The peer did not choose to use the video, but her knowledge of algorithm is very helpful. I did have chance to learn the algorithm compared to two pointers techniques.

Leetcode 18: 4 sum

August 31, 2017

Introduction

Plan to continue to work on 4 sum solution, using hashtable to store all possible two sum, and then look for 4 elements with the given sum. I chose to write the solution instead of using a two for loop for the first two elements, and then two pointer technique to find a sum value. This is the first time I wrote the idea and I like the adventure.

30 minutes practice code is here.

In the mocking practice, I explained to the peer that I have to write a function to determine that 4 indexes are unique. In other words, assume that 4 indexes are a, b, c, d, then at least 4 comparisons are needed, a != c, a != d, b != c, b != d. Actually there are a lot of duplicated pairs for a < b < c < d four numbers to a given sum, (a, b) and (c, d) are two pairs with sum a + b + c + d, or (a, c) and (b, d)  with the same sum, etc., to simplify, we can enforce that the pairs to look for are (a, b) and (c, d) only.

I thought that it will take a few minutes to write the logic, and gave up the writing in the mocking. Since in the mocking interview, I was not sure that I should simplify the search, enforce the rule to apply a < b < c < d, therefore the checking will be very simple as b < c, in other words, the second element in the first pair is smaller than the first element in the second pair.

9/1/2018

The C# code passes all test case, I did fix the grammar error, and also simplify the search. I try to search two pairs in the ascending order. First sort the array, and then iterate any pair less and equal half the given value, find another pair with index of array (start, end), the start index is bigger than the pair's second argument's index.

C# code is here. Last practice is on April, 2017, the blog is here.

A very competitive peer 

A few things I learned from the peer. If I am the interviewer, I should explain the problem to the interviewee, and then let interviewee ask questions to clarify the problem. I do not explain the algorithm to the peer when I am the interviewer, but this time the peer asked me to explain the algorithm at the very beginning, and I was told that I should explain the problem as the normal interviewer does.

The fact is that only two or three peers out of 80 mocking experience did explain the algorithm to me at the beginning. Now I knew that it should be always the case.

Do not just let the interviewee to read the problem statement and then figure out the algorithm.


Try to simplify the algorithm, otherwise I cannot finish it in 30 minutes. The peer thought that it is better to have a working solution instead of having a solution not completed.


Write test cases by yourself first, instead of using "Run tests" feature embedded in the browser.

Feedback

Leetcode 18: 4 sum

April 6, 2017

Introduction

Julia learned through the mocking experience of the algorithm. 4 sum algorithm optimal time can be lowered to O(N²), not O(N³), not brute force O(N⁴). Although it takes O(N²) space to build a hashtable to store all possible pair of two numbers in the array with the sum and two index of numbers, the algorithm actually beats O(N³).

It is Leetcode 18, Julia learned from the mocking experience. She did not follow the hints at the beginning, she wrote a 3 sum algorithm, which takes O(N²)time; but when she tried to put all possible 3 sum into hashtable, then time complexity will go up to O(N³⁾.

A few things she learned from mocking experience:

1. Stay calm, write down everything slowly. There is a lot of time if it takes slow.
2. First 10 minutes it can be good brainstorm.
3. Try to find the optimal algorithm, take first 5 minutes to think about by yourself first, do not say anything until you are sure about the optimal solution
4. Keep the first 5 minutes private as long as you are not cheating, until you have to say something.

Values of the mocking experience 

Julia did not continue to practice mocking experience when she did not fully experience what she should work on. She stopped at the end of March 2016 with 8 mocking experiences. She guessed that she moved on to practice more on hackerrank coding online test.

The statistics shows that 15 mocking experience will be at least. It is not easy to get those 15 mocking experience. So far, Julia only had 2 times experience starting this April 1. She still has 5 mocking experience to go before she reaches 15.

She understood that she has to focus on problem solving, do not pay too much attention to the partner. But she needs to respond everything he/ she says.

Julia can write better maintainable, readable and clean code compared to April 2016. She just needs to learn how to work with people face to face, through mocking interview experience, she has less emotions.

Problem solving rating 

Last 2 experience, in the problem solving category, first time she got rating 2 of 7, second one is 4 of 7. 4 of 7 is related to "working out a brute force solution". Even though the first two mock interviewers are totally different in technical skills, but one thing is common. Optimal solution is the king, need to do some study on space and time tradeoff. 

Time complexity is much more important to battle, using space to trade time complexity. Processing something first and save into memory, using as less as time as possible.

Mocking season 

She missed the first two months of practice from January to March. Usually this is the season a lot of high competitive players are practising mocking experience, Julia should have chance to meet a lot of good players and learn from the experience.

Algorithm

Statistics 

Problem solving skills - 4 out 7

Follow up 

May 29, 2017

1.  using HashSet to find unique numbers.
Leetcode 18 - 4 sum, C# practice is here.
2. Try not to use HashSet, and see if it is solvable.