Scalability Harvard Web Developemnent

January 31, 2018

Plan to watch the video again. Here is the link, the length is 1 hour 45 minutes.

Leetcode 726: Number of Atoms (II)

January 31, 2018

Introduction

It is so nice to watch a video of Leetcode 726: Number of Atoms. I like to spend 20 minutes to watch the video first, and then write down some notes here.

Video lesson

Here is the video to watch.

Coding blog

Here is the coding blog. I plan to study the code as well. And then I will write a C# solution based on the idea.

Here is Java solution. I will work on C# solution based on Java code.

C# code practice

I spent 90 minutes to write the C# code. Here is the code. I felt that it is like flatten dictionary, only difference is to handle close bracket to return dictionary. Every close bracket will be handled right away, which likes a leaf node in the tree.

Leetcode 726: Number of Atoms

January 31, 2018

Introduction

It is the last day of January 2018, I like to celebrate the first month of 2018 using one hard level algorithm. I found one today by reading a Chinese algorithm blog, the link is here. The algorithm is hard level one on leetcode called Number of Atoms. I know that it will take some time for me to understand the algorithm with hard level.

Algorithm study

Plan to study the Chinese blog and write down some notes. One thing I like to do is to read the chinese blog, and go over each word, try to put together and make it more readable first. And then write down a few things to look into, highlight them, and plan to go over it again later.

三种方法，第一种采用递归，而后两种采用栈式结构。

 方法一：递归

首先编写一个解析器Parse，这个解析器应当能统计出从当前字符串位置开始，直到遇到一个右括号“）”或读到字符串末尾，然后连带上右括号“）”后面可能跟上的数字，这可做为一段整体。

用一个counter来记录这一段各个元素的个数。最后返回counter。

1. 首先初始化counter
2. 在解析器循环中：
1. 当遇到左括号“（”时，就递归调用Parse；并把Parse子程序中元素统计结果加入当前的counter当中。
2. 如果不遇到左括号，那么会发现一定是大写字母，也就是一个原子名称的开头，那么就统计这个元素的个数。
3. 循环结束后，检查右括号后面是否跟有数字，如果有的话要对当前的counter进行相应倍乘。
4. 最后返回counter。
5. Parse可以写成一个递归函数，然后用主函数做驱动函数。

方法二：采用栈式结构

和第一种方法类似，不采用递归函数，采用栈来进行操作。（其实函数的递归和栈本就具有极大的相似性）
先初始化counter栈，然后仍旧需要一层循环，直到读完所有字符。

循环中：
1. 当遇到左括号“（” 时一层新的counter入栈。
2. 遇到右括号“）”时栈顶counter弹出，并检查后面是否跟有数字，如果有的话对当前counter进行相应倍乘，并把结果累计到新露出的栈顶。
3. 遇到大写字母，就统计这个元素的个数，计入counter，类似方法一。

方法三：同方法二，但是不手动解析字符串，而是采用正则表达式

规则表达式Regular Expression，通常被用来检索、替换那些符合某个模式的文本.

把字符串分成一个一个独立的块，这里采用的表达式为："([A-Z][a-z])(\d)|(()|())(\d)"。这里面的块分别表示：可能带有数字的元素如“Fe3”、“H”等；左括号“（”；可能带有数字的右括号“）”、“）3”等。
然后在循环中对正则表达式中的每块进行各自对应的处理。

复杂度分析

无论哪种方法，理论的复杂度相同。但是这里推荐使用第三种方法，因为栈式结构比递归的写法更加简洁, 还有第二个原因, 正则表达式极大地简化匹配操作。

时间复杂度

O(N^2)

这里N为字符串的长度，遍历一遍字符串需要O(N)的时间，但是当遇到左括号时，会对子式的元素向外累加，这就有可能达到O(N)的时间，而总字符串长度为O(N)，所以左括号的个数为O(N)（注意大O记号的含义是“不超过”，这里的意思是不超过线性界，而不是等于线性界）。故所花时间为O(N^2)，

这里给出一种时间比较逼近N^2的表达式：A(B(C(D(E(F3)4)5)6)7)。

注意：正则表达式的时间界不容易判断，这里正则表达式没有回溯，所以总的时间复杂度不会超过O(N^2)，这与正则表达式的实现方法有关。

空间复杂度

O(N)，这里无论是栈还是Map，空间复杂度不会超过O(N)。

Being an interviewer: System design - design instagram

January 31, 2018

Introduction

I do not have chance to sit in the classroom to learn the system design, and then I do not plan to learn system design today. But today the peer had super performance, first 40 minutes he passed through all four algorithms, including array, recursive, graph and then dynamic programming. So I asked him to have a system design question, design instagram with scalability.

