637. Average of Levels in Binary Tree

Here is my discussion post.

The algorithm can be solved using BFS algorithm, level by level can be implemented to track nodes in the queue first; same level nodes will be visited one by one using a while loop by tracking count of nodes.

Here are highlights:

1. Learn the technique to apply BFS using Queue, and track level by level by tracking nodes in the queue;
2. For each level, calculate sum of each node's value; data type of sum should be long not int, and then average value will be double, so it is better to declare as double type;
3. I completed the solution using 13 minutes.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<double> AverageOfLevels(TreeNode root)
        {
            var averages = new List<double>();

            if (root == null)
                return averages;

            var queue = new Queue<TreeNode>();
            queue.Enqueue(root); 

            // push into queue by level 
            while(queue.Count > 0)
            {
                var count = queue.Count;
                double sum = 0; 
                for(int i = 0; i < count; i++)
                {
                    var current = queue.Dequeue();
                    sum += current.val;

                    if (current.left != null)
                        queue.Enqueue(current.left);

                    if (current.right != null)
                        queue.Enqueue(current.right); 
                }

                averages.Add(sum/count);
            }

            return averages;
        }
}

966. Vowel Spellchecker

Here is my discussion post.

It is the second algorithm in one of mock interviews on Leetcode.com. I worked on the solution and it took me over one hour to fix it. Because I ran into timeout issue on test case 48/53, I had to review my code to preprocess a few hashSet and hashMap to expedite the lookup.

Here are highlights:

1. First, put all words in wordList into a hashSet, so it can use O(1) time to look up; if it is found, then no spell check need;
2. Next, preprocess a hashSet with lower case word, and also a hashmap to map the lower case word to its original words, for example, key string "kite", value strings {"KiTe","kite"}.
3. Thirdly, preprocess a hashSet with vowel char replaced, for example, "kite" has two vowel char 'i' and 'e' which can be replaced using '*', so "k*t*" can be a key string to represent all vowel error words.
4. Will continue to add more detail. Stay tuned.

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

namespace spellCheckerProject
{
    class Program
    {
        static void Main(string[] args)
        {
            var wordList = new string[] { "KiTe", "kite", "hare", "Hare" };
            var queries = new string[] { "kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto" };

            var result = Spellchecker(wordList, queries);
        }

        /// <summary>
        /// spellchecker 
        /// Oct. 11, 2019
        /// Timeout bug - need to continue to work on
        /// </summary>
        /// <param name="wordlist"></param>
        /// <param name="queries"></param>
        /// <returns></returns>
        public static string[] Spellchecker(string[] wordlist, string[] queries)
        {
            var lengthWord = wordlist.Length;
            var lengthQuery = queries.Length;

            var hashset = new HashSet<string>(wordlist);

            var lowerHashset = new HashSet<string>();
            var map = new Dictionary<string, List<string>>();
            foreach (var item in wordlist)
            {
                var key = item.ToLower(); 
                lowerHashset.Add(key);

                if (!map.ContainsKey(key))
                {
                    map.Add(key, new List<string>());
                }

                map[key].Add(item); 
            }

            var vowelSet = new HashSet<string>();
            var vowels = new HashSet<char>("aeiou".ToCharArray());
            var vowelMap = new Dictionary<string, string>(); 
            
            foreach (var item in wordlist)
            {               
                var replaced  = vowelReplaced(item); 
                vowelSet.Add(replaced); 
                if(!vowelMap.ContainsKey(replaced))
                {
                    vowelMap.Add(replaced, item);
                }
            }

            var matchingWords = new string[lengthQuery];

            for (int i = 0; i < lengthQuery; i++)
            {
                var current = queries[i];
                var currentLower = current.ToLower();

                if (hashset.Contains(current))
                {
                    matchingWords[i] = current;
                    continue;
                }

                // Capitalization
                var capitalization = false;
                if (lowerHashset.Contains(currentLower))
                {                    
                    matchingWords[i] = map[currentLower][0];
                    capitalization = true;
                }

                if (capitalization)
                {
                    continue;
                }

                // Vowel errors
                var vowelErrors = false;
                var replacedKey = vowelReplaced(currentLower);
                if(vowelSet.Contains(replacedKey))
                {                    
                    matchingWords[i] = vowelMap[replacedKey];
                    vowelErrors = true; 
                }

                // edge case - no matching
                if (!vowelErrors)
                {
                    matchingWords[i] = "";
                }
            }

            return matchingWords;
        }

