Leetcode dsicuss: Leetcode 600 questions beyond - strategies and tips

Here is the link. 

Dec. 30, 2020

I like to get advice how to advance my problem solving skills by practicing Leetcode algorithm.

I solved over 180 algorithms in 2020 to prepare for Facebook onsite (August) and Google onsite (December), in total I solved 605 algorithms (243 Easy/ 289 Medium/ 73 Hard). After Google phone screen, I paid for Leetcode annual premium to prepare Google onsite in Oct. 2020, I finished 14 set of Google mock onsite interviews.

I like to get advice how to improve my problem solving skills. Here are my plan in 2021:

1. Solve all Leetcode premium Facebook, Amazon, Google, Microsoft mock onsite interview questions;
2. Solve all Google last 6 months common asked hard/ medium level algorithms;
3. Follow common asked algorithms from those companies, make sure that I can see the improvements through my practice.

Here are a few Leetcode discuss posts written by me in 2020 I like to share.

1. 1368. Minimum Cost to Make at Least One Valid Path in a Grid - hard level
2. 1631. Path With Minimum Effort
3. 1231. Divide Chocolate
4. 1293. Shortest Path in a Grid with Obstacles Elimination
5. 552. Student Attendance Record II
6. 378. Kth Smallest Element in a Sorted Matrix

My favorite discussion posts related to tree and other topics:

1. 687. Longest Univalue Path
2. 236. Lowest Common Ancestor of a Binary Tree
3. 889. Construct Binary Tree from Preorder and Postorder Traversal

I enjoyed most in 2020 to go over all those links related to dynamic programming. I really enjoyed the learning how to solve dynamic programming algorithms.
Important and Useful links from all over the LeetCode