System design best one

It is so enjoyable to learn through the best system design in the world.

Here is the transcript. And the best thing is that I can watch the video again and again, learn every step he developed the design. The interviewer has more than 10 years experience to work on search engine in the city of Seattle, USA.

Every time I feel stressed to learn system design, I just go back to watch the recording, and then learn from the best.

I remembered one time I met the senior developer working for Microsoft fifth time in mock interview. I told him that I work as an interviewer in another platform. And he asked me how much I get paid. I laughed about it.

Transcript starts here:
end here.

Follow up 

Nov. 15, 2019
I like to review the notes again. I like to spend 10 minutes and learn from my own experience. What should I do in terms of system design? I did not have chance to write so many content in my Facebook onsite in August 2019. I was interrupted before I like to talk about diagram, distributed file system or storage.

maximum number of chunks

January 31, 2018

Introduction

I cannot believe that I have strongest peer in the world and then I just need to find some good algorithms, and then I can get tutored through the mock interview. I could not believe that I got matched with super talent programmer, good lord, machine learning algorithm does great job for me tonight.

Algorithm code review

Here is the transcript to understand the algorithm.

Float number and operators algorithm

January 31, 2018

Introduction

I was thinking whole day how to come out the recursion in the correct order on this algorithm called Float number and operators algorithm. Tonight I met a super talented programmer with over 10 years experience to work on a large scale system, and he taught me how he approached the problem in less than 10 minutes.

Code review

Since I already checked the peer's code skills, I just asked the peer write down a few lines of code and try to get his idea.

Here is the pseudo code. Perfect order to fit for flat precedence. Only one hint using [1, 12, -3] on line 30.

Leetcode 54: Spiral matrix

January 30, 2018

Introduction

It is such a big surprise that my first mock interview as an interviewer turns out big success. The peer solved all four algorithms I asked in first 40 minutes. He is the best peer I have met in my peers, over 150 peers.

Best thing is that I got education how to design a perfect system design: Instagram scalability in 30 minutes. I could not believe that I may interview a top company senior developer in the future.

Code review

Here is the C# code I like to learn. The idea is very clear and it is the production ready code.

Leetcode 123: Buy and sell stocks

January 30, 2018

Introduction

I have to learn the algorithm again, I believe that the algorithm of dynamic programming is such an interesting learning experience. It is like seek and hide game, every time I come back to work on the algorithm, it is like a new algorithm. What is happening?

Recursive

Please solve the problem once and then build the recurrence formula. This time I also like to watch the video and see if there are some new tips.

Follow up

Feb. 16, 2018

Here is the gist I saved from the blog to talk about dynamic programming related Leetcode algorithm.

Other two gists are written in Chinese about dynamic programming. Here are the link 1 and link 2.

AlgoExpert - 55 algorithms

January 30, 2018

Introduction

I got advice to look into those algorithms on the website algoexpert.io. I like to spend some time to learn those algorithms marked as free videos first.

So nice a Monday

January 30, 2018

Introduction

It is such a nice Monday, I am back to daily work and try to learn something from frontendmasters.com. Also I had a 10:00 PM mock interview, I learned an idea to work on reverse the sentence, with a minor bug in the implementation.

Code review

Java code is here.

Say goodbye to the weekend

January 29, 2018

Introduction

It is time to say goodbye to a busy weekend, now it is morning time 7:40 AM before I prepare to leave home for a new work weekday. Last weekend I had thirteen mock interviews first time. The interview started from the Friday evening and ended in the last hour of Sunday evening.

Let us take a look the schedule, I only went out for quickly grocery shopping in Saturday, I did not have time to go out to play sports, swimming.

It is so enjoyable to spend time to talk about algorithm using C# language, JavaScript, Python, Java this weekend, I met so many talent programmers and it is the first time I practice so many algorithms in less than 3 days.

Good experience

I applied some skills I learned from church small group meeting to the mock interview. I am getting better on those algorithms, learn a few things to make me better to write dynamic programming, recursive function.

What I have learned

Do not memorize the algorithm. Try to show some reasoning.

I still remembered that the peer told me that he read my post on quora.com about mock interview when I shared my coding blog, and then I had chance to get the trust from the peer, he shared me a lot of tips and also got invited to join Google foobar.

Deletion distance algorithm

January 28, 2018

Introduction

It is very hard for me to learn a dynamic programming solution to solve deletion distance. One thing I have learned is to understand the difference between recursive and dynamic programming. The peer is a latest computer engineering PH.D. from top university, he asked me tough questions. I had hard time to go over the analysis and answer his questions, but I managed to learn and answer correctly.

