weekend planning - easy tree level algorithms

July 28, 2018

Introduction

It is time for me to plan to work on easy level tree algorithms. Here is the link and I use it to find all easy level tree algorithms I plan to work on this Saturday.

Over ten tree algorithms

I like to write down every easy level tree algorithm by name. I am planning to work on those algorithm today.

Easy level algorithms I completed: 687, 110, 572, 2235, 101, 671, 543, 108, 563, 100, 538, 606, 226, 104, 872, 617.

Easy level algorithms for me to work on:
111, 112, 501, 437, 589, 270, 700, 429, 257, 107, 590, 404, 559, 653, 637, 669

687 Longest Univalue Path 32.7% Easy 111 Minimum Depth of Binary Tree 33.9% Easy 112 Path Sum 35.5% Easy 501 Find Mode in Binary Search Tree 37.8% Easy 110 Balanced Binary Tree 38.9% Easy 572 Subtree of Another Tree 40.3% Easy 437 Path Sum III 40.3% Easy 235 Lowest Common Ancestor of a Binary Search Tree 40.6% Easy 101 Symmetric Tree 41.0% Easy 589 N-ary Tree Preorder Traversal 41.2% Easy 270 Closest Binary Search Tree Value 41.3% Easy 671 Second Minimum Node In a Binary Tree 42.1% Easy 700 Search in a Binary Search Tree 42.1% Easy 429 N-ary Tree Level Order Traversal 42.4% Easy 257 Binary Tree Paths 42.4% Easy 107 Binary Tree Level Order Traversal II 43.2% Easy 543 Diameter of Binary Tree 45.2% Easy 108 Convert Sorted Array to Binary Search Tree 45.7% Easy 563 Binary Tree Tilt 46.9% Easy 590 N-ary Tree Postorder Traversal 46.9% Easy 404 Sum of Left Leaves 47.9% Easy 100 Same Tree 48.2% Easy 538 Convert BST to Greater Tree 48.8% Easy 559 Maximum Depth of N-ary Tree 49.4% Easy 606 Construct String from Binary Tree 50.2% Easy 653 Two Sum IV - Input is a BST 50.3% Easy 226 Invert Binary Tree 54.4% Easy 104 Maximum Depth of Binary Tree 56.2% Easy 637 Average of Levels in Binary Tree 56.3% Easy 669 Trim a Binary Search Tree 58.1% Easy 872 Leaf-Similar Trees 65.0% Easy 617 Merge Two Binary Trees 68.1% Eas

Where to find most hard working people?

July 28, 2018

Introduction

It is so surprising that I found a few people with thousand submission last year on leetcode, and I also read his post on one of algorithms I worked on in the evening of July 27, 2018. I know that I am out-of-date on this topic, where to find most hard working people? I also need to find some facts to support my training decision, work on Leetcode easy level algorithms.

Two role models

Those people with thousand submission last year should be my role model. I like to list two of them here, I like to train myself as they do using Leetcode online judge.

Engineer Tian Yuan:

Leetcode 687 Longest univalue path -> discussion link ->
https://leetcode.com/tyuan73/ -> Linkedin profile, solved 652/ 869, 1168 submissions last year
(Follow up on May 22, 2019 solved 783/1045, 737 submission last year, 2209/3697)

Engineer Naveen:

Leetcode 687 longest univalue path -> discussion link ->
https://leetcode.com/naveenkothamasu/ -> 1641 submissions last year, solved questions: 345/869

(Follow up on Sept. 5, 2019, soved 610/1778, contest ranking: 10932/112269)

Easy level algorithm training so amazing 

I just could not believe that the training of Leetcode easy level algorithms is so amazing. I also have the chance to learn from most hard working people as a software engineer.

Leetcode easy level algorithm training progress report

July 28, 2018

Introduction

It is time for me to write a report for my last two report Leetcode easy level training. I have worked so hard and then I submitted more than 30 algorithms in two weeks. This is the first time I did submit 30 algorithms in less than two weeks.

Progress report

Here are some facts:

1. My leetcode profile is here.  130/869, 147 submissions last year.
2. July 17 - July 31, 2018 two weeks practice github folder containing all source code. Here is the link.

I had chance to read more content about algorithms, and those content could not find using Google or other resource. I find most hard working people who know how to train themselves so hard.

I have so many issues with those easy level algorithms. I just could not enumerate how many times I stumble and how many things I like to learn from those algorithms. I have to push myself hard and also try to move forward with new algorithms.

