Algorithm: Find longest repeated substring without overlap

Here is my github page for the algorithm. 

Stocks making the biggest moves in the premarket: Halliburton, Chevron, eBay, Delta & more

Here is the article.

Leetcode solved problem: From 461 to 492

July 21, 2020

Introduction

It is important for me to push myself to write code every day. I did not do that since January 2020, coronavius, running to prepare for Vancouver sun run, and then hay fever, and stock market crashes. Starting from May 28, 2020, I had to prepare for Facebook phone screen, and then I started to work on algorithms again. I only solved 32 new algorithms so far.

32 algorithms

I am so glad to learn the benefit to write code for those simple algorithms. Even the tough one, it only took me less than three or four hours to make it work.

Things I like to talk about is about Trie data structure, using stack, and other things like tree algorithms.

Facts to review

It takes 3 days nonstop practice, so that I can find out how many weakness I have in my thinking process and drafting process.

After my first break-down, it took me 40 minutes to go back to think efficiently using knightdial algorithm. I learn that I have to let my brain get used to those stress, and then I can perform better.

At my peak time, it only takes me five minutes to recall the whole thing, after six months break, the first one will take me 40 minutes. To prepare for Facebook phone screen, I need something like 2 - 3 minutes to refresh my muscle memory.

Two hours research: Oil stock 10% gain

Here is the link.

I am studying Chevron, and deal to purchase Nobel energy in 5 billion dollars.

Inflations -> good structure company with a lot of debt - cash deal to purchase stock of Nobel

Debt-burden energy company

Energy - all sectors - analyze things - who is good credit star rating ...

How do I handle my USA stock portfolio?

Five ideas to get back to more sports life

July 21, 2020

Introduction

It is tough project to work on. I like to lose 10 lb, and also play more tennis sports as well. I like to write down five ideas to go back to more sports life.

Five ideas 

1. Need to learn how to balance work, algorithm practice, stock investment and sports activities; 
2. Put sports first after the work and in the weekends; 
3. Start to read more about weight control, running and tennis sports;
4. Plan to finish first 20 tennis workout in one week; 
5. Plan to hike a few times in short future. 

Five hours to relax after Facebook phone screen

I spent most of time inside my home office last Friday after the work. I only took one time 30 minutes break to walk around the neighborhood I live last Saturday. I definitely needed to take a break, and walk and run and play sports, go out to meet people.

Intensive study is great for preparation. After one hour phone screen, I went out to play tennis sports.

First hour - watch a double game live in central park burnaby, I knew all those players. 
Second hour - watch another double game
Third hour - start to work on hitting against the wall
Fourth hour - take multiple breaks
Fifth hour - hit against the wall again.

How to give good impression to a Facebook manager through phone screen?

As a reminder, please keep these 4 criteria in mind during your technical interview:

• Communication: Ask clarifying questions around the problem before solving 
• Speed: One of our values here is moving fast 
• Verification and testing: bug free as possible, talking through edge cases 
• Problem-solving: Finding a working solution

Based on my own experience, the second algorithm is hard to approach the problem using dynamic programming. I like to push myself think about more about the solution, and then I remember that it is better to have a working solution. I only have 20 minutes after the first algorithm. I have to be able to write the code and test the code and make sure it works. 

To lower the risk, I did not choose to take risk to go for analysis of dynamic programming solution. It is tough decision. 

Go to brute force solution second one, if I have time, then I will write an optimal solution. It is not easy to approach the problem, but I have to solve it first. 

Understand what is thinking like a programmer

Understand what is thinking like a manager

Crafting skills - how many hours minimal to maintain the level?

July 21, 2020

Introduction

It is my short project to work on. I have to evaluate how many hours minimal one month in order to maintain my crafting skills to the certain level. It is hard for me to measure my own curiosity, and ability to stretch my brain muscle to think a hard level algorithm in less than five minutes.

How many hours minimal to maintain the level?  

I do think that I deserve to have a good career and enjoy the life as well. In order for me to work and stay competitive, I like to push myself to improve my crafting skills.

40 hours
20 hours
10 hours
5 hours