It is not good to memorize the solution, that is the reason I seek for the advice for each mock interview. This time I had chance to learn from top graduate and understand how important it is to be able to explain the algorithm.

I have to understand the algorithm and be able to defend my analysis. Mathematics is my undergraduate study major, I love to prove something based on theorem.

Analysis and code review 

Here is the transcript I wrote in less than 30 minutes. 

Leetcode 54: Spiral Matrix

January 28, 2018

Introduction

It is the algorithm I have to write on my 10:00 PM mock interview. I worked on the spiral matrix, and it took me in total 20 minutes to explain the solution and write the solution to pass all test cases.

Code review

The peer told me that I can save the space using four pointers instead of visited array. I explained to him that the mock interview is for me to write the correct solution using minimum time.

Here is the C# code I wrote.

Advice from the peer

January 28, 2018

Introduction


It is something I learn from the work. I have to let people talk and then learn something from the conversation. Recently the office coworker shared the tip to use Vancouver library card to access Lynda.com 6000 courses.

Today I had 8:00 PM mock interview. The peer shared with me the tips what to learn through so many resources. I write down and will look into later. One thing he told me is to use New York library card to access Lynda.com courses.

Here is the link.

Udemy

January 28, 2018

Introduction

I had a mock interview 6:00 pm, the peer advised me to check udemy.com. You can get a good quality course on react over there.

Learning JavaScript

January 28, 2018

Introduction

I had 6:00 PM mock interview. I had 30  minutes to learn how to write JavaScript from the peer, who went through full stack academy.

JavaScript code

Here is the code I reviewed to apply binary search in the array and find smallest index which equals to the element value on the index.

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.

Power function do it yourself

January 28, 2018

Introduction

It is the algorithm the peer shared with me on 10:00 PM mock interview January 27, 2018. Learning algorithm is kind of fun. I have to read python code, and also I learn how the peer wrote down his solution using memoization, and later he told me that the friend told him to remove memoization, just use one recursive call to reduce the number to half.

Code review

Plan to study the algorithm and review it later. The code is here.

Find first missing number

January 28, 2018

Introduction

It is the algorithm for me to work on this 12:00 PM mock interview. I like to review the analysis and code.

Code review 

Here is the code with the analysis.

Leetcode 6: Zigzag conversion

January 28, 2018

Introduction

The peer asked me to work on Leetcode 6: Zigzag conversion today after the mock interview. I wrote down my idea, here is the link.

Guess 4 digit number algorithm

January 28, 2018

Introduction

It is very good practice to ask the peer to give me an algorithm to work on, through the discussion, I can learn something from the peer quickly.

This is the algorithm I like to continue to work on. It is called "Guess 4 digit number algorithm".

I got Google foobar invitation

January 28, 2018

Introduction

I read the story on code review website about Google foobar. And I got the invitation to join Google foodbar. I was so excited to have chance to work on some algorithms over there.

Convert a binary search tree into a double linked list

January 28, 2018

Introduction

It is good idea to ask the peer what is his/ her favorite algorithm. I had a mock interview 12:00 PM today, after mock interview, we discussed several algorithms. One algorithm is to convert a binary search tree to a doubly linked list.

Here is the link on Leetcode discussion.

Learning python

January 28, 2018

Introduction

I met a peer second time in one month and she used python. What I like to do is to learn python through mock interview, and write down notes when she coded. Python is easy to follow and quickly to write. The peer told me that she works day time using C++ but she chose to write python for mock interview.

The peer started to write python since she was in the university, actually she graduated from MIT. The python code should be pretty good.

Python code about matched brackets

Here is the code.

Design a data structure

January 27, 2018

Introduction

I had a conversation with the peer after mock interview. One thing we discussed is about the data structure design. He asked me to design and data structure to do insert for a range numbers from array, I quickly thought about binary index tree. And he also said something about interval algorithm.

Algorithm related to binary index tree

It is time for me to look up Leetcode and find the algorithm. I asked the kindergarten adventures on code review stackexchange.com a while ago. It is time for me to learn the algorithm through a simple example.

H-Tree algorithm

January 27, 2018

Introduction

I practiced one more time on H-tree algorithm at 4:00 PM mock interview. I was really appreciated to have chance to look into time I need to spend. I tried to cut time short, so I meet the expectation from the interviewer on interviewing.io. Time is money, time is asset. If I can make it 10 minutes, why I like to spend 20 minutes. Extra 10 minutes I can work on another algorithm, usually it only takes 10 times to work on one algorithm, the interviewer does not need to see you code every algorithm.

