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.

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.