I do think that it is important for me to practice as many hours as possible. I should think about 40 hours for the first week, and then reduce hours to less the second week. There are so many things for me to work on.

What is most important in Facebook phone screen?

July 21, 2020

Introduction

It is only phone screen I had this year in 2020. I do appreciate the chance to be selected, so that I spent two months to learn and review a lot of algorithms. Preparation is most important, and also I do believe that it is also important to promote how hard I have to push myself to share my progress, what I learn, and what is challenging. 

Preparation

It takes time for me to learn and get used to think how to solve algorithm quickly. I do think that I have to go over at least 100 algorithms before the phone screen. 

During Facebook phone screen

I do think that it is important for me to learn how to communicate, ask clarification question, and also make sure that I can write executable code, working solution, and moving fast in 45 minutes. 

I understand that it is important for me to push myself, and let myself to take some risk, and go for a working solution, make sure that I can produce something working to solve the problem.

In other words, I have to take less optimal solution if the time is not enough for me to analyze and think clearly for a tough algorithm.

Why should I push myself very hard three days before Facebook phone screen?

July 21, 2020

Introduction

I learn from mistakes I made through Leetcode easy level tree algorithms. I understand that it is important for me to be a responsible person, how come I can take a job if I can not produce high quality of code in less than 10 to 15 minutes, and let the fact stay true for so many years. It is my 10th year on the same job. I have enough time to learn and overcome any weakness I find.

Push myself hard

It is so interesting to learn how our brain works under stress. Also it is about 53 year old engineer, or just a programmer.

How to control risk on Facebook phone screen?

July 21, 2020

Introduction

I like to talk about how to control risk on Facebook phone screen. I do think that there are so many algorithms for me to review, and also there are so many classical algorithms for me to learn and some of them are really hard level algorithms. 

Sending out messages on Linkedin

I did send out over 10 messages on Linkedin.com, and then started to get myself understand importance of project. I got a friend to offer me four mock interview to work on communication skills.

49 tagged blogs about 2020 Facebook phone screen

I do think that it is important for me to work on those algorithm and data structure. It is vital for a software programmer to survive, no matter it is good time or hard time. What is it? I do think that problem solving ability, and crafting skills, and also ability to learn.

Here is the link.

The risk

It is high probability for me to fail Facebook phone screen. Even though I was lucky to be selected for my first onsite from Facebook. This time it is more serious and more competitive to stay on top of candidates.

I like to make sure that I do my best as I can. Enjoy the learning. Also it is important for me to find weakness to work on.

I did start my first marathon weekend to work on algorithm non-stopped for 3 days in the row. I knew the difference this time, I do think that I have to really work on so many things in terms of Leetcode discuss post, analyze of algorithms, how to stay on track to solve a simple problem. Compared to my previous experience from 2015 to 2019, I tried to memorize the solutions for as many algorithms as I can.

My investment community on wechat

Talk about algorithm practice from a stock investor viewpoint

May 28 - July 20 two months preparation for Facebook phone screen

Here is github page for my preparation repository. 

It is a nice journey, and I also worked on a few small projects at work. I got motivated and push myself to write more code at work as well.

Is it possible for me to be a mediocre programmer to be a competitive one? Preparation is so important, and I have to be humble and write easy level algorithms. Stay confident, take risk to learn basic things. Crafting skills are important, but without practice, there is no skills.

Cannot stop practice algorithm!

How to lose 10 lbs in 100 hours tennis sport this summer?

Tennis sports and my sports family

I went back to tennis court after one hour phone screen. I only took less than 30 minutes walk around the community last weekend. I was busy and sit whole day to review and code algorithm nonstopped. It is important for me to go back to tennis court, and then meet my tennis family.

16 tennis courts and wall

I know more than hundred people on tennis court. Any time in summer time, I can meet people and say hi. Every one of them is potential a good friend, who can help me relax and hit tennis with me, help me quickly lose those body fat. My weight is 196 lb after so many days away from tennis court.