Today I spent 20 minutes to write the algorithm with some analysis. But I tried to cut the analysis to minimum.

Algorithm code review

Here is the code.

Use bit manipulation to solve problem of power of n

January 27, 2018

Introduction

I really like Roger Federal as a professional tennis player, but I never have any chance to talk to him. But do not worry, today I had a chance to talk to a programmer from Switzerland, he speaks exactly same as Roger Federal does, a Switzerland accent. And he also tried to teach me the algorithm called power of n using bit manipulation.

I did some research after mock interview. Here is one article about the detail.

I just could not believe that I got best help from top programmer through mock interview this weekend.

Here is the algorithm the peer wrote. The great thing is to watch him how he did the testing using 5² and then after the testing, he cleaned up the white board testing code. He just quickly demoed how he wrote a new code and also tested and put it in the production, nicely presented after removing those test cases.

Catalan number

January 27, 2018

Introduction

It is another mock interview and I had to work on the algorithm related to Catalan number. This time the peer dropped a hint, do not need to use previous row, only use current row and then save the space. I wrote the code based on his advice.

Algorithm 

Here is the code based on the advice from the peer.

floats number and operators and how to get maximum number

January 27, 2018

Introduction

I had this mock interview on interviewing.io, and the I noticed that the peer is anonymous but he is machine learning algorithm computer science Ph.D. with a few years experience.

Mock interview performance

Here is the transcript related to the discussion and my code written in the hurry. The code is copied from the record video at 55:01/ 1:00:16.

Highlights of mock interview performance:
Line 44: I tried to define the subproblem, what are the subproblems?
Line 120 - 128: I narrowed the subproblems to max/ min value. 

After mock interview 

Here is the algorithm I tried to write after mock interview, it has some bugs in there.

For example, [1, 12, -3], if we use the recursive function, then it is 1 - (12 * (-3)) = 1 + 36 = 37, but since the precedence is flat, 1 - 12 * (-3) = -11 * (-3) = 33. So we may have to process the array in reverse order instead, I have to investigate on the issue.

Here is the code from the friend I met on pramp.com.

Major hint complaint

I got feedback from the peer, the peer told me that I need major hint and also the solution is a brute force solution.

Here is the feedback I got after January 25 mock interview. 

Follow up 

The solution is attached here. Also I posted the question on codereview.com, and the link is here.

Hard level algorithm is a good choice?

January 27, 2018

Introduction

It is most important to learn something from Silicon Valley engineering culture. I am in the city of Vancouver last eight years. Last week I had 3 mock interview on interviewing.io, I learned something about mock interview the first time.

Hard level algorithm is biased

The interviewer told me that the very hard level is biased for people who have worked on the algorithm before. The interview from facebook mostly is focusing on the data structure efficient, bug-free code. Dynamic programming or string manipulation algorithm can be very hard to work on.

I had to work on group of anagrams, and then I felt so good and then spent over 25 minutes. But the interviewer gave me feedback. In order to pass his interview, the interviewee usually takes 12 minutes to go over the problem and also write the solution.

I have to work on his advice. The peer has over 500 mock interview experience so he told me the truth the facts in terms of competing for any position in top ranking start up and software companies these days in Silicon Valley, California.

Here is my mock interview practice.

Follow up 

Feb. 12, 2018

I meet a peer on mock interview platform, and then he told me that he got rating 4 out of 4 on this algorithm group of anagrams. He did talk about all four possible solutions, including short word using sorting with time complexity O(n * mlogm), m is word's length;

Leetcode 10: regular expression matching

January 26, 2018

Introduction

It is another 8:00 PM mock interview. The peer is top ranking computer science master student, and she helped me to work on the dynamic programming solution of Leetcode 10: regular expression matching. First time after I practiced over 5 times on mock interview, I wrote a dynamic programming solution and passed all test cases.

Code review

Here is the C# code.

Highlights of changes in mock interview discussion advised by the peer. I told the peer that she paid so expensive tuition as an international student, and spent half hour to help me and tutor me to work on dynamic programming solution, I am so appreciated her help. She also thanked me to give her advice as well.

1. Line 15, change dp data type from int to bool;
2. Line 32, add i - 2 >= 0 in case index-out-of-range error;
3. line 39, use row, col variable instead textIndex, patternIndex;
4. line 50, remove dp[row, col] = 0 since the peer told me the default value is 0;
5. line 58, need to change dp data type from integer to bool, otherwise the expression is too hard to read.

Follow up 

May 9, 2019

Here is the code I wrote and fixed the issue and passed online judge.

Web Security on frontendmaster.com

