Tuesday, July 16, 2019

Canada high school

安省高中(其他省应该差不多)有三个毕业条件:

1. 修满30个学分
2. 收集40小时的社区义工服务
3. Pass安省的literacy test

首先说说这30个学分,它分18个必修学分和12个选修学分。这18个必修学分为:

Gr9:英语、数学、科学、法语、地理、体育、艺术类、
Gr10:英语、数学、科学、历史、civics/careers(各0.5credit)
Gr11:英语、数学
Gr12:英语

以上的都是你在各个年级必须选的课,但是,这只是15个学分,还有三个补充要求:

1. 在英语、或法语、或其他语言、或社会科学类、或Canadian and world studies类、或guidance and career education类、或cooperative education中再取得一个学分。
2. 在健康体育类、或艺术类、或business studies类、或法语、或cooperative education中再取得一个学分。
3. 在11或12年纪科学类、或technological education类、或法语类、或电脑类或cooperative education再拿一个学分。

紧接着又是一大批注释:

1. 最多只能有3个ESL或ELD学分能被算进4个英语必修学分内,也就是说不管你英语水平如何,12年纪你必须上普通的英语课才能毕业。
2. 在以上3个补充要求中都有法语,但最多只能有2个法语学分能被算入其内,而且第一个法语学分必须被算入第一个要求,另一个学分可以选择被算入第二或第三个要求。
3. 在以上3个补充要求中也都有cooperative education,但最多只能有2个cooperative education学分算入必修学分内。

一旦你把上面我的长篇大论理解清楚了,剩下的12个选修学分就简单多了。学生每年级最多可以选八门课,4乘8=32,所以你可以在11或12年纪有2个spare。当然也可以不选spare,这个依你的个人情况来定。

再接着说高中的另外两个毕业条件。40小时的义工听起来很多,但是你也有4年的时间来完成。而且想找义工干非常容易。学校的Student Service就会有许多的义工信息。建议做义工找容易的或与你的爱好或理想相关的。这样不仅做起来动力更大,对你以后申请大学和奖学金也有一定的帮助。很多人在完成40小时后还会接着干(劳动模范啊)这样不仅帮助申请大学,也可以积累一下你在社会上的工作经验。

至于literacy test(OSSLT),我建议大家不用过于担心。它的要求是pass了就行,而且成绩不会被算进你的平均分内。这个考试十年级做,我在9年纪英语得了85分,十年级OSSLT考了接近满分,很容易,而且英语不好的中国学生也不必担心,因为10年纪没过可以接着考,再考一次估计就肯定能过了

230. Kth Smallest Element in a BST

It is like a party to prepare this July 2019

I like to get together those algorithms to review before my phone screen from Facebook.

I just could not believe that I came cross so many new algorithms, and I need to write a few algorithms just to warm up my crafting skills.

My favorite one is to write quick select algorithm.


Google algorithms in 2017

Here is the link.


Zumba Vancouver waterfront

July 16, 2019

Introduction

It is my health research. I need to work on weight control project, one idea is to play more tennis sport. Another idea is to have a healthy life style.

I went to Zumba event with my coworkers today. Here is the old video.

How I choose people to chat?

July 16, 2019

Introduction


It is my personal finance research. I learn that I only have limit hours to work and chat with friends. I also get connected to friends quickly, last weekend a software engineer working in Citibank in New York left a comment in my blog, waistline problem, and then I chose to get connected.

How I choose people to chat?


I also like to have honest communication. I do not like to waste time to chat with friends, sometimes I think that chatting is such a big waste of time.

Go ahead to talk over phone 2 or 3 minutes. I start to stop responding any message in working hour from Linkedin.com, or gmail.com. I learn to evaluate how good the person can communicate.

Since I am below average as an interviewee on interviewing.io based on my 5 interviews, I start to think about how to make improvements as well.




How to get smart when you are over 50 years old?

July 16, 2019

Introduction


It is my personal finance research. I like to write a small topic called how to get smart when you are over 50 years old.

Listen to every advice


I graduated from Shanghai Jiaotong university. So my friends from same universities shared with me their work experience.

