Leetcode 18: 4 sum

May 2, 2018

Introduction

My young sister always criticized how selfish I am when we have time to argue about things on wechat recently. I like to refer this personality to the algorithm I practice. I noticed that I spent time to track how many views on code review web page related to the algorithm called array quadruplet, it is waste of the time. And then I decided to move on. I need to spend attention to other people who have shared their code on Leetcode discussion on this algorithm. So I studied over 30 minutes since there are so many of them I cannot finish all, and then I wrote my first post on the algorithm Leetcode 18: 4 sum discussion panel.

My post 

Here is my sharing. I like to write down my ideas to share as all others do on leetcode discussion panel on Leetcode 18: 4 sum. I also wrote C# code to pass the online judge. Here is the C# code.

I read one post from Microsoft intern, and here is the link. What I like to say is that I learn something from the author's experience.

Code review: Array quadruplet

April 30, 2018

Introduction

It is so happy for me to continue to practice Array quadruplet algorithm since last March. What I have learned through over 10 rounds mock interview is that I have to continue to learn the algorithm through each practice.

It is the big surprise when I chose the algorithm to ask the peer last Saturday 10:00 PM mock interview. I tried to test a senior in the university how good he is since he told me that he had ICPC contest experience in high school.

Build a hashmap on the fly

I like to answer my own question asked five months ago on stackexchange.com. Here is the question's link. Here is my answer's link.

Leetcode 4 sum discussion panel

I have to push myself to learn from others. One drill is to read as many discussion as possible, and try to figure out new ideas, creative thinking process. I spent 30 minutes to read through the discussion, and also wrote a reply. Here is my reply link.

I noticed that I had some issues, since I keep checking code review my answer link. I know that it is waste of my time. I should spend time to read more discussion on Leetcode 4 sum.

Sometimes I notice that I have to push myself to show concern to others, people in the community, and also give out support for other people's good thoughts and work they share.

To be selfish or pessimistic, it is not working very well in this fast-paced software industry. This is the first time I make this argument.


Here is my post to show my idea and answer for Leetcode 18: 4 sum. I did spend 30 minutes to read my submission eleven months ago and then I decided to write a new solution based on my practice on array quadruplet.

One step further

Here is the reply I gave to the most view answer 6.1 K views. I shared the tip to lower down the time complexity to O(n * n).

Being an interviewee: Array quadruplet

April 22, 2018

Introduction

It is my favorite algorithm called array quadruplet. I did talk about the analysis of the algorithm and then wrote down the algorithm without any bug and pass all test cases first time. Only thing I did is to include library using ..., I explained to the peer that I have worked on the algorithm multiple times, but one time a young lady who was preparing facebook onsite, she told me that I should simplify the code to check if dictionary contains key or not. So I only need to write three lines of code from line 57 to line 62, before I need to write if/ else and then update list in both cases.

Mock interview

Here is my C# code.

I still remembered that the first time I worked on the algorithm on mock interview platform. I had such difficult time. After I worked with over ten people on this algorithm, I followed every peer and understood how they think and analyze. So it is also very good experience to help the peer to work on the algorithm the first time. Here is the blog I wrote to give the feedback to the peer. 

Four Sum problem

January 28, 2018

Introduction

It is busy weekend. Today I had a mock interview at 4:00 pm,  I felt that I were a student to be interviewed for an algorithm, the teacher is questioning me everything, and make sure that I understand everything I write.

Code review 

Here is the code.

Highlights of interview:

1. First the data type of function on line 44, getTwoSum, its return type dictionary's key is integer, not string;
2. Second, the array should be sorted in ascending order. I forgot to write the first round.
3. Discussion of dictionary search algorithm time efficiency.

4 sum algorithm

January 21, 2018

Introduction

It is the most popular algorithm and also my favorite one. I asked Four sum algorithm mock interview practice on the code review two months ago on stackexchange.com. This time I had to write the algorithm in mock interview at 12:00 PM mock interview, I found that it is easy to write and also I finished the analysis and coding in 30 minutes.

Code review

Here is C# code with the analysis.

Leetcode 18: 4 sum

January 6, 2018

Introduction

I had a mock interview at 10:00 PM in May 5, 2018. I learned some JavaScript from the peer, but also I had to learn how to help the peer write a brute force solution using JavaScript. I had to write down the four loops and then also write the start index for each loop for the peer.

Brute force four loops

It is the first time I had to show the peer how to write brute force solution using four for loops. And also it is my job to fix the start index for the peer as well.

I made the comment to remove the line beside a while loop, and then line 12 to line 15, I changed the start index to i + 1 instead of 0, likewise to apply k and l.

Code to review

Here is the JavaScript code written by the peer in JavaScript, passing all test cases on mock platform. It is also a brute force solution.

I have to learn how to help the peer write a brute force solution first, and then let the peer understand the solution and get the good feelings to solve the problem.

Summary of five practice of Leetcode 18: 4 Sum

Dec. 29, 2017

Introduction

It takes over 6 months to learn one algorithm similar to Leetcode 18: 4 sum, and also each of five practice is helpful and also documented. I just need to go over them again and figure out what to learn from those practices.