January 25, 2018

Introduction

It is time for me to calm down and work on some courses on frontendmasters.com. My favorite topic is web security. The course link is here.

Now it is 9:12 PM, I have a mock interview at 9:55 PM. So I have over 30 minutes to watch the video.

Light speed to learn binary search algorithm

January 24, 2018

Introduction

It is another 10:00 pm mock interview. I met a peer and then I observed how quickly the peer came out from the Newton method, and in less than five minutes, he came out his own style of binary search algorithm and solved the problem.

The peer told me that he learns the programming by himself.

Code review 

Here is JavaScript code.

The peer wrote a few lines of console statement, and then he just quickly removed them once the code passed all test cases. Just unbelievable the peer can learn the binary search in light speed.

The code is not perfect, but the peer showed me how good he can learn and how fast he can learn to write the algorithm and also solve the problem.

Since it only takes a few minutes for the peer to learn, I called it light speed.

Follow up 

Feb. 21, 2019
The interviewee joined Google in July 2019.

Mathematics series

January 24, 2018

Introduction

It is interesting to look into mathematics series, so I can prepare better for the algorithm problem solving. I still remember that first time I came cross this encryption and decryption problem, it took me over one hour to get used to work on the combinatorics analysis and find the sum of source string in encryption formula.

I had a mock interview 10:00 PM today. And I practiced one more time to do analysis of the algorithm and also wrote a solution. The peer is a new graduate from top university of USA. So I had good time to communicate and write down the combinatorics formula. Feel so good. I still remember the feeling to work on Introduction to Combinatorics home work back in 1996 when I worked on Math department graduate study in Florida Atlantic University.

Code review

Here is the C# code. I like to improve my analysis of the algorithm. In terms of writing and how to derive the formula through the problem statement.

Specially I added extra two lines (line 61 and line 63) so that I can explain the idea to the peer and he could understand better.

Actionable Item

Plan to read Series wiki article. The link is here.

Leetcode 54: Spiral Matrix

January 24, 2018

Introduction

It is the algorithm I have practiced over 6 times in mock interview and also interviewed other 6 peers from March 2017 to January 2018. On January 23, 3018 10:00 pm, I had my first mock interview on interviewing.io platform, and then I had to work on the algorithm. What I learned through the mock interview is to get rid of those 4 for loop inside a while loop. In other words, the interviewer told me that in order to perform a 20 minutes coding interview, I have to write only one loop, and adjust the direction accordingly.

Mock interview 

Here are the hints the interviewer gave to me:

1. After 20 minutes, he wrote down four directions in two one dimension array.
dr = new int[]{0, 1, 0, -1}
dc = new int[]{1, 0, -1, 0}

2. After another 10 minutes, he gave second hint to use visited array [][] to mark the visited node.
3. After that, he gave me another hint, how to write a checking for direction change.

if(row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col] == 1)
{
      // change direction
}

Here is the transcript I copied from video clip at 50:00 of 51:00.

After the mock interview 

This the first time I used interviewing.io to practice mock interview. It turns out that the interviewer is much strong in technical skills and also interview skills. I have played the interview recording twice, and here are something I have to work on.

1. Do not interrupt the interviewer.
2. Say something like "Let me think about two minutes.". Actually calm down and think carefully in two minutes.
3. Stay calm and speak slowly.
4. Take hint and write down the hint quickly, and really think about hint. Follow the hint.
5. It is too slow to take the hint, and work out a solution based on the hint.
6. I should work on the example and write fully functional C# code in mock interview.
7. Check the time I spend and act fast.

Define the keywords for the problem, write down in mock interview. So it is very easy to discuss with the peer for various ideas. Seek and you will find, brainstorm the ideas related to time complexity, space complexity.

Direction - There are four direction. Change direction if need, in the order of clockwise, starting from top left corner (0,0).
Range - Stay inside the array
Visit - visit each element in the array only once. Do not visit more than once.
Order - follow the order of clockwise, start from (0,0).

Ideas can be searched through those keywords. Let us go over one keyword together.

For example, direction can be managed smartly using array for four direction, or manually specified. Every edge in one direction can be specified by start point and end point two variables, but it also can be implicitly specified using visited array. Just relax and talk to the peer in mock interview, and go over each possible options. Evaluate pros and cons, have a conversation.

Follow up 

Here is the C# code I wrote after the mock interview. I really like the idea and the solution is so easy to write, I write on purpose to add fourDirections in order to make the code more readable.

I am planning to post a code review on the stackexchange.com as well. The link is here.

Feeback is gold

It takes a village to raise a child. 

Interviewing.io is my new village. 

Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays (II)