Last year my classmate laughed about me to apply Facebook or Amazon; it should be young person's job. I took the advice, and learned from her advice. She invested on the stock market, so I started to invest on stock market as well back from March 2019.

I also like to learn from my friends. Do not let emotions get into my way. Just do it!

I think that working on algorithms, and also I help a lot of people to prepare their onsite interviews. I feel that it is such great time in my life.


The secret to have a happy life as a software programmer

July 16, 2019

Introduction


It is so challenging to work as a software programmer. I like to stay on my current job forever, since it is so enjoyable to work every day.

Happy life as a software programmer


It is so challenging to meet a new person on interviewing.io. But I find that it is also very exciting experience.

I met an interviewee today, he told me that he went to Facebook onsite, Microsoft onsite, and prepare Amazon onsite. And he gave me feedback to work on communication skills.

He does not believe that my feedback on lowest common ancestor is true. He likes to test the code using web compiler.

One thing I can tell is how good I should be in order to pass facebook phone screen and get onsite.

July 17, 2019

What is secret? Describe a happy life

I just finished the phone screen from Facebook. I like to add some content about secret, describe a happy life.



Minimum rectangle

给一堆点, 求(四个点)能组成最小面经的矩形

111. Minimum Depth of Binary Tree

Here is my sharing. Second practice in 2019 is here.



233. Number of Digit One

713. Subarray Product Less Than K

560. Subarray Sum Equals K

Tips to share

Here is the link. 


接着跟大家说一些面试的技巧。

1)面试官的心态
面试官要看的,不是你会不会做题。会做题的人很多,好的engineer != 会做题的engineer。你要做的是在最有限的时间里展现这点。即使题不会做,也要展现出一个好的engineering thought process跟technical communication。

2)Coding Round
绝对不要秒做!
绝对不要秒做!

绝对不要秒做!

上面说了,要有好的thought process跟communication,拿到题要先思考所有的edge case,input形式,需要的run time和space complexity,逐一跟面试官沟通。当然,绝大多数的情况下,他们会说yeah assume XYZ,但是要他们说了才可以,你自己瞎assume肯定会挂的。
然后尽量不要像是背的。太极拳的精华在招意,不在招式,同理,解题的精华在思维,不在代码。最好的方式莫过于现场跟面试官先讨论逻辑和数据结,然后写出一些common test cast,然后代码一边写一边说,现场找到bug并且完善,会比闷头写码秒解好很多。而且秒解非常容易招很难的Follow Up,因为面试官不确定你是否真的理解还是只是做了题。
还有就是互动非常重要,写代码的时候尽量同时解释自己的思维,为什么要加一个storage variable,为什么选择这样的subroutine,为什么用这个library里的数据结构等等,然后写完别等他们问,直接说这个Runtime和Space complexity是什么,还有什么其他的方法,那些其他方法的complexity是什么等等,显示出自己是经过考虑才选择出这样的代码结构。很多国人小朋友都觉得沟通有障碍就不说话,但是这样不是明摆着自己承认不会交流吗?要记得,花这么多时间刷题的同时也要同时在沟通上面下功夫。
最后最后,要想想test case要怎么写,这个现在经常问,想想你在刷题的时候LC会有什么样的test case卡到你,写这些test case的人当时的想法,会很有帮助。

3)System Design
这个也是沟通的环节,个人倾向是先把所有的Use Case写出来,然后写出所有会需要的component,schema和大概的API,然后在开始做设计。重点是根据每一个Use case做出相对的实现,比如这个A Use Case需要high availability,所以我选择这个技术实现,这个B Use Case需要Atomic transaction,所以我要做这样的实现。跟Coding一样,要确定好scope和其他supproting的系统,比如Facebook/Linkedin经常问News Feed,你要问我需不需要考虑Relevance,sorting,context等等,大概率是不需要,但是你要展示出你在思考这些问题。然后Scope也要问清楚,这个东西的User是谁,deliverable是什么,我们需不要handle infrastructure scaling,需不需要handle各种UGC storage,后台的partition tolerance和load balancing和data duplication等等。一般情况下main design部分都会让你skip,然后选一两个比较精的部分问follow up,所以当你问这些scope的同事,心里面也该有个大概的底应该要如何实现。

