Summer is the great time

July 31, 2018

Introduction

It is my turn to congratulate my two classmates to become computer science department head this year. I cannot believe how hard people are working and then make such great career success.

Being an interviewer is such great experience

July 31, 2018

Introduction

It is so interesting to know that I start to change quickly once I start to work on as an mock interviewer this 10:00 PM. I took longest break after 2:00 PM, and I let myself enjoy youtube music from 5:00 PM to 8:00 PM three hours.

Summer is such great time for a programmer

July 31, 2018

Introduction

I like to do a small research titled "Summer is such great time for a programmer". I have experienced so many great things this year, I just could not believe that the world can be so connected and every time I like to reach out the world, I got response.

Follow the procedure 

I learn to be patience for my personal growth on algorithm and data structure problem solving. Every time I have real time experience, I learn that it is so important for me to calm down, and get into the problem solving first. After those one hour, I need to quickly get out and go back to hard working and  training on data structure and algorithms.

I can tell there is something missing in my training. I have to listen carefully and also follow the advice.

Need an excuse

July 31, 2018

Introduction

We will have a get-together in the city of Vancouver this Thursday with our college statistics teacher who taught us Probability course. I still remember the time he gave us a coaching session how to work on probability. He was our probability teacher when he was only less than 25 years old, we were math undergraduate students in Shanghai Jiaotong university.

It is time for me to meet the statistics teacher back in 1985, over 33 years ago with my two other classmates of Shanghai Jiaotong University this Thursday. We three of us are in the city of Vancouver, and we will meet our teacher, who is department of head of Statistics department in the Connecticut ranking 44. Here is the link and here is the professor link.

I like to write a blog about "Need an excuse", since I try to give myself 20 minutes therapy to talk about how mathematics teaches us to prove things. I like it as an excuse to help myself out today.

Why I need an excuse?

I have to learn to take risk and then solve given problem in less than 15 minutes; most of important I have to quickly identify what are my concerns. In order for me to do that, I need to communicate with the peer what my concern is, how to get into the success of problem solving.

The problem is that my object-oriented programming skills is kind of weak; and then I have to relate to iterator to sorting. I did not question that every lists are sorted and will be iterated on. I need to get the sorted list based on multiple lists, merge a sorted list based on multiple sorted lists.

So many things are under my investigations. I did not come out what problem I should solve in first 15 minutes.

If one of lists is not sorted then the whole plan will be problematic

My argument is if one of lists is not sorted in ascending order, then the whole plan will not work.

Talk about money and confidence

July 31, 2018

Introduction

Money and confidence can be talked together. How will I make a story to connect the dots?

Here is the summary. Stock market is all about confidence. I like to write a blog about it. I also like to talk about economy, immigrant, backup plan, Canada, Canadian.

It is time for me to relax after two weeks drill about algorithm and data structure training. I like to get messy about the blogging, add some spice about my blog. Money is such a great topic, if I can master how to make good friends, keep good relationship at work, and get along with young generation in my family, all I need to learn is how to make a lot a lot money.

Up-And-downs

I did check USA most popular zillow website last Satuday, since I am the owner of a small condo near Florida Atlantic university. I slowed down my training and put together all the paper work. I suddenly realized that USA economy is heading so strong I never imaged before, I did not know what is going on there.

My zillow.com web page shows that last 12 months the sales of condo goes up a lot in total asking price. $50,000 us dollar in one year. I cannot take it too seriously since it goes up and down a few times already last 20 years.

What-if

I still could not believe that I sold all the stocks I hold in 2008 since I could not handle so many things if I can not settle down a corner in the earth. At that time, I was searching the whole world where is my next destination.

I had a very good friend starting from 2006 who gave me lesson how stock market is the confidence. For me it is not easy to understand her teaching. She worked for a wall street firm and we worked so closely together for a few projects.

I remembered one time in 2009 she decided to vote with her husband, her family will give me 100% support for me to go over the paper work of immigration, and share her past experience. I have to file a lawsuit to reopen my immigration case...

Every immigrant and family in United States has their own story, they back up so many plans in order to make it succeed in United States. Canada is their backup plan. Canada immigration is easy case for them. Usually they get first and land first. I decided to go for Canada option.

My friend gave me encouragement, just think about travelling to Canada for a tour, and visit different people and have a different life.

What if I have confidence on the stock market, specially on Amazon, Facebook, Microsoft. In 2008 I already got phone screen from Amazon and I knew that people are so hard working since I was asked if I graduated from computer science Ph.D. degree.

Confidence

I try to apply confidence concept in my software programmer pursuit. What is confidence? Why I will have scare? When I deal with the new task or new project related to coding?

