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);
 */

Mock interview: Clone graph

Here is the link.



Continue

Leetcode phone screen mock interview: Weekend marathon

I like to push myself hard to practice leetcode phone screen mock interview algorithms nonstop whole weekend.

This is the first time I do that. I like to move fast and prepare for Facebook phone screen in less than one week.

Leetcode discuss: 463. Island Perimeter

July 14, 2020

Here is the link.

C# using DFS and two hashset to remove duplicate edge count

July 14, 2020

463. Island Perimeter

Introduction

It is my first algorithm in Leetcode mock interivew phone screen. I spent over 40 minutes to write a solution, and then passed online judge.

Design issue
The challenge is to design unique key for each edge, in order for me to remove duplicate ones, I need to specify a key using integer to represent edges of rectangle.

The idea is to use left start point for horizontal edge, and top point for vertical edge.

Also map horizontal edges to integer values smaller than 100 * 200 + 100. Map vertical edges to integer values bigger than all horizontal edges, so there is no overlap, zero possibility to mix horizontal edge with vertical edge.

If the above issues are resolved, all others are standard BFS/ DFS solution with base case, range check, visited mark etc.

public class Solution {
    public int IslandPerimeter(int[][] grid) {
        // apply DFS to visit all connected nodes
        // use hashset<int> to add all unique edges first
        // use hashset<int> to record all duplicate edge next
        // all edges will have unique id - 
        // horizontal - row, col - start point
        // vertical - row, col - up point
        // 100 - map row * 100 + col -> unique value 
        // return difference between two hashset's count value - unique one and duplicate ones
        if(grid == null || grid[0] == null || grid[0].Length == 0)
        {
            return 0; 
        }
        
        var rows = grid.Length; 
        var columns = grid[0].Length; 
        
        var hashSet = new HashSet<int>(); 
        var duplicateSet = new HashSet<int>(); 
        
        for(int row = 0; row < rows; row++)
        {
            for(int col = 0; col < columns; col++)
            {
                var current = grid[row][col];
                if(current != 1)
                {
                    continue; 
                }                
                
                runDFSSearch(grid, hashSet, duplicateSet, row, col);
                break;
            }
        }
        
        return hashSet.Count - duplicateSet.Count; 
    }
    
    /// Run BFS algorithm
    private void runDFSSearch(int[][] grid, HashSet<int> set, HashSet<int> duplicate, int row, int col)
    {
        var rows = grid.Length; 
        var columns = grid[0].Length; 
        
        if(row < 0 || row >= rows || col < 0 || col >= columns || grid[row][col] != 1)
        {
            return; 
        }
        
        // starting from top-left corner, horizontal first, vertical next
        // horizontal left->right
        // vertical top->down
        var keyEdges = new int[]{
            getHorizontalNumber(row, col), 
            getHorizontalNumber(row + 1, col), 
            getVerticalNumber(row, col),             
            getVerticalNumber(row, col + 1)};
        
        foreach(var item in keyEdges)
        {
            if(set.Contains(item))
            {
                duplicate.Add(item);
            }
            
            set.Add(item); 
        }
        
        // mark visited
        grid[row][col] = 2;  
        
        runDFSSearch(grid, set, duplicate, row + 1, col); 
        runDFSSearch(grid, set, duplicate, row - 1, col); 
        runDFSSearch(grid, set, duplicate, row, col - 1); 
        runDFSSearch(grid, set, duplicate, row, col + 1);         
    }
    
    // Do not overlap vertical number
    // all < 100 * 200 + 100
    private int getHorizontalNumber(int row, int col)
    {
        return row * 200 + col; 
    }
    
    // Do not overlap horizontal number
    // all > maximum of horizontal number < 200 * 100 + 20000
    // 
    private int getVerticalNumber(int row, int col)
    {
        return 200 * 100 + 20000 + (row * 200 + col);
    }
}