4)BQ
BQ应该是最重要的环节,前面说了,会写码的人很多,能解决问题的人很少,能带领团队解决问题的人少之又少。这里所有BQ的问题都是为了验证3点。
a)你有没有problem solving skills?你解决问题有没有一定的策略,有没有办法确保相同的问题不会发生,有没有办法确保其他人不犯相同的错误,碰到自己没法解决的问题如何处理,自己直接导致的问题会如何处理,如何面对多个stakeholder不一致的方向及要求等等
b)你有没有leadership skills?团队有问题的时候你会怎么帮忙?遇到bug你是只修bug还是能深究问题并且surface给management,能不能在团队有困难时go above and beyond,能不能有效的沟通并且解决矛盾,在沟通的时候有没有对他人立场的认知和理解,并且就这个理解给出对他人最有用的答案等等
c)你有没有self awareness?你对自己的期许是什么,你最强的能力是什么,你在什么情况下会under perform,你明不明白自己在这个group里能起到多大的作用等等

面试官问的所有傻屌问题想要的答案都是你有没有一些上述的quality,而你要做的就是好好嗦发。一个好答案分成起承转合。
起:历史背景,为什么有这样的情况,其他人为什么没管,这个情况的consequence是什么
承:讨论自己的思考过程,为什么最后选择了这种方法解决问题,其他没有选择的方案有什么pros and cons
转:具体解决问题的时候遇到了什么样的困难,如何克服,学到了什么
合:最后结果,问题是否完美解决,后续有什么follow up,是否给你的org或者group带来了正面的影响等等

讲的时候多观察面试官,感觉他有问题的时候可以停一下,如果有什么笑点的时候也可以停一下缓和气氛(例如策划经常该需求,android native各种坑,samsung的OS多他妈傻逼之类的)。

5)Time to ask questions
一般情况下,能把问题答完都至少会pass,但是要有strong feedback你短短的几分钟问答就会很重要。我个人喜欢的问题是问Tech culture,比如我在用别的组的系统,发现不能实现我想做的功能,如果要加入这个功能会否给我这样的自由度,其他组会不会不高兴,将来的ownership和maintenence会如何分配,或者我会问有没有一些centralized的文档库,或者central services org,比如你之前碰到过的问题,花了很长时间才找到答案,我将来如果入职也遇到相同的问题会不会也需要花一样久的时间去找这些答案。如果对他们的业务不熟,也可以就问面试官他的经历,他来这儿几年,在那些组干过,具体业务是什么,觉不觉得有继续学习的深度和广度(要凸显自己热爱学习新技术),如果跟management提出想要跳出comfort zone会不会有阻力等等。尽量开始一个问答对话,尽量让对方感觉亲切。

最后希望所有同学都能找到自己心仪的offer!

54. Spiral Matrix

Here is my sharing.


21. Merge Two Sorted Lists

636. Exclusive Time of Functions

621. Task Scheduler

42. Trapping Rain Water

273. Integer to English Words

Here is my sharing.


973. K Closest Points to Origin

560. Subarray Sum Equals K

415. Add Strings

215. Kth Largest Element in an Array

I like to write a quick select algorithm, and also read all kinds of analysis. It is a really good algorithm for me to practice.


136. Single Number

98. Validate Binary Search Tree

  1. Validate Binary Search Tree

209. Minimum Size Subarray Sum

67. Add Binary

I like to write a C# solution and compare to those practice more than 4 years ago.

I am so excited to read my own code written more than 4 years ago. I am so glad that I can see so many issues in my practice.

July 16, 2019
67. Add Binary
C# a while loop to practice in 2019
C# Write a simple for loop practice in 2019

Monday, July 15, 2019

173. Binary Search Tree Iterator

Here is my sharing.

121. Best Time to Buy and Sell Stock

Here is my sharing on leetcode.com.

Matrix with value 0 and 1, find leftmost 1 column

高频的01矩阵找最左边1所在的列,假装没做过,分析了从O(m*n) 到O(m*logn)到O(m+n)的算法,最后实现。
0011111]], [0001111], [0111111]]。每row由0,1组成,前面全是0之后全是1,让找到最左边的1所在的列,这个例子里最左边的1是最后一行,在第二列。O(m+n)解法