        /// <summary>
        /// convert to lower case, and then replace vowel char
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        private static string vowelReplaced(string item)
        {            
            var vowels = new HashSet<char>("aeiou".ToCharArray());
            var array = item.ToLower().ToCharArray();
            for (int i = 0; i < array.Length; i++)
            {
                var vowelCheck = array[i];
                if (vowels.Contains(vowelCheck))
                {
                    array[i] = '*';
                }
            }

            return new string(array);
        }

        private static bool isMatchingVowelError(string matching, string source)
        {
            if (matching.Length != source.Length)
                return false;

            var vowels = new HashSet<char>("aeiou".ToCharArray());
            for (int i = 0; i < matching.Length; i++)
            {
                var current = matching[i];
                var sourceChar = source[i];

                if (vowels.Contains(current) != vowels.Contains(sourceChar))
                {
                    return false;
                }

                if (!vowels.Contains(current) && current != sourceChar)
                {
                    return false;
                }
            }

            return true;
        }
    }
}

48. Rotate Image

Here is my second practice in 2017.

I will write down my understanding, and highlight my solution in short future. Stay tuned.

public class Solution {
    public void Rotate(int[,] matrix) {
        int rows = matrix.GetLength(0); 
            int cols = matrix.GetLength(1); 
            
            int index = 0;
            while (2 * index < rows )
            {
                reverseRows(index, rows - 1 - index, matrix);
                index++; 
            }

            for (int row = 0; row < rows; ++row) 
            {
                for (int col = row + 1; col < cols; ++col)
                {
                    swap(row, col, matrix);
                }
            }
    }
    
     private  void reverseRows(int row1, int row2, int[,] matrix)
        {
            int cols = matrix.GetLength(1);
            for (int col = 0; col < cols; col++)
            {
                int tmp = matrix[row1, col];
                matrix[row1, col] = matrix[row2, col];
                matrix[row2, col] = tmp; 
            }
        }

        private  void swap(int row, int col, int[,] matrix)
        {
            int tmp = matrix[row, col];
            matrix[row, col] = matrix[col, row];
            matrix[col, row] = tmp; 
        }
}

48. Rotate Image

Here is my post.

Oct. 10, 2019

I came cross this algorithm when I reviewed one of Microsoft onsite interview post. I found out that I wrote two solution back in 2017, so I like to review the solution I wrote.

Stay tuned. I will add some highlights.

public class Solution {
    public void Rotate(int[,] matrix) {
         if (matrix == null || matrix.GetLength(0) == 0 || matrix.GetLength(1) == 0)
            {
                return;
            }

            int rows = matrix.GetLength(0);
            int cols = rows;
            var rotate90 = new int[rows, cols];

            int startRow = 0;
            int startCol = 0;
            int lastRow = rows - 1;
            int lastCol = cols - 1;

            while (startRow < rows && startCol < lastCol)
            {
                // put the number in the one dimension array
                int width = lastRow - startRow + 1;
                int circle = 4 * (width - 1);
                var numbers = new int[circle];
                int index = 0;

                // top row
                for (int col = startCol; col <= lastCol; col++)
                {
                    numbers[index++] = matrix[startRow, col];
                }

                // right col 
                for (int row = startRow + 1; row <= lastRow; row++)
                {
                    numbers[index++] = matrix[row, lastCol];
                }

                // bottom row 
                for (int col = lastCol - 1; col >= startCol; col--)
                {
                    numbers[index++] = matrix[lastRow, col];
                }

                // left row 
                for (int row = lastRow - 1; row > startRow; row--)
                {
                    numbers[index++] = matrix[row, startCol];
                }

                // -------------
                // Need to put numbers back to matrix                

                // right col
                int start = 0;
                for (int row = startRow; row <= lastRow; row++)
                {
                    matrix[row, lastCol] = numbers[start++];
                }

                // bottom row 
                for (int col = lastCol - 1; col >= startCol; col--)
                {
                    matrix[lastRow, col] = numbers[start++];
                }

                // left col 
                for (int row = lastRow - 1; row >= startRow; row--)
                {
                    matrix[row, startCol] = numbers[start++];
                }

                // top row 
                for (int col = startCol + 1; col < lastCol; col++)
                {
                    matrix[startRow, col] = numbers[start++];  
                }

                startRow++;
                startCol++;
                lastRow--;
                lastCol--; 
            }
    }
}