I did spend time to watch best tennis match on double match, and I chatted with a young chinese girl in her eight year old, her father was playing double tennis, her 10 year old brother played tennis against the wall. I mainly asked about coronavirus, school stuff. She likes drawing.

I spent over four hours on tennis court. I talked to over 20 people, and watched games, and also played against the wall.

Here are highlights:

1. Dress properly - casul shoes, tennis shoes, and tennis clothing
2. Bring water bottom, chat with people
3. Work on my big muscles, run and hit against the wall half hour; take break; half hour;
4. feel my body, and examine if any muscle, bone and joints are functioning properly.

Usually I run one hour before I play tennis. Usually it is better for me to run 5000 meters around central park two rounds. Warm up first, and then I can start to play against wall half hour. And then play some matches if I have chance.

Most of important, meet people and chat, and prepare for future opportunity to play together.

It is my Canadian family on tennis court.

Get smart on things to work on

Three biggest problems last 5 years on those over 60 tree algorithms

Three things improved last five year through those Leetcode tree algorithms

Two hours review of tree algorithms on Leetcode on July 20, 2020

July 22, 2020

Introduction

It is the first time I like to go over the tree algorithms on Leetcode.com. I started from hard level tree algorithms, and medium level algorithms next. I spent over two hours and then I was so busy to review and learn a few things. 

My favorite algorithm No. 1

It is my most favorite algorithm to review. 

No. 2

No. 3 

What is most important in a software programmer life?

July 21, 2020

Introduction

It is hard for me to figure out what is most important as a software programmer. But I did remember those days how I struggled to stay at home two weeks after March 19, 2020. 

Health is most important

Stay competitive is very important

Stay fit is most important

Stay financial independent is very important

Other things are important as well - keep myself to get connected to hard working people. 

How many algorithms I worked on last weekend?

Say goodbye to Facebook phone screen

July 21, 2020

Introduction

It is such great journey to work with Facebook and then I had a phone screen on July 20 2020. The phone screen was normal as 45 minutes, 2 algorithms to work on. I have to say goodbye to Facebook phone screen. 

Get organized

I have to continue to work on algorithm practice. I do think that the habit is good and healthy to code algorithm daily. I like to push myself to continue to practice, and also start to learn more about system design as well. 

Proverbs 28:19-20 A hard worker has plenty of food, but a person who chases fantasies ends up in poverty. The trustworthy person will get a rich reward, but a person who wants quick riches will get into trouble.

【箴二十八19】「耕种自己田地的，必得饱食；追随虚浮的，足受穷乏。」

Leetcode discuss: 979. Distribute Coins in Binary Tree

Here is the link.

C# Need to work on a simple case study

July 18, 2020

979. Distribute Coins in Binary Tree

Introduction

It is my first algorithm in Leetcode mock interview. I spent over 30 minutes to think about so many ways to break through the problem. Nothing can lead me to a simple solution.

Ideas I thought about in mock interview
I know that root node has coins with val, and it should take away val - 1 coins. But I continued to think which way to go, I tried to build a table.
      Root node
      /               \
Left subtree       Right subtree

I tried to think about from bottom up, leaf node has only one connection to parent node, up/ down two directions.

I also think about from root node, how to determine if left subtree has extra coins, or righ subtree has extra coins. It is impossible that both has extra coins.

Tree algorithms
It is totally different experience to solve tree algorithms after six month break. Recursive thinking is most challenge task.

Follow up
July 19, 2020 12:17 PM
Case study
A simple tree with root node (coins = 3) left child (coins 0) left.left child (coins 0)
The root node need to move away 2, left child need move one coin to add, left.left need move one coin to add, in total, there are 2.

Follow up 7/19/2020 1:32 PM
Case study
I need to work on a test case and see if I can figure out the coins move correctly or not.

The idea to calculate total coins moved is to calculate each edge what is number of coins to move from node to it's parent node. It is easy to apply a post order traversal. -1 means parent node sends a coin to it's child, +1 means that the node sends a coin to it's parent node.

The total coins moved is to add sum of each edge's absolute value.

In summary, using post order traversal, and also determine how many coins to move to parent node each time. Starting from leaf node, a node will consider it's children nodes and then add itself to the parent node.

