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.

Popular question badge on stackexchange.com

January 21, 2018

Introduction

It is a badge called popular question. 1000 views is the popular question. It takes 9 months to get over 1000 views of the algorithm I asked on stackexchange.com. The algorithm is called LINQ and string.split do it yourself practice.

How to celebrate a badge?

I like to celebrate for this popular question badge. Maybe I should ask another question on stackexchnage.com today. Let me figure out which one I should ask.

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.

H tree algorithm

January 21, 2018

Introduction

It is most classical algorithm of recursive function called H-Tree algorithm. I had a mock interview at 12:00 pm, so I had chance to learn python and also learn from the peer how to do the analysis and write code.

Code review 

Here is the python code with the analysis. The peer wrote very good analysis and showed me how depth first search is structured. Later on, I made the comment and asked what is your base case. And then he add the base case for depth = 0, and then I asked him to remove line 20: if depth >= 0 and let it fall through the base case to take care of it.

The peer had math Olympiad contest experience, I like his analysis in terms of time complexity from line 26 to line 31.

Catalan number

January 21, 2018

Introduction

It was another 10:00 PM mock interview again. I had to write the algorithm called catalan number. After I finished coding, the peer asked me if I can make an array copy instead of writing a for loop. So I looked up Array.Copy and then used it first time in mock interview.

Code review

Here is the C# code.

Code path org

January 20, 2018

Introduction

It is very easy to get education from so many resources these days. One of the ways is to go through the boot camp. I was told another boot camp today. Codepath is the name of boot camp. 

Leetcode 11: Container with most water

January 21, 2018

Introduction

It is the time for me to learn the algorithm again. I met a peer through the mock interview, and then we had discussion about favorite algorithms. One of algorithms is Leetcode 11: Container with most water.

I found my practice back in 2015. Here is the link.

Next I go over the discussion panel and try to find a very good answer with explanation. Here is one of links I like to read carefully.

H tree

January 20, 2018

Introduction

It is the classical recursive algorithm. I had 4:00 pm mock interview and then I had to write H-tree algorithm. It took me exactly 30 minutes to finish the analysis and also coding. I made a mistake in the writing first, draw one H tree first, and then call recursive tree four times for each corners of H-tree.

Code review

Here is the code.

Compared to last practice

Here is my practice in Dec. 2017. The code is almost exactly same. Only difference is that this time I work on the analysis of the algorithm, write down given constraints, and problem to solve. Write down the solution first before I write the code.

I need to work on the structure of recursive function, base case, inductive step. Please write down those steps in analysis first.

  if depth == 0
  return

  // draw one H-tree
  draw horizontal line
  draw vertical left line
  draw vertical right line

 // inductive step
 4  recursive function call for each corner of H-tree
 left top
 right top
 right bottom
 left bottom

Because my first writing in mock interview today has wrong logic like the following:

 if depth == 0
  return

  if(depth == 1)
 {
  // draw one H-tree
  draw horizontal line
  draw vertical left line
  draw vertical right line

  return; 
 }

 // inductive step
 4  recursive function call for each corner of H-tree
 left top
 right top
 right bottom
 left bottom

I found the bug in whiteboard testing and then I fixed it. But I should understand base case 100% before I write the code.

Need two hours break

January 20, 2018

Introduction

It is now 2:00 pm. I plan to take  a two-hours break to work on grocery shopping and also go to swimming pool to do some physical exercise. My car needs my attention, the maintenance light was on. I had 10:00 AM mock interview, it took me one hour 50 minutes since I asked extra three algorithms to test the peer. And then I wrote down blogs to document my practice. Last night 10:00 PM I also had a mock interview with extra algorithms, it took extra 50 minutes or so.

I need to take a break. My next mock interview is 4 PM. I set up 6 PM, 8 PM, 10 PM.

Algorithm learning

I only can do multiple interview in the weekends. So I am pretty busy and try to meet more programmers and also practice and review some algorithms. Good things are my rating are so high again, I meet top talented programmers in the world again.

Here is status report of my mock interview progress.

Leetcode 684: redundant connection

January 20, 2018

Introduction