Case study: Amazon offer package

The link is here
Last Edit: August 23, 2019 10:41 AM
Education: BS In CS
Years of Experience: 0
Prior Experience: 0
For fresh grad, any related Internship/coop experience? 2 month internship experience at Small Govt Contracting Company
Date of the Offer: August 19th 2019
Company: Amazon
Title/Level: SDE1
Location: Seattle
Salary: 108K
Relocation/Signing Bonus: 7K(Relocation) +24K(1st Year) + 20K(2nd Year)
Stock bonus: 70RSU vesting - 5/15/20 (20 every 6 months until fully vested)
Total comp (Salary + Bonus + Stock): ~ 150k
Benefits: Standard

Amazon
Here is the link.
3 rounds total

8 YOE totaly, 6 years in a small company, 2 years in a medium size company.
base 155,000
sign on 79,000 + 60,000
stock 89
on avg about 230k TC

Microsoft
Onphone + Onsite
Onsite has 4 rounds, 45 minutes each.
Only 190k TC, forgot the detail numbers. Decided to go to Amazon.

Microsoft Stack Ranking

Here is the link.

Pioneered by Jack Welch at General Electric in the 1990s and sometimes known as “stack ranking,” this method is fairly common in Silicon Valley and was most notoriously used by Microsoft until the company got rid of it in 2013 after widespread employee complaints.

Stack ranking - 30 minutes study

Stack ranking 

 “员工分级评鉴制度”(stack ranking)，在上世纪90年代由世界级管理大师杰克·韦尔奇 (Jack Welch) 发明，通过他的公司通用电气，以及包括 Facebook、微软等在内的美国科技公司发扬光大。

在业绩考核时，工程师们需要在系统里撰写两封信，分别评价自己和经理的表现，并寻求三五同事也为自己评价；紧接着，经理会阅读这些信件，按照工程师在过去六个月内所完成或未能完成的每一项工作，其所造成的影响（Impact），进行逐一量化分级。

最顶级的一级是“重新定义” (Redefine) ，但多位Facebook员工向硅星人透露这个比例能有2%就很不错了；之后则是“极大超过预期”(Greatly exceeds expectations)、“超过预期”(Exceeds)、“完全达到”(Meets all) 等等评价，比例越来越大。

这会导致一个不可避免的情况：在一个组里，尽管大家的 Impact 可能接近，也都很不错，由于比例相对稳定，总会有人不得不被放置到更差的区间里。

