Leetcode premium: Google mock onsite interview sets

 Jan. 8, 2020

Introduction

It is the first time I started to work on algorithms selected by Leetcode premium. The first step is to go over all mock onsite interview questions. I have to learn so many algorithms, and then I could easily tell my weakness in terms of finding a working solution. The most challenge is not to find optimal solution, it is to find a working solution which can be drafted in less than 20 minutes. Some of algorithms took me over hours to figure out the meanings, like Android unlocked phone. 

My performance

I do think that it is most efficient to practice those algorithm to help me prepare for Google onsite in 2020 December. 

Leetcode practice 2021 

Here is the link. 

Leetcode: Seven ideas to apply after 600 mark - Google grace hopper - GHC event in 2019

 Jan. 7, 2020

Introduction

I still remembered I attended GHC Google lake union event back in Oct. 2019 in the city of Seattle. It was such great event. I wrote about it after the event. Here is the link. I like to write about my motivation from Grace hopper. 

Being a good educator 

Grace hopper is a great role model for me to learn from. I had chance to meet a lot of people in 2019 event. I almost forgot a lot of detail until I reviewed those pictures and videos. I also had chance to get onsite in December 2020. 

It is important for me to push forward and practice more algorithms. We also can find great talent to work on so many exciting projects when switching jobs, but it is better to stay at the same job, and try different things in my life. 

I have so many needs in order for me to afford a home in the city of Vancouver. Otherwise, I think that life is comfortable. Why should I enjoy the life and write another 100 hard level algorithms by going through Leetcode premium version. 

Because I share my practice on Leetcode discuss and my blog, it is such great experience to encourage others to work hard in 2021. Pandemic will go away, do not forget to hold a lot of equity assets, catch big wave of rebound, and also I do like to have some achievements on Leetcode. 

Those hard level algorithms will help me to train myself, think better and craft better. 

I like to pretend to be a Googler. Today is my day one on the job. Cheers!

7 ideas: 

1. Pretend to be a Googler. 
2. I need to be super talent programmer first
3. I need to work hard always;
4. Work on algorithm practice first thing in a day.
5. Last thing in a day
6. Something to kill time if I have
7. 30 minutes algorithm, 30 minutes workout session
8. Read more about Grace hopper. 
9. Encourage myself to read more about industry, Google, Facebook.
10. Love ideas to innovate. Maybe I can invent something for algorithm practice after 600. 

Leetcode: Seven ideas to apply after 600 mark - 30 million unemployment

Leetcode: Seven ideas to apply after 600 mark - Housing need in Canada

 January 10, 2021

Introduction

It is my short research how to address my housing need in Canada. The condo price does not go down and the price is still over 100% gains compared to 2017. The pandemic problem is really serious and I do not think that housing need is top priority. 

Housing need

I do not like to motivate myself to practice more algorithms using material things. I do think that it is important for me to live high and good quality life as an equity researcher, a software programmer. 

One thing I can think about is to work on leetcode hard level algorithm very often. I can focus on a task which can be completed in less than 20 minutes. I give myself more time, like a hour or two. I like to go through the process very often, so I can learn how to manage myself better. 

Poverty and bankruptcy 

I need to look into how to reduce risk, and also invest on stock market. I like to spend more time to work on business study and equity research, how to make good decisions to go through second year of pandemic chaos. 

I try to avoid poverty, and focus on necessity and do not make any purchase except basic need, food and shelter. 

Leetcode: Seven ideas to apply after 600 mark - 13 million eviction in USA coming

Leetcode: Seven ideas to apply after 600 mark - 5 siblings in China

 January 10, 2020

Introduction

I cut off the connection in 2020 to focus on myself, and learn how to solve my problems by myself. This year I like to offer 30 minutes to share with my siblings in China, like 30 minutes a week. 

30 minutes a week

It is hard for me to learn to say no to siblings. But it is important for me to do that, specially after 25 years serving my mom, I still did not have a home or asset even close to my siblings. 

I learn from my own analysis, I grew up with five siblings, and I need to learn how to apply good project management and emotion control. I need to discipline myself. 

Back in 2000, I spent over $200 US dollars one month on international long distance call. This showed me lack of discipline. I just remind myself to live my own life, and be disciplined. 

Algorithm practice

I do think that algorithm practice is not just to spend time to work on practice. It is my determination to learn more and prepare for challenge projects in my life. No matter it is related to software development or other area. 

Leetcode: Seven ideas to apply after 600 mark + A trader on stock market

 January 7, 2020

Introduction

It is important for me to learn how to trade in stock market using my limit asset, and I need time and patience to learn so many things. But it is better for me to limit time on stock market, I like to focus on algorithm practice more. 

600 mark

I do think that it is much better experience for me now. I almost can tell what to learn if I can not solve the hard level algorithm. 