I change my attitude, I do not stay on same emotion too long. I need to go to work, solve an algorithm and write code. I have to take risk to implement my idea first, and then talk to myself to simplify the idea, and beat the odds to finish in less than 10 minutes. Sometimes I give up and start a brand new ideas.

Leetcode 687: Longest univalue path - recursive design learning

July 27, 2018

Introduction

It is an easy level tree algorithm. I spent over 60 minutes to write and learned from other shared source code. It is very interested algorithm and I like to learn.

My learning

I chose one of the discussion and write my C# practice here.

Follow up 

7/28/2018 10:22 PM

One thing I can do is to go over the example, and walk through the example, give the explanation of the recursive function design. Also try to explain the algorithm using less than 5 minutes.

       5
    /      \
   4       5
 /   \        \
1   1        5

The idea is to traverse the tree using preorder, visit each node once. I think that it is very good practice to explain how to design a recursive function to count how many nodes from the root node to have same value continuously to leaf node.

Follow up 

August 1, 2018

I continuously used the algorithm to give the interviewee to work on one more than two times. Both of them had difficult time to come out the clean solution in less than 45 minutes. One of them has issue to work on recursive function and design the recursive function on the value cross the root of tree.

I was asked why I spend my time to work on interview, help others to prepare and learn. I explained to the peer that I also learned from his performance. When he asked me what to recurse on, if left side path or right side path, actually it is maximum of left side path and right side path. I could not tell the answer right away. I know that I just memorize the study code, I really have to give myself time to review and think and come out fully understanding as well.

I shared my thoughts with interviewee, there are hundreds of solution for this tree problem. I could not verify every line of code for you. But I did challenge you the design of recursive function is basically wrong. You cannot recurse on something cross the root node.

So good experience to be an mock interviewer on interviewing.io. It helps me to learn the algorithm I just practice. If I do speak out my mind, the interviewee did agree with me.

Sometimes it is hard for me to give feedback honestly, since the peer may be under pressure to try to get startup interviews. The feedback is important for them as well.

Leetcode 687: Longest univalue path - faulty design

July 27, 2018

Introduction

It is easy level tree algorithm. Now it is 11:51 PM, I believe that I spent over 60 minutes to work on the algorithm.

With faulty design, I managed to write a solution to pass 43/68 test cases.

My practice

Here is my C# code.

Leetcode 671: Second minimum node in a binary tree

July 27, 2018

Introduction

It is an easy level binary tree algorithm. I spent 22 minutes and then fixed the bugs a few time and passed online judge.

My practice

Here is my C# code.

Highlights of bug fix:

1. Line 48, if current value is smaller than the smallest one, then current is the smallest, previous smallest one should be second smallest one. I forgot the previous smallest one should be replaced existing one.

2. Line 50, duplicate value with smallest one; the value should not be counted toward second smallest one.

Follow up

August 29, 2018  10:40 PM

I gave the algorithm to the mock interviewee on interviewing.io, and also I had chance to review other solutions.

I like to share my solution on Leetcode discuss first. And also I like to write another solution based on given constraint, the root node is smallest one if there are two children.

Leetcode 543: Diameter of binary tree

July 27, 2018

Introduction

It is an easy level tree algorithm. There is a linear solution O(N), the idea is to traverse the tree using preorder, and then calculate the maximum path value along the way. In the recursive call of maximum path value, all possible diameter can be calculated each step.

My practice

Here is my C# practice with optimal time complexity.

I had so many issues to work on the coding. I like to share the submission results and remind myself to be humble, and work hard on easy level algorithms first.

Ideally I should spend less than 10 minutes and submit once to get accepted. Here are highlights I had in more than one hour practice.

1. Line 34, global variable needs to reset. Online judge reported error one node tree return 3.
2. Line 52, 53, left and right variable should be used, but my mistake is to call the same function again. Time limit exceeded.
3. I aimed optimal time complexity solution, but the code has some issues...
4. I wrote time complexity O(N * N) solution, and then ...

Backtracking

Backtracking leetcode discussion link is here.

Coolest aunt this August

July 26, 2018

Introduction

It is time for me to review what I have done as a sponsor to support an immigration case. Am I coolest aunt this August 2018?

Recently I worked on the immigration paper, I had chance to review my paper work and provided my late mother's old passport page copy and her visa to United States in 2001. I like to show to immigration officer that I cherished the relationship with my mom and I had real life experience with my mom and my siblings.