One of ways to learn the algorithm is to ask the peer to solve the algorithm after mock interview. I met a peer this morning 10:00 am mock interview. He is graduating from K.I.T. a university in German. He likes to apply Switzerland Google instead of German one.

Algorithm problem solving

The peer came out the idea of the algorithm Kruskal's algorithm. And he also talked about minimum spanning tree. How does the edge joins the union by determining if the node is belonging to the union or not. If both of nodes of edge is in the same union, then the extra edge is found.

I asked him what is last time he worked on the Kruskal's algorithm recently. He said that he did not work on. But he worked on video project, cycle detection, filter, or canvas, video, use interface, when the video start time clip something related to the algorithm.

Aha, how do you compete with some one with super talent, and also hands on with projects outside the university, job?

And also the peer is super calm when he worked on the algorithm. He said that let me think about 1 to 2 minutes. And then at last, I asked him if I gave him the hint, he said no.

Maximum number of chunks

January 20, 2018

Introduction

It is so surprising to know the difference. I compared two people, one with over five years experience, with top four companies; another one is graduating and looking for job, with open source project experience. But the later on is studying in K.I.T. in German. How does those two to work on this maximum number of chunks algorithm.

Problem solving

The one with practice of one-third of elements of programming interviews handled the algorithm very quick and easily. He is really a good thinker, he did not need to write down anything, basically he just communicated with me his ideas using pure words. And then I had a short discussion with him, I asked him we do not need to sort the numbers.

I wrote down his thoughts on my paper:
In order to close the chunk, every number of smaller of max should be visited. Keep track max/ min elements.

And we discussed that sorting is not necessary, so he quickly came out the idea to preprocess the array with max/ min value for each index, one is called prefix, left to right iteration.

Binary search tree inorder successor

January 20, 2018

Introduction

It is 10:00 AM mock interview. After the interview, I gave the peer to solve three algorithm. This algorithm I like to test how good the peer is confident on recursive solution. But the peer explained it to me that the iterative solution he writes, why he likes to write iterative one instead of recursive one. He solved it in less than 10 minutes, because both of us like to move on the next mock interview, and also we moved to appear.in to get audio and video, use codeshare.io to get coding editor.

Algorithm code review

Here is the pseudo code the peer wrote in less than 10 minutes. I explained to him that his original code has a bug. If the given node is the node with value 14, the successor should be 20 instead of 12.

Advice from the peer

January 20, 2018

Introduction

I met a top talent programmer who is Tsinghua graduate student in December 2017. But today I met another who is Germany graduate student. He gave me the advice to work on "Elements of programming interviews: The insiders' guide", try to work on one of ninja algorithms. And also he told me that he learned programming from open source project, he read a lot of code. He also practiced Leetcode, but he said that since test cases are unknown, it is not very good place to practice.

Advice of open source projects

Here is the advice to get C# open source project, I asked him to give me some advice.

// https://slimdx.org/

// https://github.com/WCell/WCell

The peer worked on those open source projects:

- firefox 

- search engine in C++

- physics engine for a game

Preprocess matrix to calculate the sum of submatrix

January 20, 2018

Introduction

It is the most popular algorithm to test how to apply a cache to expedite the search algorithm. The peer is very experienced programmer last five years and also senior developer in one of top four software companies.

Transcript

Here is the transcript.

Connected components in a matrix - BFS

January 20, 2018

Introduction

It is 10:00 am mock interview, and I have chance to interview a super talented graduate student. He wrote the breath first search, since I ask him to write. He told me either BFS or DFS. I like to review BFS, so I asked him to write a BFS one.

Code review

I also told the peer that I like to learn C++ from him, so I write down each word he wrote, so I can stay current and then ask question. First question I asked in C++ why he declared a structure from line 7 to line 9 vec2i, why not int[]. And then he explained it to me. Later he also gave me a code snippet to explain the empty array shows the size 8 instead of zero in C++.

C++ code is here using BFS, queue.

And then I appraised that the BFS code is very readable and also very easy to follow. The peer changed the code to write DFS using stack as well, just a few lines of code change. And he explained to me using recursive function, it may stack overflow.

C++ code is here using DFS, stack.

Maximum number of chunks

January 20, 2018

Introduction