It is hard for me to get used to problem solving daily. It is better for me to work on my goal early in 2021. First month and first two weeks. 

Hard level challenge makes me smart, efficient and also I have better confidence and research talent. I will do better on stock market as well. 

Leetcode: Seven ideas to apply after 600 mark - 55 year old

 January 20, 2021

Introduction

It is hard for me to tell difference between 55 year old and 50 year old. But I could tell that it is hard for me to control weight. Now I am working on 200 lb weight control, the pandemic did bring a lot of stress on me, I did not pay attention to my weight. I need to look into how to work on practicing algorithm and data structure based on my age. 

55 year old

It is the first time I can learn so quickly by going through those hard level algorithms. I like to plan to work on 100 hard level algorithms in first month of 2021. 

A lot of algorithms should be same as those I already practiced. So it is more about how to analyze, approach the algorithm in efficient ways. 

I also like to plan to spend time to study system design and work on other projects as well. 

I also like to enjoy my time as a 55 year old. 

I do have 27 mock interviews as an interviewee, and I plan to work on those mock interview as well. 

Leetcode: Seven ideas to apply after 600 mark - weight control 198 lb

Leetcode: Seven ideas to apply after 600 mark - 3 Amazon, 2 Facebook, 1 Microsoft onsite

Leetcode: Seven ideas to apply after 600 mark

Leetcode discuss: 273. Integer to English Words

 Here is the link. 

First practice - C# - Check list - Take more than one hour

Dec. 30, 2020
Introduction
I came cross the algorithm in Leetcode premium Facebook mock onsite, last algorithm in 4. I spent over 35 minutes but I could not finish it.

Check list
I worked on coding using Visual studio, make sure that the code works for "123", "123456", "1234567890".

Here are the check list to record my learning:

1. Design digts, secondDigit, teens array, every thing should start from index 0 to 9 to match digit 0 to 9, easy to call.
2. More on item 1, I added "Zero" into digits, secondDigit, missing Eighteen in teens array;
3. Failed test case 0, add code to return "Zero";
4. Work on space to separate word; Call C# string.TrimEnd, assign to a variable before return;
5. Failed edge case "millon thousand", so I added the array called zeroChecking;
6. I tried to make the code easy to write, so I design a while loop using repeat, for million three digits, thousand three digits, rightmost three digits.
7. The integer is converted to a C# List, so it is always to work on first char in the list, since List.RemoveAt is called after each visit.
8. Logic of length > 8 meaning length at least 9, which should not be length >= 8.
9. Ideas to improve - I need to think about ideas to code in less than 20 minutes.