Last time I talk to myself that I need to bring a coach to work, and this time I tell myself that I can do it all by myself.

Serve the best 

I could not believe that I am in strong economy in Canada over last eight years. I do not know how business works. I try to focus on algorithm and data structure basics.

Proverbs 30: 7 - 9

Two things I asked of You,
         Do not refuse me before I die:

8Keep deception and lies far from me,
         Give me neither poverty nor riches;
         Feed me with the food that is my portion,

9That I not be full and deny You and say, “Who is the LORD?”
         Or that I not be in want and steal,
         And profane the name of my God.

Leetcode 314: Binary tree vertical order traversal

July 31, 2018

Introduction

Image that you only have five minutes for one algorithm, what I do is to read the explanation written in Chinese. Here is the blog for the medium level algorithm called Binary tree vertical order traversal.

My note in Chinese 

这道题让我们竖直遍历二叉树，并把每一列存入一个二维数组，我们看题目中给的第一个例子，3和15属于同一列，3在前，第二个例子中，3,5,2在同一列，3在前，5和2紧随其后，那么我们隐约的可以感觉到好像是一种层序遍历的前后顺序，那么我们如何来确定列的顺序呢，我们可以把根节点给个序号0，然后开始层序遍历，凡是左子节点则序号减1，右子节点序号加1，这样我们可以通过序号来把相同列的节点值放到一起，我们用一个TreeMap来建立序号和其对应的节点值的映射，用TreeMap的另一个好处是其自动排序功能可以让我们的列从左到右，由于层序遍历需要用到queue，我们此时queue里不能只存节点，而是要存序号和节点组成的pair，这样我们每次取出就可以操作序号，而且排入队中的节点也赋上其正确的序号，

Quick sort technique study

July 31, 2018

Introduction

It is time for me to review the algorithm using quicksort technique. Here is the gist.

Leetcode 40: combination sum II

Leetcode 47: permutations II

Leetcode 46: permutations

Leetcode 90: subsets II

Leetcode 78: subsets

378. Kth Smallest Element in a Sorted Matrix

July 30, 2018

Introduction

It is a medium level algorithm and I think that I worked on the algorithm a few times before. It is better for me to write one and try it using Leetcode online judge.

Leetcode 39: Combination sum

July 30, 2018

Introduction

It is a medium level algorithm called combination sum. But I felt that it is so hard to come out a solution with well-defined time complexity. All I can think about is brute force solution. I like to sort the candidate numbers and then brute force minimum value in the combination sum.

I have the idea but how to write a workable code. I really think about getting general ideas about the algorithm.

It is time to look into Leetcode discussion related to the algorithm. One of C# solutions is here to study.

My practice

I also like to write C# code this time to learn the algorithm again. I also wrote some analysis in the code, I like to help myself to understand the algorithm better this time.

Here is C# practice code in July 2018.

Here is C# practice code in June 2017.

My goal of research 

I came cross this algorithm last night, and I did spend over 10 minutes to think about the algorithm. I could not believe that I wrote a solution just one year ago. I was nervous, and I thought about a few things. I asked myself what is brute force solution. Let me sort the candidate first. What is the minimum number in combination? Can we brute force on this minimum number? How many steps to take to calculate all possible choice for a combination?

In order for me to get comfortable on the algorithm problem solving, I did look into and answer the question when I practice this time.

	/// <summary>
	/// time complexity analysis:
	/// combination starting from 2, target 7, minimum is 2, at most 4 elements in one combination
	/// starting from 2, look for at most another 3 elements -> recursive function, depth first search
	/// at most 3 time, exhaust all options. Each step at most 4 options. So in total will be 4^3 = 64 recursive
	/// calls.
	/// next step, minimum value in combination starts from 3, each step at most 3 options, so in total
	/// will be 3^3 = 27 calls
	/// so the recursive calls should be 4^3 + 3^3 + 2^3 + 1 ^3
	/// the idea is to sort the candidates first in ascending order.
	/// </summary>
	public static void RunTestcase()
	{
	var result = CombinationSum(new int[]{2,3,6,7}, 7);
	}
	public static IList<IList<int>> CombinationSum(int[] candidates, int target)
	{
	var result = new List<IList<int>>();
	var combination = new List<int>();
	Array.Sort(candidates);
	CombinationSum(result, candidates, combination, target, 0);
	return result;
	}
	/// <summary>
	/// I like to talk about the design:
	/// this algorithm is like brute force solution, using back tracking.
	/// combination can be bruted force to find solution. Like minimum value in the combination.
	/// starting from each one.
	/// </summary>
	/// <param name="result"></param>
	/// <param name="candidates"></param>
	/// <param name="combination"></param>
	/// <param name="target"></param>
	/// <param name="start"></param>
	private static void CombinationSum(
	IList<IList<int>> result,
	int[] candidates,
	IList<int> combination,
	int target,
	int start)
	{
	if (target == 0)
	{
	result.Add(new List<int>(combination));
	return;
	}
	// enforce the combination numbers in the list will be non-descending order
	// brute force the start value from all possible values starting from start variable
	for (int i = start; i != candidates.Length && target >= candidates[i]; ++i)
	{
	combination.Add(candidates[i]);
	CombinationSum(result, candidates, combination, target - candidates[i], i);
	combination.Remove(combination.Last());
	}
	}

