Leetcode discuss: 314. Binary Tree Vertical Order Traversal

 March 8, 2022

Here is the link. 

C# | Preorder traversal | Record total count, horizontal, level in the tree

Marhc 6, 2022
Introduction
It is easy for me to figure out how to traverse the tree, and also record horizontal position for each node, and preorder traversal should maintain the order of same row nodes in left to right order, but the code failed the test case 201/214. It cannot maintain the order of nodes in terms of level in the tree.

Test case 201/214 | First submission | Change design to add more tracking
201 / 214 test cases passed.
Input:
[3,9,8,4,0,1,7,null,null,null,2,5]
Output:
[[4],[9,5],[3,0,1],[2,8],[7]]
Expected:
[[4],[9,5],[3,0,1],[8,2],[7]]
I learned from the above failed test case. I need to maintain the order in the level of tree.
Tree node with value 2 and 8, node with value 8 is root node's right child, level is 1; whereas node with value 2 is the root's left.right.right, level is 3.

I decided to change the design, and record tree node's level in the tree, and also count of nodes in the tree. The comparison of tree node is up to 3 dimensions, Tuple<int, int, int>. Since second integer is the count of nodes which is unique, there will be no comparison in the third item - value of tree node.

The following C# code passes online judge.

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

namespace _314_Binary_tree_veritcal_order
{
    class Program
    {
        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;
          }
        }

        static void Main(string[] args)
        {
            var node3 = new TreeNode(3);
            node3.left = new TreeNode(9);
            node3.right = new TreeNode(20);
            node3.right.left = new TreeNode(15);
            node3.right.right = new TreeNode(7);

            var test = new Program();
            var result = test.VerticalOrder(node3);
            Debug.Assert(string.Join(",", result[0]).CompareTo("9") == 0);
            Debug.Assert(string.Join(",", result[1]).CompareTo("3,15") == 0);            
        }

        public IList<IList<int>> VerticalOrder(TreeNode root)
        {
            if (root == null)
                return new List<IList<int>>(); 

            var map = new Dictionary<int, List<Tuple<int, int, int>>>();

            var total = 0; 
            runPreOrderTraversal(root, map, ref total, 0, 0);

            var keys = map.Keys.ToList();
            var min = keys.Min();
            var max = keys.Max();

            var result = new List<IList<int>>(); 
            for (int i = min; i <= max; i++)
            {
                var items = map[i];
                items.Sort();

                var list = new List<int>();
                foreach (var item in items)
                {
                    list.Add(item.Item3);
                }

                result.Add(list);
            }

            return result; 
        }

        /// <summary>
        /// Argument:
        /// Just make sure that order is top to down, left to right; so preorder traversal should work. 
        /// Fail test case 201/214
        /// Need to sort nodes by level in the tree as well
        /// </summary>
        /// <param name="root"></param>
        /// <param name="map"></param>
        /// <param name="hIndex"></param>
        private void runPreOrderTraversal(TreeNode root, Dictionary<int, List<Tuple<int, int, int>>> map, ref int total, int hIndex, int level)
        {
            if (root == null)
                return;

            if (!map.ContainsKey(hIndex))
            {
                map.Add(hIndex, new List<Tuple<int, int, int>>());
            }

            map[hIndex].Add(new Tuple<int, int, int>(level, total, root.val));
            total++;

            runPreOrderTraversal(root.left, map,  ref total, hIndex - 1, level + 1);
            runPreOrderTraversal(root.right, map, ref total, hIndex + 1, level + 1); 
        }
    }
}

1650. Lowest Common Ancestor of a Binary Tree III

 March 8, 2022

Here is the link. 

C# | Space complexity O(1)

March 6, 2022
Introduction
I chose to practice mock interview on interviewing dot io, and then the interviewer asked me to work on this algorithm; and also asked me to come out the algorithm using O(1) space instead of O(h) space.