It is the best way to learn the algorithm in mock interview together. I asked the peer to solve the extra algorithm, and he worked so hard to solve the algorithm in 20 minutes or so. I watched him and learned how he thought out loud.

Transcript

Here is the transcript. I will review the transcript later on. The peer likes to write down the programming and then think about in the same time. I do not like this kind of style. Actually it is better to work on the idea, and until you have an idea to solve, you write down the algorithm and ask the peer which idea to write.

Sudoku solver

January 20, 2018

Introduction

It is another 10:00 PM mocking interview. At the very beginning, I always say that my name is Julia. I am in the city of Vancouver. I have been working on C# last eight years, web programmer. And then the peer told me that he is xxx and then he has been working for yyy last 5 years.

I was so surprised to learn that the mock interview has such great machine learning algorithm. I just got another senior developer with one of top four software companies and then we will spend one hour together to discuss the algorithm.

Code review

The algorithm I had to work on is called Sudoku solver. What I have to do is to write down the problem, constraints, and also explain the depth first search and idea to apply backtracking algorithm.

The peer did ask me how to optimize the function getAvailableChars, there are 27 searches.

Here is the C# code with analysis as well. I start to pay attention to the analysis in mock interview, make sure that I can write very clearly about problem, given constraints, and the problem to solve, the idea to solve the algorithm problem.

I went over the constraint in the matrix first, and the write down Constraint, and then write down the main idea of the algorithm: DFS + backtracking, and go over the first row three elements in depth first search, and then the peer told me that he understood the algorithm and I can write the code.

I continue to write down the time complexity and space complexity. The time complexity is 9⁸¹ at most, but I wrote it wrong 81⁹. The peer asked me and then I corrected it.

The only thing I found in whiteboard testing is line 32, I forgot to add !, it should be if(!isDot).

Interval algorithm

January 20, 2018

Introduction

It was a 10:00 AM mock interview. I met a peer who is super talented programmer and also very good mentor to write clean code and also readable code. He helped me to think about design along the 30 minutes mock interview.

Code review

Here is transcript for C# code and with analysis. I did spend first 10 minutes to write nicely an analysis for the algorithm.

Small accident

The code I wrote cannot pass the test case to find the interval, and then I could not find the logic problem. The peer told me on line 7 and line 8, I should check GetLength(0) < 1 instead. He said that he did not know C# very well, but he thinks that the checking is not necessary.

Advice from the peer

The peer learned how to programming through open source C++ projects, he read a lot of code. I was surprised to learn that he wrote beautiful code using queue and stack.

He advised me on line 22, design the return of function getIntervalOverlap, do not need to use third number in return array. Since if the interval is not found, then by checking startValue and endValue the interval can be defined. 

He also advised me in the function getIntervalOverlap, do not need to return empty array using new int[]{maxStart, maxStart}, let the code fall through the checking on line 28 to line 39. 

One additional note

Since the peer worked on the algorithm first, I worked on my algorithm next. So I did ask a lot of good questions through his algorithm. The peer was motivated and shared his opinion to write readable code and clean code. 

I asked three additional algorithms after the mock interview, the peer solved all of them. I gave the comment like that in the sentence: "If I am a google interviewer, I will hire you on the spot.". 

The peer is in Germany, graduating very soon from K.I.T. He learned programming from open source project, most of them are Mozilla open source C++ project. He read a lot of code. 

My last practice

My last practice is on January 8, 2019. The blog is here. 

HDU-1213 How many tables

January 19, 2018

Introduction

Union-find algorithm is my 2018 most popular algorithm. I like to learn it slowly. One way is to go over the blog and then follow each example in the blog related to union-find algorithm.

Kosaraju algorithm

January 19, 2018

Introduction

The algorithm Kosaraju has a popular name called strongly connected graph. I plan to study the algorithm.

Recently I found a very good blog to review written in Chinese about union-find, the author also wrote another blog about Kosaraju algorithm. Here is the link.

Data structures and Algorithms in JavaScript

January 18, 2018

Introduction

It is time for me to take courses from frontendmasters.com. I just started monthly subscription  starting from this Monday. The first course I like to take is Data structures and Algorithms in JavaScript. The courses on the website is here to look up.

Recursive function