The coins moved in the above diagram is 3.

Recursive function design
Apply post order traversal, recursive function will return number of coins to move in direction.

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

namespace _979_distribute_coins_in_binary_tree
{
    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)
        {
            var node0  = new TreeNode(0);
            var node0B = new TreeNode(0);
            var node0C = new TreeNode(0);
            var node4  = new TreeNode(4);
            var node0D = new TreeNode(0);
            var node3  = new TreeNode(3);
            var node0E = new TreeNode(0);

            node0.left   = node0B;
            node0.right  = node0C;

            node0B.left  = node4;
            node0B.right = node0D;

            node0C.left  = node3;
            node0C.right = node0E;

            DistributeCoins(node0);

            Console.WriteLine(coinsMoved);
        }

        public static int coinsMoved; 
        public static int DistributeCoins(TreeNode root)
        {
            if (root == null)
                return 0;

            coinsMoved = 0;

            postOrderTraversal(root);

            return coinsMoved;
        }

        /// <summary>
        /// https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/221939/C%2B%2B-with-picture-post-order-traversal
        /// go over the example in the above discuss 
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static int postOrderTraversal(TreeNode root)
        {
            if (root == null)
                return 0;

            var left  = postOrderTraversal(root.left);
            var right = postOrderTraversal(root.right);

            coinsMoved += Math.Abs(left) + Math.Abs(right);

            return left + right + root.val - 1;
        }
    }
}

Leetcode discuss: 332. Reconstruct Itinerary

Here is the link.

C# DFS algorithm with tough decisions to make

July 18, 2020

Introduction
It is my preparation for phone screen from Facebook on July 20, 2020. I like to work on leetcode mock interview phone screen mock interview nonstop for two days.

I came cross this algorithm, and it took me more than two hours to make it work. I want to say something: "Being a programmer, most important is to be patient, and also observe what happens using Visual Studio".

I learned so many lessons from those few hours. I like to write a simple solution, so I tried a few ideas and failed all the way until I figured out the simple one.

Here are highlights:

1. More than one ticket for same start and dest cities. For example, JFK to NRT, there are two tickets.
2. I tried to use C# Dictionary<string, SortedSet>, I ran into failed test case, so duplicate allows, SortedSet cannot be used;
3. I tried to use C# LinkedList, but I had problem to put it back after failed DFS search. I chose to use LinkedList RemoveFirst, AddFirst API, it does not work for back tracking.
4. I tried to use HashSet to make unique ticket like "JFK"+"NRT". Because two tickets are available for same ticket, I have to use original hashMap to mark visit.
5. I also spent over 15 minutes to figure out that variable found as List is empty and I have to add ref.
6. List is used, and then apply Sort API; Later List.RemoveAt index position, and then List.InsertAt index position position; So all destination are sorted in lexicographically order.
7. Play with base case - all tickets are used and only used once.

Performance
It should take me less than 25 minutes, but I took over 100 minutes to play with the code.

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