public class Solution {
    public string NumberToWords(int num) {
        var chars = num.ToString().ToCharArray();
            var expr = new StringBuilder();
            var digits = new string[] {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" };
            var secondDigit = new string[] {"Zero","Ten","Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };
            var teens = new string[] { "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen","Nineteen" };


            var length = chars.Length;
        
            if(num == 0)
                return "Zero";
        
            var list = new List<char>(chars);

            if (length > 9)
            {
                var digit = list[0] - '0';
                if (digit >= 1)
                {
                    expr.Append(digits[digit] + " Billion ");
                }

                list.RemoveAt(0);
            }

            int repeat = 0;
            var zeroChecking = new int[3];
        
            while (repeat < 3)
            {
                if ((repeat == 0 && length > 8) ||
                   (repeat == 1 && length > 5) ||
                   (repeat == 2 && length > 2)
                   )
                {
                    var digit = list[0] - '0';
                    if (digit >= 1)
                    {
                        expr.Append(digits[digit] + " Hundred ");
                        zeroChecking[repeat] = 1; 
                    }

                    list.RemoveAt(0);
                }

                var isTeen = false;
                if ((repeat == 0 && length > 7) ||
                   (repeat == 1 && length > 4) ||
                   (repeat == 2 && length > 1))
                {
                    var digit = list[0] - '0';
                    if (digit > 1)
                    {
                        expr.Append(secondDigit[digit] + " ");
                        zeroChecking[repeat] = 1; 
                    }
                    else if (digit == 1)
                    {
                        // expr.Append(secondDigit[digit]);
                        isTeen = true;
                        zeroChecking[repeat] = 1; 
                    }

                    list.RemoveAt(0);
                }

                if ((repeat == 0 && length > 6) ||
                   (repeat == 1 && length > 3) ||
                   (repeat == 2 && length >= 0))
                {
                    var digit = list[0] - '0';
                    if(digit > 0)
                    {
                        zeroChecking[repeat] = 1;     
                    }
                    
                    if (isTeen)
                    {
                        expr.Append(teens[digit] + " ");
                    }
                    else if (digit > 0)
                    {
                        expr.Append(digits[digit] + " ");
                    }

                    list.RemoveAt(0);
                }

                if (repeat == 0 && length > 6)
                {
                    if(zeroChecking[repeat] > 0)
                        expr.Append("Million ");
                }
                else if (repeat == 1 && length > 3)
                {
                    if(zeroChecking[repeat] > 0)
                        expr.Append("Thousand ");
                }

                repeat++;
            }

            var trimed = expr.ToString().TrimEnd();
            return trimed;
        }
}

Leetcode discuss: 158. Read N Characters Given Read4 II - Call multiple times

 Here is the link. 

Troubleshooting - C# - "abcde", [1, 4], ["a", "bcde"] - Simulation

Jan. 5, 2020
Introduction
It is important for me to learn how to quickly fix a bug. I could not find the issue by reading my own code, so I wrote some debug code. This is easy for me to review later. If you have interest to learn how to debug the code, please continue; Or leave comment for tips.

Test case
"abcde", [1, 4], ["a", "bcde"] - My code could not work, the return is ["a", "bcd"], so I figured out that I should leave n unchanged, declare a copy variable. In order for me to find the issue, I created my own copy of Read4 API which only works for two calls.

My goal
It is so easy for me to write code using my own Read4 API and make one test case work first.
"abcde", [1, 4], ["a", "bcde"]
It is also important for me to be humble, when I design and add feature to read from stored buffer C# List, I should think about how to design a test case by myself. Do not leave online judge to show me failed test case.

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

namespace read4
{    

    public class Solution 
    {
        static void Main(string[] args)
        {
            var buf = new char[4];
            var result = Read(buf, 1);
            
            buf = new char[4];
            var result2 = Read(buf, 4);          
        }

        private static List<char> buffer = new List<char>();
        private static int times = 0; 

        private static int Read4(char[] buffer)
        {
           // buffer = new char[4];
           // buffer = "abc".ToCharArray(); 
            if (times == 0)
            {
                buffer[0] = 'a';
                buffer[1] = 'b';
                buffer[2] = 'c';
                buffer[3] = 'd';

                times++;
                return 4;
            }
            else
            {
                buffer[0] = 'e';
                return 1; 
            }            
        }
        /**
         * @param buf Destination buffer
         * @param n   Number of characters to read
         * @return    The number of actual characters read
         */
        public static int Read(char[] buf, int n)
        {
            // read 5, twice, first one 4, second one
            // read 5, twice, first one 4, second 4 - but only save 5        

            var index = 0;

            // read from buffer
            var copy = n; 
            while (buffer.Count > 0 && copy > 0)  // if should be a while statement
            {
                buf[index++] = buffer[0];
                buffer.RemoveAt(0);
                copy--;
            }

            var totalTimes = (copy + 3) / 4;

            for (int i = 0; i < totalTimes; i++)
            {
                var tmp = new char[4];
                var actual = Read4(tmp);

                for (int j = 0; j < actual; j++)
                {
                    if (index < n) //  n should not be changed
                    {
                        buf[index++] = tmp[j];
                    }
                    else
                    {
                        buffer.Add(tmp[j]);
                    }
                }

                if (actual != 4)
                {
                    break;
                }
            }

            return index;
        }
    }
}

Leetcode discuss: 158. Read N Characters Given Read4 II - Call multiple times

 Here is the link. 

First practice - C# - Failed - Test case

Dec. 31, 2020
Introduction
I spent over 30 minutes to work on the algorithm in my mock interview. I could not figure out how to solve failed test case in limited time constraint. I will follow up with ideas how to fix it later.

Failed test case
63/81
Input:
"abc"
[1,2,1]
Output:
["a","b","c"]
Expected:
["a","bc",""]

Follow up
Jan. 5, 2020

1. Trouble shooting, Read function, first if statement should be a while loop.
2. In Read function, do not change variable n's value, make a copy of n and work on while loop.
3. It is important to be patient, actually I wrote a simulation for me to debug the code. I learned a few things through this Facebook mock onsite interview algorithm.

/**
 * The Read4 API is defined in the parent class Reader4.
 *     int Read4(char[] buf4);
 */

public class Solution : Reader4 {
    private List<char> buffer = new List<char>(); 
    
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    public int Read(char[] buf, int n) {
        // read 5, twice, first one 4, second one
        // read 5, twice, first one 4, second 4 - but only save 5        
        
        var index = 0; 
        
        // read from buffer <- leave n unchange, declare a copy variable: copy = n; work on copy
        if(buffer.Count > 0 && n > 0) // <- this should be while statement - added on Jan. 5, 2020
        {
            buf[index++] = buffer[0];
            buffer.RemoveAt(0);
            n--; 
        }
        
        var totalTimes = (n + 3)/ 4; 
        
        for(int i = 0; i < totalTimes; i++)
        {
            var tmp = new char[4];
            var actual = Read4(tmp);            
           
            for(int j = 0; j < actual; j++)    
            {
                if(index < n)  // <- this requires that n should not be changed. Added on Jan. 5, 2020
                {
                    buf[index++] = tmp[j];    
                }
                else
                {
                    buffer.Add(tmp[j]);
                }
            }
            
            if(actual != 4)
            {
                break; 
            }            
        }
        
        return index; 
    }
}

Sven Carlin: 10 Things To Know Before Buying Undervalued Oil Stocks in 2020

 Here is the link. 

Oil stocks are down, but before investing in oil stocks or buying the cheap oil stocks with high dividend, there are 10 factors you should consider including: oil price analysis, oil production costs, oil stocks volatility, structural headwinds, growth in production, Saudi Aramco, Shell etc.

Leetcode discuss: 1305. All Elements in Two Binary Search Trees

 Here is the link. 

Jan. 6, 2020
It is my mock interview perform. My goal is to take some risk. It should not have TLE concern. What I did is to apply inorder traversal for two trees separately, and then call C# List.AddRange to merge two lists, and then call Sort API.

It is a good practice. It should take me less than 15 minutes.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
        var list = new List<int>();         
        traverseInOrder(root1, list);
        
        var list2 = new List<int>(); 
        traverseInOrder(root2, list2);
        
        list.AddRange(list2);
        list.Sort(); 
        
        return list; 
    }
    
