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.