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.

Best peer for the Saturday January 13, 2018

January 14, 2018

Introduction

I had 6 mock interview in the day of January 13, 2018. Right now I have two candidates, I could not decide which one is the best peer. How can I make a sound judgement call?

Let the story begin.

The first candidate did not give me response. 12:00 PM one. The second candidate gave me review, here is part of the review.

I used to get a lot of complaints about the communication. This one also has a smell about it.

Here is another candidate, I learn how to developer web front end and what to learn:

 

Root of a number

January 14, 2018

Introduction

It is such a great machine learning algorithm on mock interview platform. I spent 50 minutes with a top ranking university with highest GPA, a master student to work on a problem solving. Quickly in less than 20 minutes the solution was written and also pass almost all test cases. I was amazed by the peer the engineering power, the way he tested the code, and the quick he applied to small increment value from 0.001 to 0.0009 to 0.0001, and also the answer he gave to me why it is good idea to always increment or decrement one value.

I have worked on the algorithm through mock interview near 10 times, I never came cross this idea to apply increment/ decrement the middle value one but just simply apply the value from 0.001 to 0.0001.

Code review

Here is the code written by the peer using C++. I like to code review later on.

Leetcode 10: regular expression matching

January 14, 2018

Introduction

It is so surprising that I met such a great master student from California and he also encouraged me to write a dynamic programming solution for Leetcode 10: regular expression matching. The peer is also very good to help me to understand b* pattern how to apply zero time, one time or more than one time. The peer looked at my analysis of logic and asked me to optimize to skip last char * if applying once. It is the first time I understood the idea after I struggled so long, the peer told me in person.

Learning is so much fun, specially when the peer is top ranking master graduate student with a lot of good intern experience, and also good research ability. I can tell the big difference from other graduate students with less practice on Leetcode algorithm.

Code review

My C# code was written in less than 30 minutes. The code has a bug to pass the test case "" with pattern string "b*". I need to work on base case when the text string is empty, it still can match pattern "b*" or "b*a*" etc.

Please study this version of dynamic programming code and then fix the bug in my C# code. Please work hard as the young graduate Chinese student does, here is the blog.

Follow up

The code is fixed and now it works for all test case. C# code is here.

React route course

January 13, 2018

Introduction

It is so busy that I do not have time to do research by myself what front end technology I should adopt and then apply to my work. Since I have very good performance on mock interview, today after the mock interview, the peer shared with me his experience to learn front end technology.

React route course

Plan to spend some time to look into those courses. Here is the link.

Frontend Masters - Learn JavaScript for WordPress using the WordPress REST API

January 13, 2018

Introduction

I met a JavaScript front end developer on mock interview platform, through extra algorithm discussion after mock interview, the peer was so happy that he shared with me some advice what to learn in terms of front end development of website.

One of his advice is to learn courses from frontend masters. I have chance to look into this course: Learn JavaScript for WordPress using the WordPress REST API.

JavaScript is my next goal

January 13, 2018

Introduction

It is so exciting to plan what to work on in 2018. Finally I should have time to learn some technologies besides mock interview, algorithm and data structure practice. Since I practice mock interview, I learn that the issue I have is to relax and perform on mock interview, but in theory those algorithm and data structure problem I should have solved them, or I believe that I can learn and solve it quickly.

JavaScript and technology

Today the peer shared with me what to learn in terms of react framework, and recommend me to learn from those websites.

https://tylermcginnis.com/

https://frontendmasters.com/

Backend/ 

Ruby on Rails

Django

Node.js (express.js koa.js)

Go

Scala

Frontend/

React / redux ++++

Angular 2 / 4

webpack

Gulp

One humor a day

January 13, 2018

Have you read a story about one humor a day, live life to 99 years old. Today I will share you with a funny story about numbers.

Through mock interviews, I keep meeting new people. But also I make mistakes on living cost and salaries.

Today story is about the mistake I asked to the peer about $12,000 US dollars. Let us call it $12,000.

$12,000 story

I hear a lot of stories about startup in California, United States. Back in 2014 I went to California Milpitas and visited my elder sister, I also spent over 5 days vacation in California.

Today I was told that the peer makes around $12,000. I thought that he is getting $12,000 annually, and he complained to me that the rent is expensive, almost $1200/ month. And I think that how smart the startup can pay a good employee like that these days, $1000/ month for an intern price.

Actually it is $12,000 x 12 annual salary. 

Algorithm and friendship through mock interview

January 13, 2018

Introduction

Life is so busy and we have so many problems to work on. I have to work on my sponsor application project, I like to talk to my nephew for his principle application, but he does not want to take my phone call or wechat. I have to learn so many things, go to swimming, take some pluralsight.com courses, and work on other things like my mortgage loan search, and other things like going out and enjoying the friendship etc.

I spent this Saturday with most of time to practice mock interview. Starting from 10:00 AM, 12:00 PM, 4:00 PM. Before it is so rare that I can meet one person who talked to me about algorithm and data structure, it only happened twice or thrice from 2010 to 2015. One hour a year from Microsoft employee. But since last March 2017, after I started to practice mock interview, I gained confidence to meet a programmer a day, I had so much experience to work with different programmers, from senior developer, leaders, managers, graduate student and undergraduate students. Every hour a time, I have met over 150 programmers over last 10 months.

Indian 