view raw Leetcode39_combinationSum.cs hosted with ❤ by GitHub

116. Populating Next Right Pointers in Each Node

July 30, 2018

Introduction

It is a medium level algorithm. I like to think about the algorithm using 10 minutes.

Algorithm review II

July 30, 2018

Introduction

It is time for me to read some algorithms and also read a facebook engineer's notes about algorithms. Here is the link.

Algorithm review

July 30, 2018

Introduction

It is time for me to go over the notes again. Here is the link.

Leetcode 44: wildcard matching

July 30, 2018

Introduction

It is a hard level algorithm called wildcard matching. I like to review the algorithm. I also like to think about an extended algorithm based on wildcard matching.

Say goodbye to another weekend

July 30, 2018

Introduction

It is 12:34 AM and I like to call it a day, and ready to go to sleep. I like to write down something here to document this weekend for my algorithm practice.

You do not practice, you do not deserve to win. Andre Agassi

Leetcode 23: Merge K Sorted Lists

July 30, 2018

Introduction

It is hard level algorithm and I like to review the algorithm. I like to review the topic and get the idea what to work on next. Here is the blog.

Based on one in 2015

What I did is like a teacher to help a student, and review her home work after more than two years. Since my last practice is two years 11 months ago, it was August 2015.

1. One sample test case is added from line 26 to line 50.
2. The code is reviewed and make it more readable.
   The merge of two lists is in place. The result will be saved in one of lists. So no extra space is needed.
3. The desgin of function MergeKLists is added in the comment. The main idea to apply master theorem to beat the time complexity of naive approach O(n * k * k), the optimal time complexity is O(n * k * logk).
4. Line 91 variable name is called dummyNode to remind me to go to next one to return at the end of function.
5. add two pointer technique, and write comment to help understand two pointer technique to merge two linked list.
6. edge case handling - it is to append to unfinished linked list to the first list. No need to create a new node and copy the value.


Here is C# practice in 2018 with optimal time complexity.
Here is C# practice in 2015 with optimal time complexity.
Here is the brute force solution - O(n * K * K) - not optimal time complexity, written in 2015

Here is the blog I wrote in 2016 for the practice of Leetcode 23: merg k sorted lists.

Leetcode 87: scramble string

July 29, 2018

Introduction

It is hard level algorithm called scramble string. I like to review my past practice, and then write a C# solution if I have time.

Here is my last practice. I have not submitted any solution yet.

My practice

I just quickly reviewed the code I studied more than two years ago, and then tried to submitted them using online judge. I will catch up more in the detail later.


recursive solution is here.

dynamic programming solution is here.

Leetcode 97: Interleave string

July 29, 2018

Introduction

It is hard level algorithm called interleave string. The algorithm can be solved using dynamic programming. I like to take 10 to 20 minutes to write the solution for the algorithm.

Also, I start to watch the video from basketballwangcoding, I like his teaching.

Here is my practice using C#, based on dynamic programming.

Leetcode 105: construct binary tree from preorder and inorder traversal

July 29, 2018

Introduction

It is a medium level algorithm. I like to write code for the algorithm.

My practice

I spent over one hour to debug the code and ran into index-out-of-range error, and I finally fixed all the issues.

Here is my C# code.

Leetcode 337: House robber III

July 29, 2018

Introduction

It is the medium level tree algorithm called House robber III. My learning experience covers a few areas. I chose to listen video lecture, and also I read some blogs related to the algorithm, one of blogs I read is served by grandyang.

I spent time to work on the video served by basketwangcoding, and I like to get some help from his lectures.

Plan to write C# code for House robber III.

My practice

Here is my C# code which is verified by Leetcode online judge.

New attitude

I understand that it is very important for me to submit as many algorithms as possible on Leetcode. So I slowed down everything and wrote a solution after I spent over 30 minutes to learn from video teaching from a Facebook engineer and also blog reading.

Algorithm training should be a science, I should understand the idea how to solve the problem first, and then also need to 100% follow the idea by applying my code against online judge.

What is science?