A simple trick | p -> p's parent -> ... -> root -> q -> q's parent -> ...-> LCA
It is kind of tricky to prove that a two linked list will end up a LCA node, lowest common ancestor. I think that the difference between p and q in terms of level in the tree is fixed, so it is a working idea to travel from p to it's parent node until the root node and then switch to q node and travel to LCA.

Node p to root node - denoted as pToRoot
Node q to root node - denoted as qToRoot
LCA to root node - denoted as LCAToRoot
So the distance p to root -> q ->...->LCA should be pToRoot + qToRoot - LCAToRoot
Likewise, q to root -> p ->...->LCA should also be pToRoot + qToRoot - LCAToRoot.
And also LCAToRoot <= Math.Min(pToRoot, qToRoot), so (pToRoot + qToRoot - LCAToRoot) >= 0.

Two linked lists:
p -> p's parent -> ... -> root -> q -> q's parent -> ...-> LCA
same applies to node q

The following C# code passes online judge

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

namespace Cons1650_lowest_common_ancestor
{
    class Program
    {
        public class Node
        {
            public int val;
            public Node left;
            public Node right;
            public Node parent;

            public Node(int value)
            {
                val = value;
            }
        }

        static void Main(string[] args)
        {
            var node3 = new Node(3);
            node3.left = new Node(5);
            node3.left.left = new Node(6);
            node3.left.right = new Node(2);
            node3.left.right.left = new Node(7);
            node3.left.right.right = new Node(4);
            node3.right = new Node(1);
            node3.right.left = new Node(0);
            node3.right.right = new Node(8);

            node3.left.parent = node3;
            node3.right.parent = node3;
            node3.left.left.parent = node3.left;
            node3.left.right.parent = node3.left;
            node3.left.right.left.parent = node3.left.right;
            node3.left.right.right.parent = node3.left.right;

            var test = new Program();
            var result = test.LowestCommonAncestor(node3.left, node3.right);
            Debug.Assert(result.val == 3);
        }

        public Node LowestCommonAncestor(Node p, Node q)
        {
            if (p == null || q == null)
                return null;

            var start = p;
            var start2 = q;
            while (start != start2)
            {
                if (start.parent == null)
                {
                    start = q;
                }
                else 
                    start = start.parent;

                if (start2.parent == null)
                    start2 = p;
                else 
                    start2 = start2.parent;
            }

            return start;
        }
    }
}

Leetcode discuss: 408. Valid Word Abbreviation

 March 8, 2022

Here is the link. 

C# | learn from failed test cases

March 6, 2022
Introduction
It is an easy algorithm, but it is so challenge since I failed so many test cases, so I continuously modified the logic in order to pass all test cases. I have two weeks to practice Leetcode in order to prepare Meta phone screen, I just choose to solve as many algorithms as I can and warmup my coding skills.

Learn from failed test cases | Write down and review later
test case 166/322
Input:
"internationalization"
"i5a11o1"
Output:
false
Expected:
true
Fix: Do not mix c with 'c', c is in the range from 0 to 9. '9' - c >= 0

11 / 322 test cases passed.
Input:
"a"
"01"
Output:
true
Expected:
false
Fix: Add edge case to check number should not start from 0 digit.

12 / 322 test cases passed.
Runtime Error Message:
Unhandled exception. System.IndexOutOfRangeException: Index was outside the bounds of the array.

Last executed input:
"hi"
"2i"
Fix: Add index-out-of-range check for word array, wIndex - check in the range

314 / 322 test cases passed.
Input:
"hi"
"1"
Output:
true
Expected:
false
Fix: make sure that return statement should check that search in word is completed

return wIndex == length;

The following C# code passes online judge.