I really like the lecture of recursive function. I try to learn from the teacher so I can apply the techniques in my daily mock interview practice.

ESRI - Quick study

January 18, 2018

Introduction

It is so exciting to learn ArcGIS, I have good time to learn how the software helps to change the world, and make the location information so valuable to our daily life, business and make our lives much better.

I plan to spend 30 - 60 minutes to read blogs written by China ESRI. The link is here. And also I plan to read the articles related to the products.

Kruskal's algorithm Wiki article

January 18, 2018

Introduction

It is the very good investment of time to read the article of Kruskal's algorithm on the wiki page. What I do is to go over each word and each sentence slowly, write down some new terms I like to learn. Today I spent over 30 minutes to read the article.

Kruskal's algorithm 

Plan to spend 20 minutes to read the article first.

Terms:

minimum-spanning-tree algorithm
greedy algorithm in graph theory

minimum spanning tree

a subset of edges that forms the tree that includes every vertex, where the total weight of all the edges in the tree is minimized.


How to read the algorithm Kruskal's algortihm


How to read the graph simulation of steps: b and e are added, but there is a cycle.

Average performance:  O(|E|log|V|)

Worset-case space complexity:


Prim's algorithm, Reverse-delete algorithm, Boruvka's algorithm

comparison sort

disjoint-set data structure
union by rank

(counting sort or radix sort)  Ackerman function

induction -

minimality

Leetcode 84: Largest rectangle in histogram

January 18, 2018

Introduction

Coding is always best time for me to learn the algorithm right now. What I do is to get Java code from the blog I like most and then rewrite in C# code, and then work on the code to match the design. After coding, I like to remind myself do whiteboard testing, do not use debugger, go through the test case in Leetcode 84, and go over each line of the code, run the code. I fix all the issues in the coding styles, including variable names, function name, function arguments, how to put comment to align with the code, make the code more readable.

Now it is show time to present my practice C# code.

Code review

C# code is here.

Leetcode 84: Largest rectangle in histogram

January 18, 2018

Introduction

It is the hard level algorithm and it can be solved used stack to achieve the optimal time complexity O(N) where N is the array's length. The algorithm is called largest rectangle in histogram.

On January 17, 2018, I had a mock interview and I was asked to work on the algorithm. I went through the brute force solution first, but I did not come out the optimal solution to lower the time complexity to O(N).

One more practice 

What I like to do is to study one blog I like in June 2015, and then rewrite the notes and also write the C# code as well. It is very easy to look up past practice, here is my blog to document the practice in June 2015. At that time, I was shy and did not write down my thinking process to learn to solve the problem.

Right now, I think that it is very important to write down thinking process and also the idea to break through the hurdles in the problem solving. I think that it is more important to build up some new habit to learn to solve a problem. Write down the constraints, write down the problem, difficult issues, concerns, and then ideas to solve the problem, or ideas to solve partial solution. 

First, I rewrote the note to make it more readable, and then saved a gist. Here is the gist. 

Analysis of the algorithm

Most of important is to write down the analysis, and that is something lasting longer than coding itself. Specially if I draw something to highlight the main design ideas and it will be extremely helpful to bring back the memory.

This time I drew one to help myself learn the design using stack, check upward and downward.

The main idea is very simple to explain in Chinese, let us take a look at notes in Chinese first, and then I quickly explain them in English.

Going upward

When the graph is going upward, in detail, current index is i, next step is i + 1, and height[i] < height[i + 1], there is no need to calculate the area. Since it is getting bigger value when i moves to next value.

Going downward

When the graph is going downward, in detail, current index is i, next step is i + 1, and height[i] > height[i + 1]. it is time to calculate the current rectangle's area.

Get help from a stack 

At the current index i, only right end's index is known, how to get the left end's index? So in order to iterate the array, a stack is need to maintain the backtracking history.

How to design a stack?

In this stack the right end's index is saved to the stack, but when is time to push into stack? Every time there is element in the array which is bigger than the top of the stack, push the index to the stack. Otherwise it is time to calculate the current rectangle's area and compare to the largest area.

Every algorithm will become one of your valuable weapons 

until you teach some one and show him/ her how it work.

Leetcode 684: redudant connection