follow up on July 31, 2018
Do  not spend too much time to read the algorithm, once I understand the idea, I should move on the implementation. How quick I can write, how complete solution I can come out to cover the problem? How to find edge case, interesting subproblems through online judge.

I am training myself to be a good programmer.

Leetcode 213: House robber II

July 29, 2018

Introduction

It is the medium level algorithm called house robber II. It can be solved using dynamic programming and also house robber I algorithm can be applied to the algorithm as well.

My practice

Here is my C# practice.

Leetcode 112: Path sum

July 29, 2018

Introduction

It is an easy level tree algorithm called path sum. I spent 18 minutes to work on the algorithm.

My practice 

Here is my C# code.

Leetcode 111: minimum depth of binary tree

July 28, 2018

Introduction

It is an easy tree level algorithm called minimum depth of binary tree. I like to consider two ideas, one is to use breadth first search and then shortest path and then terminate search early. Another one is to use recursive function to do depth first search, to prune the search, if the current depth is bigger than minimum depth found so far, then current path should be terminated.

My practice

Here is my C# code. My first practice failed on one test case. My base case is wrong. I should consider the base case with a node not null, but left child and right child both are null. Null node should not be considered as a base case.

weekend planning - 80 facebook algorithms on Leetcode.com

July 28, 2018

Introduction

It is time for me to make my summer weekend special one. I choose to work on facebook algorithm 80 of them on Leetcode.com.

I will plan to work on a few hours based on the list of algorithms

Here is the list I prepared before.

weekend planning - easy level array algorithm

July 28, 2018

Introduction

It is time for me to solve as many easy level algorithms as possible. So I can review my last two week practice and I will be so happy to know that I solve 50 algorithms in last two weeks, and also I work full time 80 hours last weeks.

It is not easy to move on next algorithm quickly. In order to do that, I have to train myself focus on analysis and coding. Cut emotional baggage for each algorithm, how I feel, what my concerns, I should learn quickly and move forward with another problem solving.

Easy level array algorithms

I like to list those algorithms here. I like to solve 10 easy level array algorithms this weekend. The number of easy level array algorithms is around 45 to 50.

665	Non-decreasing Array	19.9%	Easy
	189	Rotate Array	26.3%	Easy
	414	Third Maximum Number	28.2%	Easy
	532	K-diff Pairs in an Array	28.4%	Easy
	581	Shortest Unsorted Continuous Subarray	29.4%	Easy
	605	Can Place Flowers	30.0%	Easy
	88	Merge Sorted Array	32.8%	Easy
	219	Contains Duplicate II	33.3%	Easy
	840	Magic Squares In Grid	34.3%	Easy
	624	Maximum Distance in Arrays	35.8%	Easy
	26	Remove Duplicates from Sorted Array	37.3%	Easy
	643	Maximum Average Subarray I	37.8%	Easy
	849	Maximize Distance to Closest Person	38.1%	Easy
	1	Two Sum	38.6%	Easy
	724	Find Pivot Index	39.2%	Easy
	119	Pascal's Triangle II	39.3%	Easy
	66	Plus One	39.9%	Easy
	35	Search Insert Position	40.0%	Easy
	747	Largest Number At Least Twice of Others	40.4%	Easy
	53	Maximum Subarray	40.8%	Easy
	118	Pascal's Triangle	41.3%	Easy
	27	Remove Element	41.5%	Easy
	674	Longest Continuous Increasing Subsequence	42.7%	Easy
	746	Min Cost Climbing Stairs	43.8%	Easy
	121	Best Time to Buy and Sell Stock	43.8%	Easy
	628	Maximum Product of Three Numbers	44.8%	Easy
	268	Missing Number	45.7%	Easy
	830	Positions of Large Groups	46.7%	Easy
	661	Image Smoother	46.8%	Easy
	697	Degree of an Array	47.0%	Easy
	167	Two Sum II - Input array is sorted	47.4%	Easy
	217	Contains Duplicate	48.1%	Easy
	122	Best Time to Buy and Sell Stock II	48.6%	Easy
	169	Majority Element	49.0%	Easy
	717	1-bit and 2-bit Characters	49.0%	Easy
	448	Find All Numbers Disappeared in an Array	51.3%	Easy
	283	Move Zeroes	52.1%	Easy
	695	Max Area of Island	52.2%	Easy
	485	Max Consecutive Ones	53.8%	Easy
	243	Shortest Word Distance	54.2%	Easy
	566	Reshape the Matrix	57.7%	Easy
	766	Toeplitz Matrix	58.2%	Easy
	561	Array Partition I	66.8%	Easy
	867	Transpose Matrix	66.8%	Easy
	832	Flipping an Image	69.2%	Easy