January 23, 2018

Introduction

I came cross the algorithm this evening while I attended word press meeting in Vancouver down town Microsoft office. I started to think about the algorithm. I like to write down how I analyze the algorithm systematically, look like an engineer.

The algorithm link is here in Chinese.

Brainstorm the ideas

Need to brainstorm the ideas. Write down a list of ideas to work on.

Overlap – constraint, how to handle it?

Need to find  3 * K distinct elements in the array, and also 3 subarrays in the array not overlap

3 subarrays, how about one subarray, two subarray, four subarrays

It seems like 2 sum, 3 sum, 4 sum, k sum problem.

How to find three sum of subarrays? Enumerate one of the subarray, and search other two with maximum sums.

Two subarrays
We can use O(N) time, we just enumerate all possible subarray for the first one with small start index, and then find maximum subarray on it right side.

One subarray
We can using O(1) time to solve it. Preprocess the array using O(N) time and also dynamic programming to get any index and its right side maximum subarray sum or left side maximum subarray sum.

How about thinking bottom up?
Work on 1 subarray, and then two subarrays, and then three subarrays? Instead of breaking down three subarrays to two subarrays to 1 subarray.

Top k sum of subarrays
Let us differentiate the problem with top three sum of subarrays or top k sum of subarrays problem. 

Try to avoid complicated math theory, we even cannot tell that top three sum of subarrays with non-overlapping can add to maximum sum of three subarrays. 

Preprocessing

Preprocess the array using dynamic programming, we can do the work using O(N) time. What is the common calculation we can do for the algorithm. 

What is the time complexity we can target to solve the problem?

What is most common problems on solving this problem? 

Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays (I)

January 23, 2018

Introduction

I came cross the algorithm this evening while I attended word press meeting in Vancouver down town Microsoft office. I started to think about the algorithm. I like to write down how I analyze the algorithm systematically, look like an engineer.

The algorithm link is here in Chinese.

Step by step

Thinking process is more important for me right now. I know that I have improved a lot how to write clean code, readable code through last 8 months mock interview practices.

Let the journey begin, how to approach a problem like an engineer.

First of all, let me write down the constraints:

Integer array, given K value, find 3 subarray, non-overlap, the sum is maximum.

What is the time complexity for the algorithm? linear, or n², or higher time complexity? Can we solve the problem using linear time?

Of course, brute force solution takes O(n³) time. Just try to find 3 start index by enumerate the index value from 1 to length - 1.

How to approach the problem?

If it is neither in mock interview nor in phone screen. Let us work on the very basics and take time. I did take more than 30 minutes to think and write down the notes. 

Non-overlap constraint

If constraints non-overlapping is not required, so the problem is very easy, just use O(N) time where N is the array’s length to get the top three sum of subarray by linear scan the array from left to right.

Each iteration only one addition one subtraction and apply dynamic programming techniques.

K = 2, the array size is 100

What if we work on this task, K = 2, array size is 100. How do we find those three subarrays with maximum sum?

Preprocess the array using O(N) time

We can easily preprocess the array to get any index with its maximum sum from i = 0 to current index – 1, each index with size K subarray. It is processed by scanning left to right using Dynamic programming and time complexity O(N).

Likewise, we can preprocess the array to get any index with it maximum sum from i > currentIndex to length -1. It is processed by scanning  the array from right to left using dynamic programming and time complexity O(N).

How to find 3 subarray with top 3 sum?

It is not good idea, since first those top 3 sum may be overlapped, and then we can prove that top 3 sum may end up biggest sum of 3 subarray. In theory, it is not true.

Left, middle, right 3 subarray

Let us think about the order of search, how many options? Start first, and then search rest two; start last, and then search first two; or start from middle one, and then search left and right both sides.

Find left subarray first

Brute force first one for its start position, and then we will work on the subproblem to find two subarrays to get maximum sum. The subproblem to find two subarrays is with time complexity O(N).  The whole solution will be O(N²).

Find middle subarray first

Advice for Julia 

It is good idea to write something down for my favorite hard level algorithm. Maybe I also should write down something to make it more pleasant later on to review.

Like the mistake I make in the first 30 minutes thinking process. On January 22, 2018, my mistake is to mix the algorithm with the problem "Find top kth sum of subarrays in the array". The algorithm I tried to solve is much more complicated and then I thought about more than ten minutes.


On Jan. 22, 2018, second mistake I made is not to enumerate all options for three subarrays.What I mean is that there are options, work on leftmost subarray first, or middle subarray first, or rightmost subarray first.

On Jan. 22, 2018, third mistake I did not realize I need to brute force one of subarrays. Ask myself why?