Coolest aunt this August

I try to be the coolest aunt this August 2018.

I know that I am very independent, have good critical thinking skills.

I did my sponsor application project by myself starting from 2016 October, and it took me more than 12 months until the paper work was accepted in October 2017. My young sister kept telling me to hire a professional to help, but I just said that I solved problems just by failing again and again.

Am I coolest aunt this August?

Follow up 

July 31, 2018

No law is well-written and it should be case by case. In order to save the time and cost, only way I can survive to support an immigration case is to do it by myself. Find ways to show the genuine relationship with my late mom and her grow-up children.

What is luck?

July 26, 2018

Introduction

It is my small research topic tonight for 10 - 30 minutes. Now it is 11:40 PM. I had a mock interview yesterday, and the peer talked about something about luck. Hard working is important, but sometimes you have to depend on the luck. The performance can fluctuate so much.

Recently I reviewed one of coaching video in my blog, talking about training hard. When you train yourself, you have less distraction, but when you are on tournament, there are so many distractions. Try to focus more when you train yourself.

I did find issues on my training on Leetcode 114 tonight.

There are a check list for me to work on. For example, Does the candidate enjoy finding multiple solutions before choosing the best one? Detail see my blog here.

What is luck? 

My baby step on easy level tree algorithms

July 26, 2018

Introduction

It is so true that I have to go through Leetcode easy level tree algorithm training first, 10 hour or 20 hours until I understand the basics again. I did practice 5 easy level tree algorithms on July 25, 2018. I could not believe that my baby step is 5 easy level algorithms a day. I felt so much joy to work on those easy level tree algorithms.

Also I had chance to meet a peer through mock interview at 10:00 PM on July 25, 2018. The peer gave me advice saying that if you do easy level algorithm very well, you will have chance to work on medium level or hard level algorithm quickly. There are so many ways to solve easy level algorithms, once you master those ways, you will much fast learn the hard level algorithm. The peer demonstrated good problem solving skills on tree algorithms.

My baby step

Here is the folder I created on github to celebrate my dedication to easy level leetcode algorithm practice. It is the first time I learn to be humble, and try to work independently first, and then seek the ideas through Leetcode discussion.

Actionable Items

I like to figure out ways to expedite my problem solving skills on easy level tree algorithms. I need to train myself another 10 to 20 hours.

Leetcode 110: balanced tree

July 26, 2018

Introduction

It is an easy level tree algorithm. I struggled more than 30 minutes when I practiced, so I asked the interviewee in mock interview, he solved less than 10 minutes in July 25, 2018 10:00 PM. I understood that it is so important to meet people and learn from others.

Here is the gist for C++ code. I will write a C# solution based on the code later.

Leetcode 114: Flatten binary tree to linked list - Every road leads to Rome

July 26, 2018

Introduction

It is most famous verse "Every road leads to Rome", and I learn from my mock interview experience. Every peer solves binary tree problem different ways, I have met over 100 people to work on binary tree. But every road leads to Rome. I have to be open to ideas, and make every idea work in my practice as well.

Story begins this way

Idea A -> failed a few times over 30 minutes -> Idea B -> succeed in less than five minutes using idea B-> felt happy over 30 minutes -> feel not right -> go back to idea A, and try to make it work. Less stress -> really learning begins here

Idea A -  left subtree as a linked list, which should connect to right subtree as linked list.
Idea B - using two global variable, previousNode, currentNode.


It is a medium level tree algorithm. I spent more than two hours to work on the algorithm tonight. I could not make the idea work more than 30 minutes, I try to make the left subtree's last node connect to the right child. I knew that my code was too complicated.

I have tried all possible solutions in the first hour, I could not make it work. And then I solved the algorithm using two global variables - previousNode, currentNode first. After 20 minutes, I decided to go back to original idea, and I felt so relaxed. I like to make my original idea work as well.

Here is the submission records. Tonight at least I struggled more than 20 minutes on this idea until I tried to write simple code, changed the idea to use two global variables, 1 hour, 37 minutes ago with one succeed submission. Now it is 10:55 PM, 10:30 I submit a solution and passed online judge using the original idea.

My submissions of Leetcode 114

Here is my solution submitted on June, 2016. I need to review the solution again.

Here is my solution which passes Leetcode online judge, submitted in July 25, 2018 at 9:10 PM. The idea is to use two global variables.