而且，尽管考核分级会经过不同级别的人校准，但工程师们的直属Manager (经理）在这个考核体系里有相当大的裁量权。

According to two former executives, the grade breakdown is approximately as follows:

• “Redefine,” the highest grade, is given to fewer than 5 percent of employees
• “Greatly exceeds expectations”: 10 percent
• “Exceeds”: 35 percent
• “Meets all”: 35 to 40 percent
• “Meets most,” a low grade that puts future employment at risk, goes to most of the remaining 10 to 15 percent
• “Meets some” grades are extremely rare and are seen as an indication that you’re probably getting fired, according to multiple employees.
• “Does not meet” are exceptionally rare, as most employees are fired before they get to that level.

Case study: Facebook E4 package in 2019

Oct. 10, 2019

Introduction

It is my personal finance research. I like to be a millionaire before I turn 60 years old. It is hard for me to get the offer from Facebook, but I made my first onsite in 2019. Now I am trying to work on investment, I am just a learner, try to adapt my research on algorithm and data structure to personal finance. One thing is to study Facebook E4 package in 2019. 

Case study

I think that the package should be real number since the engineer wrote the post and also works for Google. 

Facebook E4
Here is the link.
January 16, 2019 1:15 PM
Education: MS in Computer Science
Years of Experience: 4
Prior Experience: Bloomberg 2 yrs, Apple 2 yrs
Company: Facebook
Title/Level: Software Engineer
Location: New York
Salary: $155,000
Relocation: n/a
Signing Bonus: $75,000
Stock bonus: $300k stock grant vested over 4 years
Bonus: Performance-based bonus up to 20% of salary every year (10% target)
Total comp (Salary + Bonus + Stock): ~$320.5K first year
Benefits: 21 paid vacation days, 401k, health and welfare, free food
Other details: Negotiated once, just increased signining by $25,000
Experience: Offers from Google, Facebook is here.

Offers from Google/Facebook/Apple/Uber/Snap/etc.. after numerous failures

Oct. 10, 2019

Introduction

It is so challenging for me to advance myself in Leetcode weekly contest. If I can push myself to top ranking 5000, then I think that it is easy for me to pass any algorithm and data structure coding interview.

Role model

I came cross this article since I like to study the offer package from Facebook.

Here is the article.

Leetcode contest

I moved from Manhattan to Silicon Valley, and I was so bored! I actually started to solve leetcode problems for fun and started participating leetcode contest whenever I could on Saturday night. The contest time was not the best, but I enjoyed whenever I could participate, and this really improved and prepared me well for the upcoming interviews!

Doing lots of leetcode practice got me prepared to solve algorithm question very quickly and efficiently, and the interview seemed easier than doing the contest. 

Taking more risk

Oct. 9, 2019

Introduction

I like to write a blog about taking more risk. How to advance myself to be a rich person, and a millionaire if possible.

How to set up a goal and motivate myself? 

It is the first time I learn that I should work on my goal setting. Even though I may find that it is so hard for me to achieve the goal to be a millionaire, I may learn a few things through the research. I will open a new world for me.

It is so important for me to reach out and fully enjoy my career and my life. What else should I do in terms of building wealth, enjoying life and my career.

I need to work on a few things in order to build wealth, reach a million dollar wealth goal. My idea is to fully develop myself as a career woman, personal investor of USA economy.

Right now, everything looks tough from my side. Three things surprised me, this May I passed Microsoft online code screen, and then this June I passed Amazon online code screen, phone screen; and then I passed Facebook phone screen in July as well.

Business world is totally different, and it is so exciting to meet people in Amazon and Facebook through onsite interview.

I did feel the excitement, I should work hard to advance myself in terms of problem solver. I should figure out better what to work on after those two onsite interviews.

Get motivated

It is such great experience to read this post on leetcode.com, the author shared his experience to get offers from Google and Facebook after numerous failures. Here is the link.

Keep learning personal finance

Oct. 9, 2019

Introduction

It is my concern how to spend time, should I focus on algorithm and data structure practice, or I learn more about personal finance, investment.

A check list 

How to write an excellent post?

Oct. 9, 2019

Introduction

It is the first time I learn that I can write a post and then get 4 upvotes, ranking top 7 in one of hard level algorithm on Leetcode.com. 

Crafting skills

I think that it is not difficult to write an excellent post. The algorithm I studied is so easy to understand, since I put together some comment to make it so straightforward.

And also I did spend time to save a graph from weekly contest lead board, and then wrote down my observation.

It is so important for me to learn how to document good learning process for other players.

Being a good mentor, helper, or player, I strive to document my practice, my learning, and then I have chance to meet more people in the world. I do believe that it takes so much time for me to learn and master one algorithm. I also certainly like to see people advance skills quickly, since they learn from my experience through my post or blog. I always like to be one of players, share and learn, learn and then share.

Here is the link.

Case study: hard level algorithm my post ranks top 7

Oct. 9, 2019

Introduction

It is the time for me to review my achievements. I did not get really big progress in terms of problem solving in 2019. I did get back into stock market, and put my 401 K and IRA back into stock market this April, and I went to onsite interview from Fortinet in May, and then prepared onsite for Amazon and Facebook in August, I had phone screen from Docusign in September. I learn slowly to adapt the challenge to advance myself. Today I like to talk about something new, my post ranks top 7 - a hard level algorithm.

Case study

I did not notice that I wrote a post, since I did not add it to my github repository Leetcode page six month ago.

Here is the image to show my ranking.

Here is the link.

How to write an excellent post?

I think that it is not difficult to write an excellent post. The algorithm I studied is so easy to understand, since I put together some comment to make it so straightforward.

And also I did spend time to save a graph from weekly contest lead board, and then wrote down my observation.

It is so important for me to learn how to document good learning process for other players.

Being a good mentor, helper, or player, I strive to document my practice, my learning, and then I have chance to meet more people in the world. I do believe that it takes so much time for me to learn and master one algorithm. I also certainly like to see people advance skills quickly. I always like to be one of players, share and learn, learn and then share.

US blacklists China's biggest unicorns

Here is the link.

1049. Last Stone Weight II

Oct. 9, 2019

Introduction

It is my second practice. I like to write one more idea and also look into the issues, what I should learn from the code.

Case study

Here is the post.

Oct. 9, 2019
It is a good idea to learn to write more than one solution. What I did is to study the most popular post in the discussion post, and then I wrote one C# solution.

It is important to read the case study I prepare first, and then it will be much easy to follow the design of the solution.

Case study
Given the array with values [31, 26, 33, 21, 40], the sum of the array is 151, let us denote it as Sum. Sum/ 2 will be 75. We can divide into two sets, [33, 40] and [31, 26, 21], the sum of first array is 73, and the sum of second array is 78, the minimum difference is 5.

But if we update the loop from ascending (this is descending, (for (int i = Math.Min(1500, prefixSum); i >= item; i--)), one number may be used more than once, so that minimum difference can be one. Since [26, 26, 23] can be an array, but 26 is counted twice, the sum of the array is 75, so 151 - 2 * 75 = 1.

The challenges

1. How to design the solution so that each stone will be at most counted once to the sum?
2. Argue to yourself, why order does not matter? We can count each stone at most once in any sum, but which goes first does not matter.

Here are highlights:

1. Understand how to convert the problem to classical Knapsack problem to divide array into two sets;
2. Understand how to find all possible sum using all stones available, make sure that one stone can only be used at most once for each sum;
3. Most challenging problem is to design the search using descending order. Detail see my first practice if you have questions. Here is the post.
4. Go over a test case and learn the case study before working on the solution.

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

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

        /// <summary>
        /// Oct. 9, 2019
        /// study code
        /// https://leetcode.com/problems/last-stone-weight-ii/discuss/294888/JavaC%2B%2BPython-Easy-Knapsacks-DP
        /// 
        /// The idea is to implement the solution using time complexity O(NS), N is length of the array, S is the sum of the array. 
        /// space complexity is O(S), where S = sum of the array stones. 
        /// </summary>
        /// <param name="stones"></param>
        /// <returns></returns>
        public static int LastStoneWeightII(int[] stones)
        {
            // length <= 30, value of stones [1, 100]
            var dp = new bool[1501];

            dp[0] = true;
            var sum = stones.Sum();

            var prefixSum = 0; 

            foreach (var item in stones)
            {
                prefixSum += item;
                for (int i = Math.Min(1500, prefixSum); i >= item; i--)
                {
                    dp[i] |= dp[i - item];
                }
            }

            for(int i = sum/2; i > 0; i--)
            {
                if(dp[i])
                {
                    return sum - i * 2; 
                }
            }

            return 0; 
        }
    }
}