Brute force one of subarrays, and then try to find the rest using preprocessed result, looking up only takes O(1) time. Only work on the middle subarray first, and then left is maximum subarray, right is also maximum subarray.

Draw a circle

January 23, 2018

Introduction

It is one of my favorite algorithm called Draw a circle. I had some discussion with the peer after the mock interview 10:00 PM. I also like to revisit the code I wrote in 2015. So happy to read the blog and then I can learn from the experience.

Follow up 

January 23, 2018

I traced my outlook email and then I found out that it is one of my phone screen algorithm I got in 2012. I supposed to write in 20 - 30 minutes, and at most 40 - 50 minutes.  

"More detail about the draw circle program, in first 10 minutes, I came out a mediocre solution, an then I tried to catch up while coding to put more ideas in, so I changed the original idea to set a target, and then made this 1000 tries to reach the target; the algorithm is like an undetermined optimal algorithm, with a lot of mistakes, losing the focus sometimes. I should have clarified the requirements with you before I started yesterday and work in the right direction. "

It is such a great feeling to read what I wrote in 2012. It is more than 6 years ago. At that time, I was too shy and I did not have habit to write daily. And I still remembered that I was so excited to have a phone screen, at that time, as a software developer, I was too isolated and my personality was kind of introvert. I was afraid to write down what I think at that time.

C# code I wrote in Dec. 2012 is here. Read the code I wrote more than 6 years ago. How to define the feeling? It is like meeting an old friend, sweet and sour. But this time the sour is mild level, code smells make the sour feeling. 

Leetcode 752: Open the lock

January 23, 2018

Introduction

I asked the peer to give me his favorite algorithm after 10:00 PM mock interview, so I can solve the algorithm and later we can discuss together. He shared with me Leetcode 752: Open the lock. He told me that he ended up to read the discussion, I will try to solve it by myself.

Algorithm study

Will come back later.

Encryption and decryption

January 23, 2018

Introduction

It is another 10:00 PM mock interview. I had a very good peer to ask me about time complexity related to 26 * x calculation, I ended up to correct my time complexity analysis, and tried to optimize the time.

Code review

Here is the C# code I wrote in mock interview.

My argument of time complexity with the peer, a top ranking 60 university with computer science major master degree student, who is graduating this May. What is time complexity 26 * x?

To decrypt the each char in the string with length n, then the total sum of number of chars 1 + 2 + .. + n = n², how many number of char in sum will be O(N²).

If each while loop only 26 is taking off, and then it will take O(N²) while loop and make the time complexity to O(n²).

So this mock interview, I wrote extra 3 lines of code from line 26 to line 28.

if(smaller)
{
   diff += (97 - diff)/ 26 * 26;
}

With this calculation, I reduce the while loop times to O(n) time.

Correction on unknow number x analysis

Here is the analysis with the fix of unknown number x.

Have you seen the problem before?

January 22, 2018

Introduction 

It is most common question peer asks me in  mock interview. Have you seen the problem before? Sometimes I just answer quickly, similar problem. I like to practice one more time and see if there is an issue to work on and also get help from the peer. Today I found one in mock interview as well.

Analysis does not match code

Here is Deletion distance dynamic programming analysis and C# code. I asked the peer that the analysis does not match the code. And he confirmed with me after carefully review of my code and the analysis.

Nothing can beat the peer's insights. 

A humor a day

January 21, 2018

Introduction

Today I like to write a humor a day blog. I met an algorithm engineer in mock interview 10:00 PM. So we discussed what is your favorite algorithm. I wrote down something quickly, so the peer confused.

Kruskal algorithm - 2018 my favorite - minimum spanning tree.

After one minute or so, the peer told me that based on the wiki article Kruskal invented the algorithm in 1950s, not 2018.

I just explained to the peer that my favorite algorithm is Kruskal algorithm in the year of 2018.

Quick writing

Here is the writing I shared with the peer. I did say that I worked on mathematics study from18 years old to 22 years old, and then another 12 months when I was 30 years old.

NP complete problem

January 21, 2018

Introduction

It is exciting to learn some new algorithm through mock interview. I like to ask the question what is your favorite algorithm.

It is the first time in a week I heard two time NP complete problem.

Algorithm 

Here is the algorithm I can do some study.

Follow up 

Dynamic programming - Set 25 (subset sum problem)

https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/


Subset sum dynamic programming - similar to deletion distance dynamic programming, regular expression matching problem.


https://gist.github.com/jianminchen/ea004cdf37689d4c2c090dcec638f1c3


Subset sum problem