Here is my solution which passes Leetcode online judge, submitted in July 25, 2018 at 10:30 PM. The idea is to find left subtree's last node, and make it connected to right subtree linked list.

Follow up 

7/28/2018 9:11 AM
I like to show the image to compare two submission, left side is the problematic code, right side is the code which passes online judge. How to think and solve the problem?

I am trying to write down some notes here to coach myself, next time I should be careful.

First, choose the preorder traversal. Visit root node first, and then recursive call of root.left and root.right. Here when the root node is visited, assign root variable to the global variable currentNode on line 11.

Next, I need to find the place when the currentNode is the last node of left subtree, and then I need to set it next point to right subtree linked list's first node. Here line 15 I put comment saying currentNode is the last node in left subtree.

1takeinterview.com

July 26, 2018

Introduction

It is a good idea to spend 30 minutes to look into the interview coaching website. I like to figure out something through my 30 minutes study.

Here is the website.

Leetcode 114: Flatten binary tree to linked list

July 26, 2018

Introduction

It is a medium level tree algorithm, I spent over 30 minutes to struggle to write the code. I believed that I did write some code in June but I never tried the solution on the online judge. This time I really had difficult time to figure out the solution.

My practice 

I finally calmed down. I tried to write most simple solution as possible. I did look at the result, it is preorder traversal to output all the nodes in the binary tree. All I have to do is to take care of the current node. If there is a previous node, previous node's right child is current node; the current node's left child will be null pointer.

Here is my C# practice.

Sliding window minimum

July 26, 2018

Introduction

It is my 10:00 PM mock interview. I had chance to give the peer second algorithm to work on called sliding window minimum. He gave me the optimal solution but I could not fully understood the algorithm. So I decided to prove it the correctness using k = 3.

Mock interview discussion

I modified the transcript to make it more readable. Here is the transcript.



To summarize, the sliding window minimum algorithm can be solved using two scan of array, one from left to right, second one from right to left. And then each scan the minimum value is calculated after the elements of array are divided into windows with size k.

Follow up

Feb. 12, 2019

I just learned that the interviewee joined Google this Feb. 2019. I like to review mock interview, and also I like to write an algorithm based on his idea as well.

Leetcode 98 Validate Binary search tree

July 25, 2018

Introduction

It is an easy level tree algorithm. I reviewed my practice over two years ago, and then I rewrote the code.

Here is my code.

Leetcode 572: subtree of another tree

July 25, 2018

Introduction

It is an easy level tree algorithm. I wrote a C# algorithm based on my understanding, and it passes online judge.

Here is C# code.

Leetcode 563: Binary tree tilt

July 25, 2018

Introduction

It is an easy level algorithm. I wrote a solution based on my own understanding, and it works fine with online judge.

Here is my C# code.

Leetcode 538: Convert BST to great tree

July 25, 2018

Introduction

It is an easy level algorithm. The idea I chose is to traverse the tree by visiting right child, root node and left child this order.

Here is my C# algorithm.

Leetcode 110: balanced binary tree

July 25, 2018

Introduction

It is easy level tree algorithm. I worked on the algorithm and try to choose O(N) time complexity algorithm, by visiting all the nodes in the tree once. I ended up to spend over 30 minutes and then the code has multiple bugs and a few test cases failed.

I like to document my learning on the tree level algorithm and encourage myself to practice more on easy level algorithms.

My practice

Here is my C# code with multiple failed test cases.

How smart you can control your expense?

July 24, 2018

Introduction

It is 11:39 PM. I like to do 10 minutes study about controlling expenses. My argument is that a smart programmer should be very smart to control his/ her expense. We all know that the software programmer as a career is not easy one. Specially I had met a few people on the job market and I understand how stressful it is.

My understanding is that very good software product can be built by so many iterations. If the living expenses and job security is questionable, then the software programmer will not have too much determination to optimize the product.

I need to learn better to control my expense. I like to do some study on this topic as well.

Actionable Item

Next time do not spend over $300 dollars on any project, set a cap value to $300.00. I have to count tax paid, all living expenses paid in order to save those money.

I need to plan carefully. Money cannot buy success.

Leetcode 96. Unique Binary Search Trees

One week for new habit

Introduction

I like to write down if I can build a new habit to code every day, using leetcode online judge to train myself.


How many days does it take for me to build a habit to write code daily?

I find out that it is easy to write code for easy level algorithms on Leetcode.com. I like to write easy level algorithms to train myself in next two weeks. Also I like to do some small research how to build a good habit to write code daily.