namespace airlineTickets
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase3(); 
        }

        public static void RunTestcase1()
        {
            // [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
            var tickets = new List<IList<string>>();

            tickets.Add(new List<string>() {"MUC", "LHR" });
            tickets.Add(new List<string>() {"JFK", "MUC" });
            tickets.Add(new List<string>() {"SFO", "SJC" });
            tickets.Add(new List<string>() {"LHR", "SFO" });

            var result = FindItinerary(tickets);
        }

        public static void RunTestcase2()
        {
            var tickets = new List<IList<string>>();

            tickets.Add(new List<string>() {"EZE","AXA" });
            tickets.Add(new List<string>() {"TIA","ANU" });
            tickets.Add(new List<string>() {"ANU","JFK" });
            tickets.Add(new List<string>() {"JFK","ANU" });

            tickets.Add(new List<string>() {"ANU","EZE" });
            tickets.Add(new List<string>() {"TIA","ANU" });
            tickets.Add(new List<string>() {"AXA","TIA" });
            tickets.Add(new List<string>() {"TIA","JFK" });
            tickets.Add(new List<string>() {"ANU","TIA" });
            tickets.Add(new List<string>() {"JFK","TIA" });            

            var result = FindItinerary(tickets);        
        }

        public static void RunTestcase3()
        {
            var tickets = new List<IList<string>>();

            // [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

            tickets.Add(new List<string>() { "JFK","KUL" });
            tickets.Add(new List<string>() { "JFK","NRT" });
            tickets.Add(new List<string>() { "NRT","JFK" });                  

            var result = FindItinerary(tickets);
        }

        public static IList<string> FindItinerary(IList<IList<string>> tickets)
        {
            // the idea is to run a DFS search
            // keep all tickets into a hashmap
            // path - find first path then return
            // hashMap - C# Dictionary<string, SortedSet<string>>
            if (tickets == null || tickets.Count == 0)
            {
                return new List<string>();
            }

            var count = tickets.Count;
            // ANU->TIA two tickets
            var map = new Dictionary<string, List<string>>();
            foreach (var item in tickets)
            {
                var start = item[0];
                var dest  = item[1];
                if (!map.ContainsKey(start))
                {
                    map.Add(start, new List<string>());
                }

                map[start].Add(dest);
            }

            foreach(var key in map.Keys)
            {
                map[key].Sort();                 
            }

            var path = new List<string>();
            var found = new List<string>();
            
            path.Add("JFK");

            runDFSSearch(map, 0, count, "JFK", path, ref found);

            return found;
        }

        /// DFS - mark visited
        /// backtracking
        /// check the final length 
        private static void runDFSSearch(
            Dictionary<string, List<string>> map,
            int index,
            int total,
            string start,
            List<string> path,
            ref List<string> found)
        {            
            if (found.Count > 0)
            {
                return;
            }

            // all the tickets used once and only once
            if (map.Count == 0)
            {
                found = path.ToList();
                return;
            }

            if (!map.ContainsKey(start))
            {
                return;
            }

            var destCities = map[start];
            var copy = new List<string>(destCities);

            for (int i = 0; i < copy.Count; i++ )
            {
                var dest = copy.ElementAt(i);

                path.Add(dest);
                map[start].RemoveAt(i);
                if (map[start].Count == 0)
                {
                    map.Remove(start);
                }

                runDFSSearch(map, index + 1, total, dest, path, ref found);

                // backtracking
                path.RemoveAt(path.Count - 1);
                if (!map.ContainsKey(start))
                {
                    map.Add(start, new List<string>());
                }

                map[start].Insert(i,dest);
            }
        }
    }
}

Leetcode discuss: 304. Range Sum Query 2D - Immutable

Here is the link. 

C# preprocess matrix to calculate left top corner area

July 19, 2020

Introduction
In order to get O(1) to answer the query given start left top corner and bottom right corner, it is a good idea to preprocess the left top corner area for any position in the matrix.

My practice
It took me over 20 minutes and reviewed the code since one failed test case. My first submission failed since the cross area is related to (row1 - 1, col1 - 1), not (row1, col1).