public class Solution {
    public bool ValidWordAbbreviation(string word, string abbr) {
        if (word == null || word.Length == 0 || abbr == null || abbr.Length == 0)
                return false;

            var length = word.Length;
            var aLength = abbr.Length;
            var wIndex = 0;
            var index = 0;
            var digits = 0;
            while (index < aLength)
            {
                var c = abbr[index];
                if ((c - '0') >= 0 && ('9' - c) >= 0)
                {
                    var digit = c - '0';
                    // test case: "a", "01"
                    if(digit == 0 && (index == 0 || abbr[index - 1] >='a') && (index + 1 < aLength && (abbr[index + 1] - '0' >=0)))
                    {
                        return false;
                    }
                                                                               
                    digits = digits * 10 + (c - '0');

                    if (index == aLength - 1 || abbr[index + 1] >= 'a')
                    {
                        if (wIndex + digits > length)
                            return false;

                        wIndex += digits;
                    }
                }
                else
                {
                    digits = 0;
                    if (wIndex >= length || word[wIndex++] != abbr[index])
                    {
                        return false;
                    }                    
                }

                index++;
            }

            return wIndex == length;
    }
}

Leetcode discuss: 670. Maximum Swap

March 8, 2022

Here is the link. 

C# | Sort a char array | case study: 1993

March 7, 2022
Introduction
The idea is to sort the integer as a char array, and then compare leftmost digit to largest digit, and then find first one unequal.

Case study: 1993 | Answer should be 9913, not 9193
I should choose to compare from rightmost digit first to find the swap digit based on failed test case: 9913.

The following C# code passes online judge.

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

namespace _670_maximum_swap
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = MaximumSwap(1993);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public static int MaximumSwap(int num) {
            var unsorted = num.ToString().ToCharArray();
            var length = unsorted.Length;
            var sorted = new char[length];
            Array.Copy(unsorted, sorted, length);

            Array.Sort(sorted);            

            for (int i = 0; i < length; i++)
            {
                if (unsorted[i] - '0' < sorted[length - 1 - i] - '0')
                {
                    var digit1 = unsorted[i] - '0';
                    var digit2 = sorted[length - 1 - i] - '0';

                    // swap those two digits
                    for (int j = length - 1; j >= i + 1; j--)
                    {
                        if (unsorted[j] - '0' == digit2)
                        {
                            unsorted[i] = unsorted[j];
                            unsorted[j] = (char)(digit1 + '0');

                            return Convert.ToInt32(new string(unsorted));
                        }                        
                    }
                }                
            }

            return num;
        }
    }
}

Leetcode discuss: 498. Diagonal Traverse

 March 8, 2022

Here is the link. 

C# | Automatically direction change

March 7, 2022
Introduction
It is challenge for me to write a working solution to automate direction change using direction array. I came cross a few failed test cases, so I made a few changes on my code.

The following C# code passes online judge.

public class Solution {
    public int[] FindDiagonalOrder(int[][] mat) {
         if (mat == null || mat.Length == 0 || mat[0].Length == 0)
                return new int[0];
            
            var rows = mat.Length;
            var columns = mat[0].Length;            

            // up, -1, down, 1
            var directionRow = new int[] { -1, 1 };
            var directionCol = new int[] { 1, -1 };            

            var startRow = 0;
            var startCol = 0;
            int index = 0;
            int direction = 0;
            var diagonal = new int[rows * columns];

            while (index < rows * columns)
            {
                diagonal[index] = mat[startRow][startCol];
                index++;

                var nextRow = startRow + directionRow[direction];
                var nextCol = startCol + directionCol[direction];

                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < columns)
                {
                    startRow = nextRow;
                    startCol = nextCol;                    
                }
                else
                {   // go up 
                    if (direction == 0)
                    {
                        if (startCol < columns - 1)
                            startCol += 1; // increment column value
                        else
                            startRow += 1;

                    }
                    else
                    {   // go down
                        if (startRow < rows - 1)
                            startRow += 1;
                        else
                            startCol += 1;
                    }

                    direction = (direction + 1) % 2;                    
                }
            }

            return diagonal;
    }
}