January 17, 2018

Introduction

It is the second time to meet the peer again in less than one week. Julia chose to give a medium level algorithm for peer to solve, Leetcode 684: redudant connection.

Discussion

Here is the transcript for the discussion.

Highlights of good things in discussion

Peer did:

1. First the peer came out to check if the graph has a cycle

2. Second the peer drew a more complicated tree, and then try to add one edge to make it a cycle

3. Third the peer write down a list of graph algorithm he worked before.



I try not to give out hint explicitly. So what I talk is about the example a tree drawed by the peer how node 1 is connected to node 7.

What is the connected meaning for us? The nodes are connected.

Also, I added one more graph algorithm called Kruskal algorithm, and then share the wiki page for the algorithm. I talked about the algorithm for minimum spanning tree using disjoint set data structure. And then I asked if the peer knew the data structure before.

I explained the data structure, what is for, why we need this data structure. Since the path from one node to other node is not needed, all we care about is if two nodes are connected. We do not need to search a path from one node to other node.

At last, I tried to give the explanation how to solve it in less than five minutes.


Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3         
 

Julia's explantion:


At the beginning, each node has its own set.
{1}, {2}, {3}, {4}, {5}.

[1,2] first edge is to connect 1 to 2, so {2} likes to join {1].


{1} <- {2}, {3}, {4}, {5}.

we have {1, 2}, {3}, {4}, {5}.

[2,3] second edge is to connect 2 to 3, 2 is not the set, but 3 is not in the set.


{1, 2} <- {3}, {4}, {5}
we have {1, 2, 3}, {4}, {5}

[3,4] third edge is to connect 3 to 4, 3 is in the set, but 4 is not in the set.

{1, 2, 3} <-{4}, {5}
we have {1, 2, 3, 4}, {5}

[1, 4] fourth edge is to connect 1 to 4, 1 is in the set, and 4 is also in the set. Then we know that node 1 and node 4 are connected, but direct connected edge 1 to 4 is to be added. Then edge [1, 4] is to form a cycle.

Leetcode 84: Largest rectangle in histogram analysis

January 17, 2018

Introduction

It is 10:00 pm mock interview. The peer gave me the algorithm Leetcode 84: largest rectangle in histogram analysis to solve.

Algorithm analysis

The peer gave me his analysis using stack, and how to store the stack with (value, index). The discussion link is here.

Mock interview

Leetcode 84 is the hard level algorithm. I did not come out the optimal solution using time complexity O(N), and then the peer reminded me to go over upward test case like [1, 2,3, 4, 5] and then go over downward test case like [5, 4, 3, 2, 1]. And then the peer gave me the hint and then I came out using stack to push previous nodes into the stack, but I did not have idea how to manage the stack, when to push into the stack and when to pop the stack.

The peer went over quickly using the example to explain the idea.

I know that it takes me 10 mock interview practice to learn a hard level algorithm Leetcode 10: regular expression matching.

Actionable Item

Review what I did in the past on this algorithm. I did practice the algorithm in June 2015, here is the blog.

Leetcode: The skyline problem

January 17, 2018

Introduction

It is hard level algorithm, some of us categorize the algorithm as binary index tree. I start to work on the hard level algorithm, 30 minutes a time, called the leetcode 218 The skyline problem. So I spent 30 minutes to read the article from Leetcode discussion most voted discussion.

Plan to work on some coding. First, I like to read code written in various languages first.

Good time to read the article with good simulation of problem solving with skyline in the background image. Time is well-spent 20 minutes or so.

Catalan number

January 17, 2018

Introduction

It is the algorithm peer gave it to me for a test since he had the algorithm the day before. I had to work on the algorithm called Catalan number on January 15, 2018, 10:00 mock interview. I explained the algorithm to the peer, and also showed last 3 practices.

Will write down the discussion of the algorithm here later.

Can plant flower

January 17, 208

Introduction

It was the algorithm I gave to the peer in 10:00 PM mock interview on January 15, 2018. The peer wrote code with a few of bugs, and then the topic is how a senior developer face the challenge to write a production ready code in mock interview.

I showed my blog about 48 minutes performance issue in Leetcode weekly contest. And it is one of easy questions in Leetcode.