lintcode----最左的1


第二题,一个01矩阵,每一行所有的0在前,1在后,要求给出矩阵中最左边的1所在的列id。我先给了一种O(m logn)的方法,面试官说我这个方法在n大的时候可以,然后直接告诉我了O(m+n)的方法让我实现,不知道算不算黑点。

题目描述: 
一个二维数组,每一行都只有0和1,前面部分是0,后一部分是1,找到数组里面所有行中最左边的1所在的列数。

注意事项: 
数组的行数,列数不超过1000 
为了约束时间复杂度,你的程序将会运行50000次

样例: 
给出 arr = [[0,0,0,1],[1,1,1,1]], 返回 0。

解释: 
arr[1][0]为所有行中最左边的1,其所在的列为0。 
给出 arr = [[0,0,0,1],[0,1,1,1]], 返回 1。

解释: 
arr[1][1]为所有行中最左边的1,其所在的列为1。

思路讲解:这个题目不是很难主要的难点就是关于程序会运行50000次,就说明程序会重复的调用,如果我们按照从第一列开始搜索、第二列搜索………….一直到最后一列。这样调用一次不会花费很多时间,但是如果这样的程序调用50000次,时间复杂度就变得很高了,所以我们就需要对这个数组特殊处理,因为我们每次都是判断是那一列,我们只需要将一整列加起来了,如果不是0,就说明其存在1,反之则不存在,这样时间复杂度就变成了o(n)。

代码详解:

class Solution {
public:
    /**
     * @param arr: The 2-dimension array
     * @return: Return the column the leftmost one is located
     */
    int getColumn(vector<vector<int>> &arr) {
        // Write your code here
        vector<int>res;
        i2D_change_1D(arr,res);
        for(int i=0;i<arr[0].size();i++){
            if(res[i]!=0){
                return i;
            }
        }

    }
    void i2D_change_1D(vector<vector<int>> arr,vector<int>&res){
        int m=arr.size();
        int n=arr[0].size();

        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=0;j<m;j++){
                sum=sum+arr[j][i];
            }
            res.push_back(sum);
        }
    }
};
--------------------- 
作者:一只叫羊的羊 
来源:CSDN 
原文:https://blog.csdn.net/qq_34355232/article/details/79668575 

版权声明:本文为博主原创文章,转载请附上博文链接!

785. Is Graph Bipartite?

I plan to write C# code for 785 is graph bipartite.

It is very important for me to write one algorithm more than one solution. I have to time myself and try to push myself to write bug free code in less than 20 minutes.

Here is my practice in July 16, 2019.


295. Find Median from Data Stream

Here is my practice sharing.

It is most challenging problem to solve since the optimal solution is to use two data structure, one is minimum heap, and the other one is maximum heap. I was asked to work on the algorithm in phone screen in March 2017.
It is time for me to review the algorithm again.
How to design minimum heap and maximum heap using C#?
Using C# SortedSet, and also define Comparer.
One tip to make median calcuation easy
It is a good idea to make minimum heap size is bigger than maximum heap size by 1 if total length is is odd.
public class MedianFinder {

    /** initialize your data structure here. */
    public MedianFinder() {
        
    }
    
    private int counter = 0;