My most favorite reading to prepare for Google onsite
Nov. 27, 2020
Google | New Grad L3 [ Pending ]
Helpful Channels by Rank [According to me] :
Back To Back SWE ( Best one for everything )
Abdul Bari ( Very good, when it comes to learning new Data Structures )
WilliamFiset ( Very Good for learning Graph problems )
Kevin Naughton Jr. ( Good for random medium problems. Does not always solve the most effecient way, but it is good enough )
Nick White ( Same as the above )
happygirlzt ( Solves a lot of hard problems. Even if you don't understand her soll, if you watch her code you can figure out yourself )

Toughest bug I wrote and hard to fix by myself
If you are the expert on Leetcode, you know where I am in terms of weakness. I still find myself to struggle on small details here and there.

1. 416. Partition Equal Subset Sum
2. 737. Sentence Similarity II

My hobby

I really love to practice hard level algorithms, and I also like to explore different ideas from top players, and then copy idea and write C# practice in less than 15 or 20 minutes for those hard level algorithms. My favorite players are Lee215 and a few others. When I have free time, I always like to try some new ideas, specially hard level, try at least three top voted discuss posts, and I really like to advance my C# coding skills.

85 - Maximal Rectangle
(Second practice - C# - Curiosity - Study and learn - 84 Largest histogram

84 - largest rectangle in histogram
C# Showcase how to solve the problem starting from 2015
How to analyze the problem starting from brute force solution?
It takes a few years to learn those two hard level algorithms 84 and 85. I think that one of practical approaches is to write at least three solutions just by copying ideas and code, convert it to my own language choice first. One of ideas I tried is to work on a simple test case, explain to myself using the test case, build confidence by solving this simple test case first, and later if I have time, then I can add some edge cases discussion.

Mathmatics is my hobby. Security and cryptograhpy is my favorite courses in my academic learning experience. I really like to advance my research skills, I think that Leetcode algorithm practice will help me to improve my research talent.

Please share your tips and strategies if you have 5 to 10 minutes, your favorite top players on Leetcode, who to learn from ideas and coding from Leetcode discuss post.

Happy new year 2021 and great success for everyone in 2021.

onsitephone screengoogle onsiteleetcode premiumonsite preparationhard levelfang onsitealgorithm interviewfacebook onsiteonsite 2020

Leetcode discuss: 687. Longest Univalue Path | 10 upvotes | 474 views

 Here is the link. 

C# post order - check with parent value with step by step illustration

Added on Feb. 2019

The idea to solve the problem is to avoid using root node to compare with left and right child, two user cases; Every node works with its parent node instead.

It is very challenge to explain and prove the code written is correct based on counting the edge from node to it's parent node.

What I like to suggest is to go over a few steps based on an example to test manually before writing the code. First step is to number every node in the tree using a, b, c, d,..; And then work on edge value calculation following the order of nodes in traversal, specify each edge using node id; third step is to calculate cross path and explain how it works for the maximum value.

I like to show the steps to work on an example, how to explain the idea and come out the design. Since there are so many ways to approach the problems, it is important to make the approach easy to understand.

Added on June 2019
Case study a binary tree

To understand the approach, let us work on simple test case, a binary tree with three nodes, root node with value 5, and left and right child both with value 5 as well:

Here is the overview to display, after that, I will go over one step a time.
Here are hightlights:

1. Traversal the tree using post order traversal, mark with a, b, c in the order of traversal for each node;
2. Add edge value to each node, every node will check its parent and see its value equal to parent value;
3. Add cross path value next to the node from 5a, 5b, 5c. Only 5c has cross path value 2.

Quick overview for each step

Three steps, each step is illustrated one diagram:
step 1: Post order traversal the tree, mark the order using a, b, c next to the node.

step 2: Calculate edge value, and add value next to the node.

step 3: Calculate the cross path value, add value next to the node

The following tree with node value 5 is very helpful to illustrate the process.

The longest univalue path is 2, and the edge count is 2, including one edge from root node to its left child, and one edge from root node to its right child.

There are so many ways to approach the problem, to check with parent value is different from the above counting. The edge is counted from left child to it's parent, likewise the right child to its parent. The node is counting the edges toward itself from direct children nodes first, and also includes it's child's count if need.

How to approach the problem in detail?

A few steps will be explained in the following. using postorder traversal

First, we work on recursive function. Every node is to check with its parent node's path value. Post order traversal, bottom up, three steps, left child 5a, right child 5b, root node 5c, all nodes in the tree have value 5, using a, b c to mark them with unique id, and also alphabetic order is the order of post order traversal.

step 1:

The first node visited is 5a, and its value is equal to it's parent node 5c. 1 edge is added next to 5a. The edge is from node 5a to node 5c.
step 2:

The second node visted is 5b, and its value is equal to it's parent node 5c. One edge is added next to 5b.

step 3:

The third visited node is 5c, and the value does not equal to it's parent node's value. 0 is added next to 5c.

Combination of step 1, 2, 3:

The above tree left child with node value 5, 1 counts for the edge of the node 5 to its parent, in other words, edge from node 5a to 5c;

likewise the right child.
Now the calucation of cross path, bottom up, post order, in the order of 5a, 5b, 5c

Step 1: work on 5a-1-?, cross path value

Step 2: work on 5b-1

Step 3: work on 5c-1
Cross path should be two edges, 5a->5c, 5b->5c

The node 5c's cross path value is 2, since two edges, one is 5a to 5c, and the other is 5b to 5c.

I think that it is definitely good idea in general to go over an example first, and then write the code based on the idea to check with parent value.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace longest_univalue_path___compare_to_root
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    class Program
    {
        static void Main(string[] args)
        {
        }

        int maxCrossPath = 0; // global variable
        public int LongestUnivaluePath(TreeNode root)
        {
            if (root == null)
            {
                return 0;
            }

            maxCrossPath = 0;
            postOrderTraversal(root, root.val);

            return maxCrossPath;
        }

        private int postOrderTraversal(TreeNode node, int parentValue)
        {
            if (node == null)
            {
                return 0;
            }

            var current = node.val;

            int left  = postOrderTraversal(node.left,  current);
            int right = postOrderTraversal(node.right, current);

            maxCrossPath = Math.Max(maxCrossPath, left + right); // longest univalue path crossing the root

            if (parentValue == node.val)
            {
                return Math.Max(left, right) + 1;
            }

            return 0;
        }
    }
}




124. Binary Tree Maximum Path Sum

Here is the link.

C# mock interview practice on Nov 24, 2019 with insights

Nov 25, 2019
It is one of my mock interview algorithms. I solved the algorithm but I also experienced the nervousness since I could not remember if I solved the algorithm before. It is a hard level algorithm, and I like to write down how to approach the algorithm in the contest or mock interview or onsite.

I solved all tree algorithms on Leetcode six months ago. But my generic approach is to solve all easy level algorithms on Leetcode.com first, and then move to medium level. So it is important for me to explain how to approach this hard level algorithm since I solved similar easy level tree algorithm called longest univalue path, my discussion post is here. I am still in the accumulation stage to solve as many algorithms as possible. Be greedy, solve easy one, solve one with less time first, solve ones to help me build confidence, increase curiosity, and expand my comfortable zone.

Case study

I like to go over the example and explain to myself how to approach the problem. Let me show some diagram with my thought process in my mock interview.

I like to go over the example, and explain how I ask question what to do based on example 2.

After the work out on example 2, I learned that I need to work on an extra task to calculate the path cross the root node. The whole process from example 1 and example 2 took me around 10 to 15 minutes.

If you cannot follow the process, then I can advice you to review the post I have about longest univalue path. Here is the link.

I spent two months to interview people on interiviewing.io using a few binary tree algorithms almost every weekday, I learn and work every day on tree algorithms. Those interviewees are best teachers in the world and they brought all their education and industry experience to demonstrate how good thinkers are, I learn to build up my curiousity and be a real problem solver, open to all ideas as an interviewer and determin to make the idea work, remove bias and avoid memorization of a solution, ask good questions to follow the idea and understand the question.

References:

public class Solution {
    public int MaxPathSum(TreeNode root) {
        if (root == null)
                return 0;
            var maxPathSum = Int32.MinValue;
            postorderTraversal(root, ref maxPathSum);

            return maxPathSum; 
        }

        /// <summary>
        /// return max value of path from root node to one of node downward to leaf node
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private static int postorderTraversal(TreeNode root, ref int maxPathSum)
        {
            if (root == null)
            {
                return 0;
            }

            var maxLeft = postorderTraversal(root.left, ref maxPathSum);
            var maxRight = postorderTraversal(root.right, ref maxPathSum);

            var sumLeft  = Math.Max(0,maxLeft);
            var sumRight = Math.Max(0, maxRight);

            var currentMax = root.val + Math.Max(sumLeft, sumRight);
            var currentPath = root.val + sumLeft + sumRight; 
            maxPathSum = Math.Max(maxPathSum, currentPath);
            return currentMax;
        }
}

Lowest common ancestor in binary tree - Summary of interviews

July 4, 2019

Introduction 

I chose the tree algorithm called longest univalue path from August 2018. I spent three months to work on the algorithm in mock interview with a lot of engineers. But starting from May 2019, I choose the algorithm Lowest common ancestor instead. I have interviewed more than 15 times, I like to write some summary notes.

One tree algorithm

I have tried so many ideas to work on my problem solving skills. I hired a coach last June 2018 for two weeks, my friend told me that it is too expensive. She joined Facebook this May 2019. I know that the idea to work with a coach may not be a good idea. I have to be independent, be a problem solver. My friend just sent me an email through Linkedin.com, and ask me if I like to practice with her in 2018 when she prepares for Facebook interview. Being frugal is also very important in decision making.

I choose lowest common ancestor tree algorithm to interview on interviewing.io starting from May 2019. Since I could not learn backtracking and find the bug in my own code, I start to investigate how good people are in this industry.

I believe that this algorithm helped me tremendously. One thing I can do is to work on more algorithms, solve more problems. But learning and sharing experience through those mock interview hours are great.

I still remembered the feedback from hiring manager in top 100 software company I interviewed, he said that he does not ask the hard question like this in his interview.

I am getting better to interview senior engineers using this algorithm. Let me know if you like to practice together in the future, try this famous tree algorithm - Lowest common ancestor. I will help you find your weakness in tree algorithm problem solving.

10 benefits to master a tree algorithm

June 21, 2019

Introduction

It is my short research. I like to write a 10 benefits to master a tree algorithm. Today I was under pressure, since I have to prepare an online code assessment in a week, counting starting from this past Monday, but I still choose to use lowest common ancestor. Why, I should test the algorithm I have problems on, Coin change 2.

10 benefits

I like to use tree algorithm in mock interview, since I learn that dynamic programming will be very easy to write if the interviewee knows the solution.

I will write down my experience here later. 10 benefits, let me write down one at least first.

It is hard to master the tree algorithm called lowest common ancestor. I did ask another tree algorithm over six months over 20 people from 2018 to 2019 called longest univalue path, just after the first time I practiced the easy level tree algorithm on August 2018.

In order to master the tree algorithm lowest common ancestor (LCR), I have to learn how to master the recursive function design, early termination of traversal, preorder/ post order traversal, how to find path from p to root, how to efficiently save the path information for another one to look up, how to work with so many talent people and learn from them.

There are issues related to code performance, tree algorithm in general how to solve using recursive function.

I also need to learn from interviewees, so that I can behave best in problem solving. Figure out how people learn and work with others, solve problem together.


Benefits:

1. I can help interviewee better, drop hint, give quick inside, expedite the process interviewee solves problem;
2. I also challenge myself to learn more about how to analyze problem instead of memorizing all kinds of solutions I learn through interviews;
3. I have to constantly follow up with a practice after mock interview;

Leetcode 687: longest univalue path - C# various topics covered in practice from 2018 to 2019

Here is my post on leetcode.com.

June 2019

It is an easy level tree algorithm. I got advice to work on easy level algorithm on Leetcode.com first in June 2018. So I started to work on all easy level tree algorithms on Leetcode.com in August 2018, I found out that my first practice was hard, and my idea did not lead to a working solution. After that, I asked the algorithm on interviewing.io as an interviewer, I continued to learn from every interviewee, and I like to put together a list of topics I learn through the experience. Here are the blogs I wrote based on my mock interview experience using this algorithm from August 2018 to June 2019. I will add some of practices here for me to master the tree algorithm.

August, 2018

My failed first practice, here is the link.

Recursive function design: return longest path from root to leaf instead
My first recursive solution, here is the link.

Case study two examples
Sept. 2018
Longest path cross the root, two case studies on example trees, the link is here.

Recursive function design: return cross root longest univalue path directly
Nov., 2018
One recursive function to solve the problem, here is the link.

Feb. 2019

check with parent node's value instead of check child's node - inverse check
C# post order - check with parent value with step by step illustration, here is the link.

Count nodes instead of edges
C# post order and count nodes instead of edges

Common mistakes in mock interviews:

1. Make sure that every node is traversed, bottom up, post order traversal is most commonly used;
2. Common mistake - visit left or right only if the root value equals to its left(right) child's value
   So the whole tree will not be traversed properly.
3. Make sure that there is a place to increment one, otherwise the value will always be zero; explain to the interviewer, that one is related to which edge or node in example tree.

An experienced interviewer will check you a few things:

1. post order traversal or preorder, bottom up or top down, what is your choice?
2. How do you design recursive function, return directly asked or return indirectly?
3. Count node or count edge?
4. Do you check children node with two cases to discuss, or compare to parent node only one case?
5. Argue the code will be correct.
   A. Increment one check, relate to example tree edge or node clearly.
   B. Make sure that all nodes will be traversed. Do not put conditional check for left or right child node's value to apply traverse;
6. Can you explain the algorithm very well? At least you warm up the traversal with an example, and then explain every node what will happen. Do not jump to coding for only solution you memorize. Click here to see how I explain the algorithm in case study.

Show case

I like to share my experience how I master a tree algorithm to work with over 50 most talent people in the world, every time 45 minutes discussion, and a lot of follow-up practice after mock interview as an interviewer. I do believe that it is possible for me to master a tree algorithm. I took time from August 2018 to June 2019 after my first failure practice dated on August 11, 2018.

Right now, I move on another tree algorithm called lowest common ancestor and ask the algorithm in mock interview on interviewing.io almost every time.