https://gist.github.com/jianminchen/57704617cd684d8dd61bd5ae93d0b621

Sort algorithm

January 21, 2018

Introduction

It is the sorting algorithm with time complexity O(n²). I had a mock interview today at 8 PM, so I wrote one more time.

Code review

Here is the analysis and code. I tried to write a better analysis this time.

Advice to an undergraduate student

January 21, 2018

Introduction

It is not easy to give advice to a undergraduate student. I wrote down every practice I did, so I can easily relate to some statistics for each algorithm.

Spiral Array Copy

The peer worked on the algorithm. And also I tried to help but we could not finish it in 30 minutes. Here is the code.

After the mock interview, I just shared the fact. I have worked on the algorithm more than 50 hours.

Here is the sharing.

Interviewing.io

January 21, 2018

Introduction

It is the second time in less than a months two peers shared with me interviewing.io website. I like to study the website and try to get some experience at least one time.

Word of mouth is most efficient marketing tool this day. I was so busy and I should spend time to get some experience in 2018. It is part of new year resolution in 2018.

48 minutes learning Go language

January 21, 2018

Introduction

It is another mock interview at 6:00 PM. I had chance to learn Go language when the peer worked on problem solving. I did not have chance to copy the code he tried to solve the problem. But the learning experience of Go just started Jan. 21, 2018, 6:00 PM. I finally found myself to enjoy 48 minutes to study Go and had a good discussion with the peer about the algorithm problem solving.

Go

Plan to write down some good website to study Go language here. Next time I should add Go as my interview language so I can learn more, meet more peers using Go language.

Number of Isalnds II

January 21, 2018

Introduction

It is the second time I heard the algorithm through mock interview conversation. Last December I could not find time to work on the algorithm. I just wrote one blog to leave for future. Today I like to study the blog written by Grandyang, and then write a C# code later on.

Algorithm analysis

Most of important is to write down study notes from the above algorithm blog. Try to understand the problem using the analysis.

Here is the note I wrote down to study the blog written in Chinese.

Here is the gist I created to study Leetcode discussion on the algorithm.

Here is the C# code I wrote based on the above Leetcode discussion in Java language.

Word count algorithm practice

January 21, 2018

Introduction

It is another mock interview at 4:00 pm. I had to work on the algorithm called word count in a sentence. The task is to lower the char in sentence, replace ' using empty space, split into words using delimiter string ".!,", and then store words to Dictionary<string, int>, and then apply bucket sort, and then output to array.

30 minutes is the time limit for me to write. I could not finish it.

Please complete the code

Here is the code I wrote in 30 minutes in mock interview. I like to spend time to write today and complete it to pass all test cases on mock interview platform.

Follow up 

January 23, 2018

Here is C# code to pass all test case. I spent over 30 minutes to read Regular.Split and String.Split and figure out how to specify delimiters, how to specify multiple using +, using [ and ] to enclose all delimiters, and understand ( and ) meaning.

C# code is here.

Common range in two intervals algorithm

January 21, 2018

Introduction

It is another 4:00 PM mock interview. I had chance to review interval algorithm. I still remembered that I had so many experience to work on the interval algorithm. It is not difficult one but I failed in January 2017.

What are the common mistakes in the problem solving?

Code review

Here is the code I like to review. I learned to ask questions and then had some discussion through mock interview. After that, I also took the time to review the code and discussion some coding style, using var explicit typing, and write readable code.

I recommend the book called "The art of readable code"

Maximum number of chunks algorithm

January 21, 2018

Introduction

It is the new way to learn the algorithm called maximum number of chunks. Last 2 weeks I asked the algorithm after mock interview over five times, through the discussion with so many peers, I also learned a few things. The peers are super talent on algorithm problem solving, one is senior developer of top four companies, one is computer science Ph.D., and others are preparing Google/ Facebook onsite.

Brute force analysis

One thing I learn is about the brute force solution. What is the time complexity for a brute force solution. I met a software engineer who is also Chinese. He argued with me and then I understood after the mock interview he is correct on the time complexity. For the array of size N, every index can be open chunk/close chunk position or not. So each index has 3 options, open chunk or close chunk or not the first two. So the option should be 2ⁿ time complexity.

binary search algorithm in python

January 21, 2018

Introduction

It is so popular language called python. Today I had 10:00 AM and 12:00 PM mock interviews, both of peers chose to write in python. The later one told me that he used python last 2 years only for algorithm practice.

I also start to learn python through mock interviews. I try to ask some good question, and also get some ideas how other people learn python quick and efficiently.

Code review

One thing is helpful for me to review the peer's python code. Here is the code I reviewed and made some changes.