Code review: Binary search

January 16, 2018

Introduction

It is my time to learn some new ideas to write binary search. I learned the new way to find smallest index today. But I like to look into the idea and see if there is any pitfall on that.

Code review

I like to study the code and give some code review. The code is here.

A few things I gave in the discussion:

1. Ask the question about arr[i] - i, how to prove that it is not descending. It cannot take for granted.
2. Advice to write down some analysis before writing the code; write down the constraint, what to find. The peer missed the keyword: lowest index.
3. Binary search while loop, should include = sign.
4. Coding style

Find the smallest missing number

January 16, 2018

Introduction

It is another 10:00 PM mock interview. I started to work on my analysis of algorithm, I tried to put together the algorithm requirement, constraints, and my solution, time complexity, space complexity, and also go over the small case to explain the algorithm. This time the analysis of the algorithm is not up to standard I like.

Analysis of the algorithm review

Instead of doing code review, I like to review my analysis of the algorithm. I like to make it better. Clarify the question, understand the constraints, and also the problem to work on.


I also like to find a few issues in the above writing:
I should write a summary to describe the idea to solve the problem, using the extra array to store 1 if index value is found in the original array.

Here is the code with the analysis.

case study: Depth first search base case

January 15, 2018

Introduction

It is another complaint from the mock interview on January 14, 2018. The peer complained that depth first search missing a base case. What I did is that I put a base case to check the matrix element is not one in four if statement, so the if statements are giant expression, but the base case is hidden.

Plan to look up the book of mathematics for computer science and look into how to solve this issue from better understanding of depth first search.

Code study

The C# code is here.

10 things to remember

January 14, 2018

Introduction

It is a busy weekend with nine mock interviews. I met very good programmers in the world, and I cannot believe that I meet so many talented programmers in such a short time period, 48 hours.

I miss the swimming pool, crystal mall shopping, walk in metro town mall, or catch some Netflix movies, I miss those weekends I spend time do other things. I was staying in the home almost all the time, I did this very often when I play hackerrank contests and try to solve medium level up algorithms from June 2016 to Sept 2017.

As a software programmer, full time eight years, this is the first time I learn that it is my job to do something, learn to get connected to other programmers. Reach out to other programmers, in person, talk face to face, and get help and encourage each other to solve data structure and algorithm problems.

There are so many software engineers in the world. I cannot meet a lot of them, nine mock interviews a weekend, that is a lot. It is like intensive training, how to be an interviewer, and I also have to write 9 algorithms a  weekend, that is a lot of writing.

10 things to remember

Here is the easy thing for me to do to end this weekend with something easy and relax. Remember the article on quora, the link is here.

It is true that those 10 things can apply everywhere, not just in mock interview, interview. It can apply to normal daily work. No one has the responsibility to train you.

You have to get those training by yourself. I am glad that I have over 100 mock interview experience, now it is around 150 mock interview experience.


1. The single biggest good engineers fail the technical interviews is because they lack the ability to showcase how they came to their solution.

One step a time. Provide facts, good arguments, and also show some reasoning.

2. Your logic wasn't actually logical.

Try to related to very simple well defined problem if possible.

3. You didn't gather requirements or ask clarification questions.

Gather requirement and clarify the question, please!

4. You think you solved the problem but you actually didn't even answer the question.

Answer the question. 

5. You forgot to consider important things like monitoring or you code isn't production ready.

Code should be production ready.

6. You took too long or too many hints.

Accomplish something. Try to solve problem at work also using limited time, 30 minutes a time. 10 minutes analysis, 20 minutes coding.

7. Lastly, your work style just doesn't fit the culture.

People skills. Always stay positive, give people good encouragement first; and then ask permission to give some feedback. 

8. The technical breadth and depth of which you went into, simply didn't meet the expectation of the level you might be interviewing for.

9. You didn't optimize for simplicity.

10. You couldn't deal with constraints and variables.

Production ready code?

January 14, 2018

Introduction

Production ready code is a new concept for me, at least less than 6 months old. The concept is that we should be able to write code in mock interview which can be ready to be shipped. There are a lot of things to be considered, let me brainstorm here.