Through mock interview, I have worked with more than twenty Indian students or programmers now. I am pretty sure that it is very easy to work with Indians. Definitely I can get along and I can work with them easily.

I could not believe that I have learned so many things from Indian. Before March 2017, I never had chance to sit down with an Indian to talk over an hour. But now I have learned so many things through mock interview those 20 + hours.

Chinese

Now it is so easy to get connected to Chinese. I have met so many graduate students in USA and Canada. I almost interviewed over ten top 100 ranking university students.

Today it is the first time I met a Chinese who likes to talk to me over one hour and 45 minutes, also works full time in a startup in California. I asked the extra algorithm for him to solve, and then he found that the problem was so interesting. I kept telling him that I will not give any hint. But he solved the problem pretty quickly.

We do discuss some math problem, how to define the possible brute force solution for maximum number of chunks. I argued that the first chunk starts from index = 0, one option only. But the end index of first chunk can be 0, 1, 2, to N - 1, N options. So brute force gives N options first chunk. We at most have N chunks, so brute force solution's time complexity is O(N * N). This gives the peer hint and he quickly came out the solution.

Startup, Microsoft and Googler

It is not big surprise for me to meet a peer on mock interview platform who works for Microsoft and has Google onsite interview experience today, I learn how other people work and how good people are to solve algorithm and data structure problems. I have met more than five Microsoft employees since last December.

Through mock interview practice, I learn how to connect to people and also learn from each of them.

Root of a number

January 13, 2018

Introduction

It is so interesting to meet an engineer and I can compare to the peer's performance. What we discussed in the mock interview at the very beginning is about lower bound and upper bound. For example, given x = 7, n = 3, how to define an upper and lower bound fitting for most of x >=0 and n >0 as integer?

We have to define it to apply two case, one is x < 1 and x > 1. The good range is [0, Math.min(1, x)]. The thing I can learn from the peer is the way the peer communicates, and how easy he is to be able to communicate. That is something I can learn.

Of course the peer has not practiced the algorithm over ten times in last six months as I do. But let us look at his code and see how good it is.

Code review 

Here is the C# code.

One algorithm is tagged #好玩？

January 13, 2018

Introduction

It is the first time I tag the algorithm using Chinese word 好玩. I met the peer through the mock interview and I spent over 30 minutes time to discuss the solution with him. At the end of the discussion, he said that word in Chinese 好玩. Both of us worked on mathematics major, the peer works for a startup in California, and I work in the city Vancouver, Canada.

It is very good time to coach each other after 50 minutes mock interview. I asked the peer to solve the algorithm called maximum number of chunks.

Algorithm discussion

Here is the transcript for our discussion. The final result is that both of us are very happy. I like to measure how good the peer can think and analyze the problem, he did so well, and then he came out a simple formula for the solution.

At the very beginning, I presented the problem statement. And then the peer asked me can you give more examples?

So what I did is to add more examples. And then we discussed the brute force solution. What is maximum number of first chunk options.

First chunk always starts from index equal to zero, but the end value can be index value 0 to N - 1. The peer came out the checking of running sum equals to the expected sum of ( 1 + 2 +...+ index).

Leetcode: Array of Array products

January 13, 2018

Introduction

It is the time for me to write Array of array products again. Last two practices, I made some mistakes. One time I made 3 mistakes in Dec. 2017, I documented in the blog. So this time I have to work on something to make it perfect. What I did is to count how many multiplication I have to allow me to consume in the design of dynamic programming method.

Code review

Here is C# code.

I wrote down the multiplication allowed in first iteration from left to right, I only allow myself to do n multiplication. However, second iteration from right to left, I have to do one more extra multiplication, take the existing product value to multiple rightToLeftProduct variable.

This time I did extra work to check how many multiplication operations are allowed in the design process, I write perfect code based on this extra checking.

After the mock interview, I asked the peer to solve extra algorithm related to DFS and dynamic programming method.

Actionable Items

January 14, 2018 11:33 PM

Julia, try to work on your analysis. Make your writing a better one. Think about production ready code. Also think about analysis of algorithm should be ready to publish as well.

Learn from the peer how he wrote his analysis algorithm. The blog is here.

JavaScript: Largest smaller binary search tree key

January 13, 2018

Introduction

I do not have time to write a lot of JavaScript code last 12 months, since most of time I have to write C# code. But this morning 12:00 pm I had a mock interview, I met a programmer and then he showed me how to solve the problem using JavaScript.

Code review

Here is JavaScript code with his code from line 26 to 59. The peer came out the recursive solution and then base case correctly, and only comment I had is to clean up code, avoid duplicate node.right on line 46 and 51.

Since the peer solves the problem in 20 minutes, I told him that I will start my algorithm. After I complete the algorithm, I will ask him an extra algorithm problem.

Get minimum path sum of Root to leaf path in a tree

January 13, 2018

Introduction

It is my turn to write a tree recursive solution called minimum value of all path sum, for each path root to leaf node in a tree. I have already practiced multiple times, this time I spent first 15 minutes to write down my analysis.

Analysis of algorithm

It is the first time I have time to carefully go over each step and write down the analysis. This only happens after I master the recursive function using the template.

First of all I write down all the paths from root to leaf node first, and add the sum for each path. And I give a title called "Go over all the paths". Next I write down "Find minimum value". Third I write down my depth first search using recursive method. I write my template for recursive solution.

Here is my analysis of the algorithm:

Code review

Here is my C# code.