One week 24 algorithms

I wrote three hard, two medium, 19 easy level algorithms in one week. I train myself in a week using those 23 algorithms.

I started from July 17 to July 24, I wrote 23 algorithms and also passed Leetcode online judge. The algorithms are

Easy level
63, 88
113, 198,
202, 203, 205, 231, 234, 277, 278, 283, 290
303, 326, 343, 349, 387,
438,

Medium level
556
648

Hard level

132
273
301

In order to pass Leetcode online judge for the above 23 algorithms, I did a lot of work and surprisingly I was so happy to write code for those algorithms. I am a happy problem solver.

Leetcode 301 Remove invalid parentheses

It is hard level algorithm. I worked on the algorithm more than 12 months ago I have to make algorithm simple as remembering one test case, how to come out the story how to solve it, for example, hard level algorithm 301. Here is my practice documented in the blog.

Leetcode 648 redudant connection

Also I learn that I spent time to write down my frustration and learning more than 6 months ago, but at that time I did not learn that it is most important to write the code for the algorithm and pass online judge.

To build a new habit to write code and run against Leetcode online judge.

Great coach videos

July 23, 2018

Introduction

It is such good videos about Leetcode algorithms. I like to spend time on those videos.

https://cspiration.com/

Leetcode 132: Palindrome partition II

July 23, 2018

Introduction

It is hard level algorithm and it is very interesting problem. I spent over one hour to study all the discussions but I am not sure if I understand the problem.

I found one video and then finally I understood the min cut meaning. Here is the video I really figured out the problem.

My practice

I like to read two discussion. One is here. The second one is here.

This video teaching is an excellent one. And the source code is here. I will write one using C# as well.

Time spent

9:00 PM - 11:28 PM

I could not believe that I had luxury to spend over two hours on this algorithm.

careercup.com website

July 22, 2018

Introduction

It is my summer drill for next few weeks. I like to choose one of four biggest software companies and then work on algorithms and train myself to think hard.

I start to use careercup.com website and search using keyword facebook, sort by latest date.

Here is the link I am using tonight.

Leetcode 556. Next Greater Element III

July 22, 2018

Introduction

It is a medium level algorithm, and it is not easy to come out the idea to find smallest larger integer. I plan to write the algorithm in short future.

My practice 

It took me over 60 minutes to write the code. I submitted a few times before the code can pass online judge.

Here is the C# code.


There are a few issues to slow me down in the coding process. I will look into later.

1. Content is wrong. Try to call .ToString() method from a char array, and then output is not char array content. I fixed the issue on line 56, using string constructor instead.
2. Confuse myself on line 76, current variable name is confusing. It is better called digit, which should be declared as int, int digit = s[i] - '0'
3. ...

Actionable Item

I do not know how to come out the idea by myself next time, I read the hint and analysis from geeksforgeeks.com "Find next greater number with the same set of digits" this time. The article link is here.

I have to push myself hard and figure out the idea by myself next time. The analysis is so well written in the article. Here is the analysis:

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

Following are few observations about the next greater number.
1) If all digits sorted in descending order, then output is always “Not Possible”. For example, 4321.
2) If all digits are sorted in ascending order, then we need to swap last two digits. For example, 1234.
3) For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)

Following is the algorithm for finding the next greater number.
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

Count down the weekend hours

July 22, 2018

Introduction

It is 8:30 PM and I have three hours left to say goodbye for the weekend. I like to work on 1 to 5 10 to 20 easy level algorithms just by quickly scanning the problem statement, and thinking about a few minutes, and checking discussion panel.

Easy level algorithms

Here are easy level algorithms I like to work on. Leetcode 292, 303, 326, 342, 344, 345.

Leetcode 290. Word Pattern

July 22, 2018

Introduction

It is easy level algorithm called word pattern. I did not catch the constraint until my code failed the test case: "abba" with "dog dog dog dog". The problem statement is written using the following phrases:  bijection. Given example 4 is the test case I failed in my first writing.

Here is my C# code passing online judge.

Leetcode 283: Move zeros

July 22, 2018

Introduction

It is an easy level algorithm called move zeros. The time complexity should be O(N), N is the array's length.

Here is my C# solution.

Leetcode 278. First Bad Version

July 22, 2018

Introduction

It is an easy level algorithm called First bad version. The binary search algorithm is applied and also the lowest index is found for the first bad version.

Here is my C# code.