all edge cases
the code style
the correctness of the code
the maintainability,
self-document code

How to write production ready code? 

One of ideas is to work on one type of algorithm again and again. Keep writing, keep practicing. Journal the practice until we can not get it wrong.

In tennis sports training, there is a saying that "Do not stop until you get correct". It should be "Do not stop until you cannot get it wrong".

Here is another binary search practice I did this evening 8:00 PM mock interview.

Are you ready?

January 14, 2018

Introduction

It is the first time in mock interview I came cross a peer who worked hard first five to ten minutes to write down his analysis and also in very structured ways. It is the algorithm called "Find largest smaller binary search tree key than given node". I have written more than five time and also I have interviewed others more than five times. Over my one hundred interview, this is the first time I read such a great analysis of the algorithm.

Analysis of the algorithm

Here is the algorithm analysis. I never know that the analysis of the algorithm is also very important part of presentation until today 4:00 PM mock interview.

Here is the link.



There is only minor thing to modify in the base case. The node may not be the leaf node all the time.

Code review

Here is the C# code after the code review. I asked the peer to add null pointer checking at the beginning and make it one of base cases. So this way the code is much simple to read and if statement do not need to check is null pointer at all. The success of coding is that base case is well-defined on line 24.

Are you ready?

This is not the first time I met a person who is working on Google onsite in less than one week. The mock interview platform provides me great training and also I just write down those peer's code and study more, I should figure out ideas for me to improve. We do not need to spend money for tutoring, just learn by ourselves.

One easy thing to learn is to write down some note related the analysis of the algorithm. Organize them so it is well-written. Write down the constraints, write down the ideas, write down the pseudo code, write down base case for depth first search if applicable.

Share some advice from the peer

I like to share some advice from the peer. Focus on soft skills.

Find smallest substring containing unique characters practice

January 14, 2018

Introduction

It is the Saturday morning and I had 10:00 AM mock interview. I had a very good peer to help me to practice one more time the algorithm called "Find smallest substring containing unique characters practice". The peer also uses C# to write code, but after the peer wrote the algorithm called "Find Binary search tree successor", I compared his performance to my first performance in 2016 and a first practice in 2017, I knew that he has strong engineering skills. So I managed to get his very good code review for my practice this time.

Algorithm analysis

Here is my analysis of the algorithm. I like to present here. Since I wrote the code based on the idea presented in the analysis, the peer advised me to change the design, do not define the substring variable (line 31) and get the substring all the time; and the concern of heap usage to store C# reference variables. Only last line of code to return substring using slide window left pointer value and substring length (line 40).

I spent extra a few minutes to explain the time complexity of the algorithm, since we are doing iteration of the string once, and then each sliding window we are not recounting all the chars to see if the substring is found or not, a variable is maintained to keep check. So the time complexity is optimal. It should be around O(n), since left pointer of slide window at most visit each char in the search string once, same as right pointer of slide window.

Code review  

Here is my code to pass all test cases, I spent around 40 minutes to explain the algorithm and write the code for the idea. Since the peer had not worked on the problem before, I spent extra time to go over the idea and explain my analysis and design of the algorithm.

I spent extra 5 minutes to find the bug and then make sure that dictionary variable is filled with all keys.

My code with a bug I did not catch through my whiteboard testing, run tests button catches it:
    var dictionary = new Dictionary<char, int>();
    keys.ToDictionary(key => key, val => 1);

Should be:
Line 14:  var dictionary = keys.ToDictionary(key => key, val => 1);

Since the peer has more experience on LINQ than I do, he is very helpful to give some explanation how to construct the key and value using LINQ. Need to look up Lamda expression keyword later on.

The above code a few places are reviewed by the peer for improvements.

line 50 - the peer advised me first to move the code to if block to avoid extra work, string usually takes some heap space. Later the peer advised me to remove the variable.

line 52 - the bool variable is not necessary

line 60 - add ++ after var leftChar = search[left++]; so line 71 can be removed.
line 64 and line 65 merges to one line.

Here is the code after the peer gave me the code review. I will document each review the peer gave to me, and some explanation.

No need to store substring

I like to present a diagram about the code review I got.

Code with modification

Here is the code after the modification by the peer for the above section.