Leetcode discuss: 523. Continuous Subarray Sum

 March 8, 2022

Here is the link.

C# | Learn from failed test cases

March 7, 2022
Introduction
It is such great learning experience to learn those failed test cases. After a few iterations, I figured out working solution

learn from failed test cases

1. {23, 2, 6, 4, 7], k = 13
   a hashset should save residue, not k - residue
2. [23,2,4,6,6], k = 7, should consider residue == 0 case
3. [1,0], k = 2, true, expected: false - at least two numbers, so [0] subarray only contains one number.

The following C# code passes online judge.

public class Solution {
    public bool CheckSubarraySum(int[] nums, int k) {
        if (nums == null || nums.Length < 2 || k <= 0)
                return false;

            var prefixSum = 0;
            var length = nums.Length;
            var hashSet = new HashSet<int>();
            
            // {1, 0}, k = 2
            var saved = new int[length];

            for (int i = 0; i < length; i++)
            {
                prefixSum += nums[i];
                var residue = prefixSum % k;

                if (i > 1)
                {
                    hashSet.Add(saved[i - 2]);
                }

                if ((i>= 1 && residue == 0) || hashSet.Contains(residue))
                {
                    return true;
                }
                else
                {
                    saved[i] = residue;                    
                }               
            }

            return false;
    }
}

Leetcode discuss: 162. Find Peak Element

March 8, 2022

Here is the link. 

C# | Binary search algorithm | Learn from my failure

March 7, 2022
Introduction
I spent 20 minutes to try to write my own code using binary search. I could not simplify and make it work. I like to look into this issue quickly and write down some notes.

Binary search
How to design a binary search algorithm to find one of peeks in less than 10 minutes?
Here are facts or tips to review:

1. If there is one element in the binary search, which should be a peek;
2. Minimum case has two elements. Choose middle to be a smaller one if there only is two numbers;
3. Compare middle and middle + 1;
4. Do not compare middle with middle - 1 if left exists; It should be covered in step 3.
5. Do not consider if the middle is the first position of the array, which should be covered in step 3 as well.
6. Do not consider if the middle is the last position of the array, since middle is the smaller if there are only two numbers. Middle cannot be the last position in the array.
7. Always consider middle, not start, not end;
8. Stay focus on two elements and comparison of two integers.
9. It is defined in the problem that any two values in the array next to each other should have different value.

Follow up
March 8, 2022
Reasons for failure
I do think that taking risk and avoid redundant work is so challenge in terms of find a working and simple solution using binary search. I did spend over 20 minutes to write before I could come out a simple solution to compare two numbers, and also limit to only one comparison.

My ideas were so complex, I tried to discuss middle value with right side and also left side, edge cases like two nodes, three nodes etc.

This practice allows me to find my weakness in my analysis. I just love this algorithm.

The following code passes online judge.

public class Solution {
    public int FindPeakElement(int[] nums) {
        var length = nums.Length;
            if (length == 1)
                return 0;

            var start = 0;
            var end = length - 1;            

            while (start < end)
            {
                var middle = start + (end - start) / 2;  // middle is close to start                    

                // argue that middle + 1 is in the range
                if (nums[middle] < nums[middle + 1]) // middle is not a peak
                {
                    start = middle + 1;
                }
                else
                {
                    end = middle; // middle maybe is a peak
                }
            }

            return start;
    }
}

Google's IWD 2022 Global Summit: What is impossible?

 What is impossible?

12:35 PM - 12:45 PM

Aubrie LeeIgustiaju Tjitrawati (Tjitra) Esfahani

Hear from brand manager, Aubrie Lee as she discusses her community-driven mindset and her mission to make product design and technologies more accessible to disabled people. 

Tune in to the beginning of Aubrie's talk to learn more about the speech recognition tool, Project Relate. 

My notes: Jigsaw - harassment, research efforts, online violence