    private void traverseInOrder(TreeNode root1, IList<int> list)
    {
        if(root1 == null)
            return; 
        
        traverseInOrder(root1.left, list); 
        
        list.Add(root1.val);
        
        traverseInOrder(root1.right, list);         
    }
}

Leetcode discuss: 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

 Here is the link. 

Second practice - C# - copy idea - Time complexity - Each row maximum cost - Sorting

January 5, 2020
Introduction
It is so quick to learn a new idea and code is so easy to write. I really enjoyed the learning.

Copy idea - C# - changes
I made a few changes to make it work and fit into my style.

It is localize optimization algorithms as well. Do not worry about kth element smallest for given number of columns. Focus on each row, keep kth small numbers of prefix sums.

First row, just start from left to right, and keep kth smallest number. It is smart and easy to do.
Next row, brute force all comibination of two rows, first row has at most kth numbers, second row has size of columns numbers. So combination is easy, k * columns variations.

The time complexity is upper bounded by sorting those k * columns numbers, O(k * columns * log(k * columns)).

Time complexity
O(rows * k * columns * log(k * columns))
Each row upper bound of time complexity is related to sorting algorithm.

My first one hour
I spent one hour in mock interview, but I could not figure out a working solution.

Here are lesson learned:

1. Work on time complexity analysis - brute force, how to lower the the time compleixty
2. Brute force, find all sequence in which one number is selected for each row, the combinations are columns^rows. It will time out.
3. Next, work on exactly how to get next smallest sum for sequence - it is too hard to search - beyond a hard level
4. Next, relax the condition, each row, find kth smallest numbers. Easy task;
5. Start from second row, consider sequence of two numbers, keep kth smallest sequence as well. Time complexity, sorting, total upper bound of number - k * columns.
6. What did I miss in mock interview? Will add later.
7. Take a row by row solution, work on one row at a time. Next work on combination of two rows, sum of two number sequence, find kth smallest one.

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

namespace _1439_kth_element_II
{
    class Program
    {
        static void Main(string[] args)
        {
            var mat = new int[2][];

            mat[0] = new int[] { 1, 3, 11 };
            mat[1] = new int[] { 2, 4, 6 };

            var result = KthSmallest(mat, 5);
            Debug.Assert(result == 7); 
        }

        /// <summary>
        /// study code and copy idea 
        /// https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/discuss/609961/C-Without-Priority-Queue
        /// </summary>
        /// <param name="mat"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int KthSmallest(int[][] mat, int k)
        {
            var rows = mat.Length; 
            var columns = mat[0].Length; 

            var currentSum = new List<int>();

            for (int i = 0; i < columns && i < k; i++)
            {
                currentSum.Add(mat[0][i]);
            }            

            // start from second row 
            for (int row = 1; row < rows; row++)
            {
                var nextSum = new List<int>();

                for (int col = 0; col < columns; col++)
                {
                    var current = mat[row][col];

                    foreach (var sum in currentSum)
                    {
                        nextSum.Add(sum + current);
                    }

                    nextSum.Sort(); 

                    // remove those beyond k 
                    while (nextSum.Count > k) 
                    {
                        nextSum.RemoveAt(nextSum.Count - 1);
                    }
                }

                currentSum = nextSum;
            }

            currentSum.Sort();

            return currentSum[k - 1];
        }
    }
}