        private SortedSet<int[]> setLow = new SortedSet<int[]>(
            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));

        private SortedSet<int[]> setHigh = new SortedSet<int[]>(
            Comparer<int[]>.Create((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
            
    public void AddNum(int num) {
        var newNum = new int[2] { num, counter++ };

            bool twoTreesSameSize = setLow.Count == setHigh.Count;          

            if (twoTreesSameSize)
            {
                if (setLow.Count == 0 || newNum[0] <= setLow.Max[0])
                {
                    setLow.Add(newNum);
                }
                else
                {
                    setHigh.Add(newNum);

                    // move the minimum number from setHigh to setLow. 
                    setLow.Add(setHigh.Min);
                    setHigh.Remove(setHigh.Min);
                }
            }
            else if (newNum[0] <= setLow.Max[0])
            {
                setLow.Add(newNum);

                // move the maximum number from setLow to setHigh
                setHigh.Add(setLow.Max);
                setLow.Remove(setLow.Max);
            }
            else
            {
                setHigh.Add(newNum);
            }
    }
    
    public double FindMedian() {
        if (setLow.Count == 0)
            {
                return 0;
            }

            if (setLow.Count == setHigh.Count)
            {
                return (setLow.Max[0] + setHigh.Min[0]) / 2d;
            }
            else
            {
                return setLow.Max[0];
            }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.AddNum(num);
 * double param_2 = obj.FindMedian();
 */


Sunday, July 14, 2019

Columbia international college

I plan to spend 30 minutes to study the website. I have to work for my young sister and help her to apply admission for my niece.

Here is the link.


Technical Interview Question: Minimum Window Substring [Sliding Window] [Leetcode]

Here is the link.


July 15, 2019
76. Minimum Window Substring C# slide window template study code practice in 2019 

It is party time! play tennis against the wall

Case study: How can you compete with young people?

July 14, 2019

Introduction


It is my personal finance research. Last year our Shanghai Jiaotong University 70141 classmates got together, and we met our mathematics professor in the city of Vancouver. I talked to my classmate,  she advised me not to apply Amazon again, or Facebook. I just shared my onsite interview in the city of Seattle in 2018. I wondered what I should do, should I do something else? She made comment, how you can compete with young people?

Case study


I like to write a small case study on this topic. I did not have answer at that time, in July 2018. How can I compete with young generation for those positions?

I started my personal finance research starting from Nov. 2018.  I decided to move on, since Amazon is the only company I got two onsite interviews from 2016 to 2018.

I have to learn to push myself, examine all things I can do. So I started the personal finance research, continue to learn US economy, watch a lot of CNBC fast track money show. I started to work on my retirement portfolio and Canada TFSA portfolio as well. My classmate purchases stock over years, she works for bank and also insurance company.

I come back to apply again for Amazon AWS job in 2019.

If I cannot compete with young people, then I will be the best friend or coach, or hitting partner to work together.

How to do a good job? 


I just keep learning. My ex-coworker left after working in same manufacturer company this May 2019. She coached me to reach out to people, say hello; I still remembered the last day we went out lunch with a lot of coworkers, after 20 to 30 minutes, she started to collect business cards from restaurant sitting next to us. She talks to strangers.

I invited others to join me Kevin O Leary's show in Canada, my coworker Jenny went with me. In less than 30 minutes, she pushed me to talk to the front, left and right. And she asked what brings you to show.

Young people are working so hard. They keep running and doing physical exercise, fit like a movie star, fashion like a model. 

Case study: Why I failed to get computer science Ph.D. from Florida Atlantic University from 2001 to 2010?

July 14, 2019

Introduction

It is my personal finance research. I like to conduct some research and analyze why I could not get computer science Ph.D. and what lessons I should have learned from my own experience.

Case study


Case study: How I passed Amazon AWS phone screen on July 8, 2019

July 14, 2019

Introduction


I was so nervous to work on online assessment two weeks ago. A lot of emotions just came to my mind in the first 10 minutes, and then I noticed that I had to calm down, and what I did to read problem statement word by word loudly. I used the technique to calm myself down. So how I passed Amazon AWS phone screen? I should not talk about algorithm, but instead I like to talk about my communication and how I improved my performance in short 60 minutes.

Case study


First of all, I always am very nice to meet people and learn things if I can. I went to Amazon AWS security group open house, what I did is to make sure that I talk to every manager, manager's manager. I never know who will be my hiring manager or I always find out that those people are very nice and helpful to answer my questions.

Most of time I ask Amazon leadership principles questions as well in those event.

How did I do in phone screen?

I read the problem statement slowly after I think that I understand the problem. That is my technique! I am trying to make sure that I understand the problem first.

Three things are most important.

1. Scalability, I discuss options available to deal with time complexity, O(nlogn), O(n^2), O(n) algorithm. I write down all options, and ask network size;
2, Object-oriented design, the function show be designed to follow S.O.L.I.D. principle
3. I can come out the solution in a minute, how to solve the problem. And also I can write the code matching the idea as well.

Actionable Items


I need to work on object-oriented design. The interviewer gave me several hints to come out good design of API. Also the interviewer reminded me a few times that I like to ask an extended algorithm. I need to make sure what I write is correct before he can move on extended algorithm.

I need to measure how much time I have in order for me to work on extended algorithm.


10 reasons I apply Facebook second time two years in a row

July 14, 2019

Introduction


It is hard for me to parent myself. I have to watch out my behavior problems. I made wrong comment to say that I am setting my target too high when Facebook recruiter contacted me this May from Seattle office. I should believe that it takes a village to raise a child. I should help other learn and contribute to make our society better place to be, and live and enjoy.


10 reasons


One of most important reason is that I like technology, and all I can do is to write more blogs, more algorithm and data structure, more personal finance blog, and work hard from my niece and nephew, and help myself as well.

One thing I can do is to apply Facebook, prepare for phone screen. I need to figure out how to handle stress and pressure to solve an algorithm problem.

The pressure to prepare phone screen is so helpful. I start to find ways to learn again, I like to try new ideas to find algorithms to work on.


10 reasons I apply Amazon non-stop

July 14, 2019

Introduction


It is my personal finance research. I like to do what  a rich person chooses to do. Be frugal, love equity exposure, do not let emotion get on the way, just do it. Recently I chatted with my friend, he is such successful in his career, and he told me that even he does not apply Amazon; I already invest so much time on this Amazon job application, I should think about doing something else.

10 reasons I apply Amazon non-stop


I learn to have thick skin, first step is to follow all Amazon managers on linkedin if I can. If there is an event about AWS woman meetup, AWS security open house, I just show up, and then ask questions, and eat food and enjoy view. I just like to push myself to explore new things as I can.

My young sister asked me why I continue to apply. I quit sibling wechat group, and I do not like to do so many social chats. I like to do something bigger. I certainly can help my young sister if she likes her daughter to study high school in Canada. But I just cannot handle it when I am super busy.

I should put together 10 reasons first.

First of all, I like to push myself hard, and invest on US economy, and make my favorite technology company bigger and stronger. That is all I like to do.

I love to code algorithm and data structure. I can do it all day long. Usually I only have 30 minutes to one hour break every day, but I like to jump on coding for my favorite algorithm.

This year August I will have my third onsite interview. They are five rounds of interview, including shadow interview, system design interview, I will have to win those votes from onsite meetings.

It is hard, but if I prepare enough time and also ask help from my friend to work on system design, I should learn a lot through a few weeks preparation.



Columbia academy

It is busy summer. My young sister likes to send  her daughter to attend high school in Columbia academy this Sept. I need to catch up and do some research if I can be a guardian, and also it means that I will spend time to work on those courses to prepare college admission test.


Technical Interview Question: Minimum Window Substring [Sliding Window] [Leetcode]

Here is the link.


Facebook phone screen 72 hours count down

July 14, 2019

Introduction


It is time for me to work on 72 hours count down for Facebook phone screen. Last night I went through the 1point3acres website to see all recently asked Facebook phone screen or onsite interview algorithms. I like to continue to work on them.

72 hours 


I need to go out to play one or two hours tennis, and then spend rest of day to work on algorithms.


My waist line

July 14, 2019

Introduction

 I like to write something related to my waist line. I need to control weight, and play more tennis. I used to play whole day tennis in weekend, but now I have to cut to 1 or 2 hours in weekend, since I like to work on algorithm practice.

How to control weight?

I need to continue to work on weight control.

3. Longest Substring Without Repeating Characters

Here is the video I plan to watch.

Here is the picture of lecture notes:



Add character located at right index of input string into our Set, checking if it already exist

  - Doesn't Exist:
      Add to set, right++; update max (expand our window)
  - Exists
      Remove character at left pointer from set; left++; (shift our window)
Repeat until right index and left index have reached the length of input.


Actionable Items


I like to watch a few times, and also figure out how to explain the algorithm based on Daniel Su's presentation.



3. Longest Substring Without Repeating Characters

I put all most past practice on Leetcode.com. I just could not believe how much I have improved in terms of problem solving.

In 2015, I just started to work on practice of Leetcode algorithms.



Saturday, July 13, 2019

How to answer the question properly?

I like to look into this topic called how to answer the question properly, specially in the onsite interview.

I should be able to answer the question directly, give out the answer, and then do not talk more. It is important for me to help the interviewer to evaluate a lot of things in the onsite interview. The interviewer prepares a lot of questions to ask me, if I use more time than needed, then the interviewer will not have enough time to complete the assessment.

I was complained back in 2010 June when I joined the current company. But I still have the same issue.


23. Merge k Sorted Lists

It is a hard level algorithm. I wrote a minimum heap using SortedDictionary and also I shared my solution here.

I like to warm up this algorithm since I was asked to work on the algorithm back in August 2018 phone screen.

Here is the link.

It is hard level algorithm and also minimum heap is most popular data structure to work on. I learned to write the first minimum heap using SortedDictionary in August 2018, and it is time for me to warm up and study other C# solution as well.
I like to take some time to write a C# solution again.
Here are highlights:
  1. Define MinHeap class using SortedDictionary, the key of dictionary is the value of linked list node's value, the value of dictionary is Queue;
  2. Add two API for MinHeap class, one is to add node to the heap, second one is to remove minimum from heap. In order to find node with minimum value, since SortedDictionary is sorted, just call First() API and then get Key.
  3. Time complexity is O(k * logk + n * logk), k is the heap size, n is total of nodes in all the lists.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _23_merge_k_sorted_lists
{
    class Program
    {
        public class ListNode {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }

        static void Main(string[] args)
        {
        }

        /// <summary>
        /// July 13, 2019
        /// I like to take the approach using minimum heap as a solution, so the time complexity will be O(N), 
        /// N is total of all nodes. 
        /// Assuming that lists's length is K, build a heap with size K, 
        /// time complexity: O(KlogN). 
        /// 
        /// </summary>
        /// <param name="lists"></param>
        /// <returns></returns>
        public ListNode MergeKLists(ListNode[] lists)
        {
            var heap = new MinHeap(); 

            // put head node in every list into minimum heap first
            foreach(var node in lists)
            {
                if (node == null)
                    continue;
                heap.Add(node.val, node);
            }

            // next build a linked list using ascending order
            ListNode current = null;
            ListNode newHead = null; 

            while(heap.map.Count > 0)
            {
                var node = heap.PopMin();
                if (node.next != null)
                    heap.Add(node.next.val, node.next);

                if (current == null)
                {
                    current = node;
                    newHead = current;
                }
                else
                {
                    current.next = node;
                    current = current.next; 
                }                
            }

            return newHead; 
        }

        /// <summary>
        /// Define my own minimum heap class MinHeap
        /// </summary>
        public class MinHeap
        {
            public SortedDictionary<int, Queue<ListNode>> map = new SortedDictionary<int, Queue<ListNode>>(); 

            public void Add(int val, ListNode node)
            {
                if(!map.ContainsKey(val))
                {
                    map.Add(val, new Queue<ListNode>());
                }

                map[val].Enqueue(node); 
            }

            public ListNode PopMin()
            {
                int minKey = map.First().Key;
                var node = map[minKey].Dequeue(); 

                if(map[minKey].Count == 0)
                {
                    map.Remove(minKey);
                }

                return node; 
            }
        }
    }
}





143. Reorder List

438. Find All Anagrams in a String

Here is my discuss post.


49. Group Anagrams

Here is the post I shared.


211. Add and Search Word - Data structure design

Here is my discussion post.


721. Accounts Merge

Union find algorithm, here is my discussion post.


529. Minesweeper

269 Alien dictionary

It is a hard level locked algorithm on Leetcode.com.  I plan to study the algorithm on this web page.

986. Interval List Intersections

297. Serialize and Deserialize Binary Tree

636. Exclusive Time of Functions

Array algorithm

已排序的二维零一数组中寻找最左侧一的位置。


417. Pacific Atlantic Water Flow

我们day0 出发, day1 返回.

Algorithms to review

FB面的是5/6 senior tech lead
  • 电面很简单,两道题:
  • find kth nearest point to the origin
  • see if given numbers in array can sum up to target


onsite:
第一轮:
alien dictionary (leetcode原题)
topological tree, given courses and their de...

674. Longest Continuous Increasing Subsequence

It is an easy level algorithm. I like to share my practice written 10 month ago.