Googlers behind Jigsaw: building a safer digital world

 March 8, 2022

Product manager, 10 years, she shares the following. My notes are not so clean, 

1. Active Zone minutes
2. High & low ...

24/7 heart rate - technology is helping to power better understanding of your health

Fitbit sensors: PPG

PPG sensor: Blood absorbs green light - algorithm - light detector - measure heart beat - helping user understand the health 

Powered by sensor - Active Zone minutes 

What is impossible?

12:35 PM - 12:45 PM

Aubrie LeeIgustiaju Tjitrawati (Tjitra) Esfahani

Fireside chat with Adrienne Lofton and Nuha Elkhiamy, in conversation with Cinthia Lopez

March 8, 2022

1. When did you know that it is time to make changes? 
2. You can take the call, and make new relationships, not career decision. Start to think about how I admire technologies. 23-24 years in to make a jump, the skills can be adapted, imposter syndrome. The first response is to feel comfortable. Start to look at the mirror, how much I am learning, how much I am teaching. 
3. Consumer market perspective, Lorraine leads market organization - need sponsor, human ...
4. the way she respects the team ...

PIE - Performance, I - Image, E - exposure 

vehicle of communication, blog, high profile presentation, every one knows how remarkable you are. Naturally humble, powerful and authenticate way - check into ...

Think about industry - tech, different industry 

1. Comfortable, and get bored, so it is time to investigate what is true. What area you like to look into, how to get there?
2. Wealth experience in your current field - role you are 
3. Be where you are, there are transfer skills - how to talk inside the industry 
4. Difference between mentorship and sponsorship 
5. Friends - inside this industry - get true to get there 
6. Meet right people - recognize things does not happen over a night
7. The world is a marathon, not a sprint - what you are in right now. 

What is best career advice you have?

Do not be afraid to be a beginner. 

Start a new role. First few months you will learn. Do not shy away from learning. 

Know yourself 

build my teams, high performance team, skillsets - build people around me

Add value - do not lose your authentication

Chart out your goals - five year increment - 

Be curious, ask questions, day one today 

urgency - let it play out - 

five things to offer 

AAL stock: March 8 rebound

 March 8, 2022

I got up early and prepared for rebound of AAL stock. 

OXY stock: Warren Buffet 5 billion purchase in 5 days

巴菲特谈增持西方石油：5天投45亿 能买多少买多少

 

伯克希尔·哈撒韦公司（Berkshire Hathaway）董事长沃伦·巴菲特（Warren Edward Buffett）在3月7日的一次采访中披露了他最近大手笔增持西方石油公司（Occidental Petroleum）的经过。

据中国媒体新浪财经3月8日报道，这位著名投资者在阅读了2月25日西方石油公司第四季度财报电话会议的记录后，作出了增持该公司股份的决定。

巴菲特称他在上周（2月28日当周）五个交易日内豪掷45亿美元，买入了9,120万股，按当前股价计算价值超过了50亿美元。

巴菲特说：“我们从周一开始买进，能买多少就买多少。”

根据巴菲特的言论和美国证券交易委员会（SEC）收到的文件，伯克希尔到上周二（3月1日）收盘时买入了2,980万股西方石油股票，然后在接下来的三天里又买入了6,140万股。

Leetcode algorithms: It is tough to make things work!

March 7, 2022

Introduction

It is tough experience to work on leetcode algorithms. There are so many issues once I like to solve another 50 algorithms in next two weeks. 

Mental toughness | Work hard

It is not easy for me to handle the stress. There is always good articles and videos out there related to Meta phone interview or onsite interview algorithms. But nothing can compare my own experience, struggle to solve one by one algorithm, deal with failed test cases, and then figure out how to do better, think better, and also stay focus on practice. 

Oil stock: Nov. 2021 my purchase of 5000 shares of GTE

      Porfolio Name                                                                                     Market value Day chg Day Chg% Total Chg total chg%