4 sum algorithm

5th practice, Dec. 27 2017, here is the blog. After the practice, I updated the code review code with this version to replace 4th version written in Nov. 2017, and also added some commented in the question.

4th practice, Nov. 4, 2017, here is the blog. After the practice, I posted the question on code review.

3rd practice, August 31, 2017, here is the blog.

2nd practice, April, 2017, here is the blog.

May 2017, Leetcode 18: 4 sum practice is here.

Here is the link to search 5 practice using label: 4 sum practice, Leetcode 18: 4 Sum.

Leetcode 18: 4 sum

Dec. 27, 2017

Introduction

It is the cold day in the city of Vancouver, I spent the whole day inside the home for another vacation day. I have a whole week off. I only went out with my friends to take a walk in Burnaby central park, and I booked 3 mock interview 12:00 PM, 8:00 PM, 10:00 PM.

First peer is working on next January Google onsite interview, second peer is working on next January Facebook onsite interview. Third peer is from Shanghai, China, he had Google onsite 4 years ago, and then he prepares to get another one.

I was busy to observe how other programmers work on problem solving. My thinking is that young people are smart, and very good at communication, but lack of challenge in daily work or practice compared to working on Hackerrank contest advanced level algorithm. I want to see those determination and dedication in their problem solving process in the future.

 I went through the Hackerrank contest to work on advanced level algorithm, I understood that it is so hard to make things work, score zero from over 5 hours for a depth first search, but the algorithm cannot meet the time complexity requirement.

Those young peers are trying their luck, they will experience how tough the fight is after their onsite interviews. There are some candidates with a lot of practice and being able to solve the problem in less than 10 minutes.

Here is my records of practice:

Leetcode 4 sum

I had mock interview 8 PM. The peer has experience to work for Microsoft, and then I got advice how to improve my code.

My last practice is on Nov. 14, 2017. I wrote the blog the document the practice. And after that I posted a question on code review website but no one gave me review.

Dec. 27 is my fifth time I worked on the algorithm, I wrote exactly same code of 4th practice. But the peer gave me a few of advice to simplify the code.

The above code can be simplified. First look at the redundant code to manipulate the dictionary.

The first is to reduce four variable to two variables, save i, j instead of arr[i],arr[j], i, j. Secondly line 17 and line 23 are the same, extract them outside the if/else branches.

Here is the code after simplification.

Actionable Items

Look into those four companies, Nitanix, Uber, Qualtrix, Splunk.

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.

Leetcode 18: 4 Sum

May 17, 2016

Introduction

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write her own practice using C#. 

Will come back. 

January 31, 2017

Study C++ code first. 

Code review study here. 

Follow up

Dec. 29, 2017

It feels good to read the blog written 18 months ago. At that time, I was shy and do not write too much how I feel to learn 4 sum algorithm. At that time, I do not know that I can use Leetcode 18 discussion to find all the solutions. It is so interesting to know the person who I was 18 months ago. The code I liked at that time usually is searched from Google.

I like to review the blog written by TenosDolt, and then copy and paste the analysis of Leetcode 18: 4 Sum in Chinese here.

算法 2： 
O(n²)的算法，和前面相当，都是先对数组排序。

哈希map预处理

我们先枚举出所有二个数的和存放在哈希map中，其中map的key对应的是二个数的和，因为多对元素求和可能是相同的值，故哈希map的value是一个链表(下面的代码中用数组代替)，链表每个节点存的是这两个数在数组的下标；这个预处理的时间复杂度是O(n²

枚举第一个和第二个元素方法

接着和算法1类似，枚举第一个和第二个元素，假设分别为v1, v2, 然后在哈希map中查找和为target - v1 - v2的所有二元对（在对应的链表中），查找的时间为O（1），为了保证不重复计算，我们只保留两个数下标都大于 V2 的二元对（其实我们在前面3sum问题中所求得的三个数在排序后的数组中下标都是递增的），即使是这样也有可能重复。

Example study

比如排好序后数组为[-9, -4, -2, 0, 2, 4, 4]，target = 0，当第一个和第二个元素分别是-4，-2时，我们要得到和为0 -(-2) -(-4) = 6的二元对，这样的二元对有两个, 都是(2,4)，且他们在数组中的下标都大于-4和-2，如果都加入结果，则(-4,-2,2,4)会出现两次，因此在加入二元对时，要判断是否和已经加入的二元对重复. 

由于过早二元对之前数组已经排过序，所以两个元素都相同的二元对可以保证在链表中是相邻的，链表不会出现(2,4)->(1,5)->(2,4)的情况，因此只要判断新加入的二元对和上一个加入的二元对是否重复即可.

因为同一个链表中的二元对两个元素的和都是相同的，因此只要二元对的一个元素不同，则这个二元对就不同。我们可以认为哈希map中key对应的链表长度为常数，那么算法总的复杂度为O(n²).

Also, I will study the code written in Java and then write a C# version. First, let me save the java code in a gist first. 

One thing I like to read the blog written by TenosDolt is that he recommended a blog related to K sum algorithm in general.