public class NumMatrix {
    private int[][] rectangle; // from (0,0) to (i, j) rectangle sum
    private int rows, columns;
    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.Length == 0 || matrix[0].Length == 0)
            return;
        
        rows = matrix.Length;
        columns = matrix[0].Length; 
        
        rectangle = new int[rows][];
        for(int i = 0; i < rows; i++)
        {
            rectangle[i] = new int[columns];
        }
        
        for(int row = 0; row < rows; row++)
        {
            for(int col = 0; col < columns; col++)
            {
                var left = col > 0? rectangle[row][col - 1] : 0;
                var upper = row > 0? rectangle[row - 1][col] : 0;
                var cross = (row > 0 && col > 0)? rectangle[row -1 ][col - 1] : 0;
                rectangle[row][col] = matrix[row][col] + left + upper - cross;
            }
        }
    }
    
    public int SumRegion(int row1, int col1, int row2, int col2) {
      if(row1 < 0 || row1 >= rows || 
         row2 < 0 || row2 >= rows || 
         row1 > row2 ||
         col1 < 0 || col1 >= columns ||
         col2 < 0 || col2 >= columns ||
         col1 > col2)
          return -1; 
        //            whole - left - up + cross              
        var area = rectangle[row2][col2]; // whole
        area -= col1 == 0? 0: rectangle[row2][col1 - 1]; // left
        area -= row1 == 0? 0: rectangle[row1 - 1][col2]; // up
        area += col1 == 0 || row1 == 0? 0: rectangle[row1-1][col1-1]; // cross
        
      return   area;         
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.SumRegion(row1,col1,row2,col2);
 */

Leetcode discuss: 935. Knight Dialer

Here is the link.

C# Need to move fast

July 18, 2020 10:36 PM

Introduction

I am preparing for Facebook phone screen on July 20, 2020. One thing I have to work on is to move fast. I will be measured how fast I can solve the problem.

I am working on this marathon on Leetcode phone mock interview, the idea is to push myself to move fast, solve as many algorithms as possible.

First I need to get myself under this drill, work on algorithm problem solving non-stoppable for 10 hours at least.

I came cross this algorithm as the second one, I remembered that I solved the problem before.

How to analyze?
It took me over 20 minutes and then I knew that it can be solved using DFS or BFS algorithm for N step. And I thought about there is no need for each path. All we need is the total count.

Another thing is that intermediate steps are also only 10 digits. The array is good enough for me to build recurrence formula. I need to count number for each digit for each step.

DFS/BFS -> 10 digits each step -> Simple recurrence
It should take me less than five minutes to spot the pattern. But it did take me 20 minutes or so.

When to code?
After over 40 minutes, I started to code the solution; First I define the hashset array, and then map digit 0 - 9 to next step, cross 1x2 or 2x1, eight directions.

Performance
It is hard for me to push myself. It is interesting to learn that I gained some confidence after two hour solving a problem this afternoon. Here is the discuss post I shared. It was tough for me to be patient to solve it after failing so many times.

Facebook phone screen advice
I like to share those four things to work on when I practice through mock interviews:
As a reminder, please keep these 4 criteria in mind during your technical interview:

1. Communication: Ask clarifying questions around the problem before solving
2. Speed: One of our values here is moving fast
3. Verification and testing: bug free as possible, talking through edge cases
4. Problem-solving: Finding a working solution

public class Solution {
    public int KnightDialer(int N) {
        // DFS -> only 10 digits each step - using array to represent 
        // 
        if( N <= 0 || N > 5000)
            return -1; 
        
        var map = new HashSet<int>[10];
        for(int i = 0; i < 10; i++)
        {
            map[i] = new HashSet<int>(); 
        }
        
        map[0] = new HashSet<int>(new int[]{4, 6});
        map[1] = new HashSet<int>(new int[]{6, 8});
        map[2] = new HashSet<int>(new int[]{7, 9});
        map[3] = new HashSet<int>(new int[]{4, 8});
        map[4] = new HashSet<int>(new int[]{0, 3, 9}); 
        //map[5] = new HashSet<int>(new int[]{});
        map[6] = new HashSet<int>(new int[]{0, 1, 7});
        map[7] = new HashSet<int>(new int[]{2, 6});
        map[8] = new HashSet<int>(new int[]{1, 3}); 
        map[9] = new HashSet<int>(new int[]{2, 4}); 
        
        var previous = new long[10];
        var current = new long[10];
        
        var number = 1000 * 1000 * 1000 +7;
        
        for(int i = 0; i < N; i++)
        {            
            if(i == 0)
            {
                for(int j = 0; j < 10; j++)
                {
                    current[j] = 1; 
                }                              
            }
            else 
            {
                for(int j = 0; j < 10; j++)
                {
                    var set = map[j];
                    foreach(var item in set)
                    {
                        current[item] = (long)(current[item] + previous[j]) % number;
                    }
                }
            }                 
            
            // reset current array
            for(int j = 0; j < 10; j++)
            {
                previous[j] = current[j];
                current[j] = 0; 
            }
        }
        
        return (int)(previous.Sum() % number); 
    }
}