Wednesday, July 26, 2017

Find first ancestor

July 26, 2017

Plan to study the algorithm called "Find first ancestor". The blog link is here.

Ways to climb a stair case

July 26, 2017

Plan to study the algorithm called "Ways to climb a stair case". The blog link is here.


Parentheses

July 26, 2017

Plan to study the algorithm called Parentheses. The blog link is here.


Flood fill algorithm

July 26, 2017

Plan to study the blog about the algorithm "Flood fill algorithm". The blog link is here.

Practice depth first traversals

July 26, 2017


Plan to study the algorithm blog called "Practice depth first traversals". The blog link is here.

Can a blog make a difference?

July 26, 2017

Introduction


It is so much fun to have a new school once a while. Julia spent over three months to learn from codereview.stackexchange.com, she was kind of getting lost in the code review but she received a lot of valuable review from JS1. The internet is big world and she never met the person and contacted him personally, the anonymity of user makes internet more interesting.

From March to July, Julia started to meet a person one by one. But she met too many people, sometimes she could not prepare very well for the algorithms used in the mocking. The experience was amazing, this mocking website machine learning algorithm really did great favor to Julia, she could not believe how she connected top talent in the world. It is like inviting people to give you guest lecture every day. Julia learned that good personality really makes life easy as a programmer, so she works hard to reduce her accent, discipline herself to prepare early, learn to be super patient.

Now Julia likes to conduct  a small research on the blog written by Aviad Ezra. Julia likes to go over around 20 algorithm one by one.


Blog study 


First one is about boggle algorithm. Julia wrote a blog on this algorithm. Julia just learned the trie again in June, 2017. The blog is here


Tree contains linkedlist

July 26, 2017

Plan to study the algorithm called "Tree contains linkedlist". The blog is here.

Design cache with auto deletion

July 26, 2017

Plan to study the algorithm called "Design cache with auto deletion". The blog link is here.

Algorithm: Possible Triangle

July 26, 2017

Introduction


It is so challenging to review the code written in October 2009. How to determine if three numbers can be a triangle, which is one with three lines with same length, two of them with same length.


Algorithm practice 



Here is the code to review. Link is here.

Plan to write the function and give some code review the previous one.


Tuesday, July 25, 2017

System Design - Designing a URL Shorten Service like TinyURL

July 25, 2017

Plan to read the system design preview on this site.

It is the important to be specific, not be vague. Julia starts to learn system design from this easy one.


Data structures and algorithms

July 25, 2017

Introduction


It is always a good practice to write down something everyday, maybe 10 - 20 minutes, work on a small research topic. Today Julia likes to review the post from Aviad Ezra on the question.

A small research 




Designing a URL Shorten Service like tinyURL - a very detail preview on https://www.educative.io

Vacation planning 2017

July 25, 2017

Introduction


It is very exciting project to work on 2017 vacation planning. Last year Julia fled flied to China and spent a lot of time to watch China open tennis. She actually did not go anywhere in Beijing a few days, only spent time to watch China open all day long from October 1 to October 3, from morning to the evening 8:00 pm. Most of her favorite time was to watch tennis professional practiced in the evening.

After a short stay in the city of Beijing, Julia will fly back to her home town and visit her family over there.

Vacation talk 


Vacation is fun but also Julia had to deal with jet lag; it is best to live in a nice hotel, and then spend a first 2 - 3 days vacation to overcome jet lag, and also enjoy some sightseeing. The October weather in Beijing is perfect, and Julia has good time to enjoy the city. 

But it is also good to get prepared better, it is very important to get China cellular phone setup, the taxi service through cellular phone will make things so easy and convenient. 


Monday, July 24, 2017

System design: a chat system

July 24, 2017

Plan to read the article written by Aviad Ezra. The link is here.

Power Set

July 24, 2017

Plan to study algorithm blog called "power set" written by Aviad Ezra.

Plan to study Leetcode 78: Subsets, medium level algorithm. The discussion link is here.

Boggle - find words in matrix of letters

July 24, 2017

Plan to study the algorithm Boggle coding blog. The blog link is here written by Aviad Ezra.

There are a lot of thing for Julia to learn through those blog and code sample. Let us read words from Aviad Ezra together in the following:

Learn: Cracking the interview, solve all 189 questions.

Practice: Nothing beats mock interviews. It will boost your confidence and you’ll learn a ton from having someone watching you and listening to your explanations while you solve coding problems. You can pair with a friend or use one of the free peer-to-peer mock interviewing platforms. You don’t need to sacrifice your first interviews just to get hands-on practice.

Think fast: Developers that can think on their feet do much better in coding interviews. Practice in as many competitive programming sessions as you can.

Before you lost hope, keep in mind that there's a finite number of algorithms topics and only a handful of data structures that are used in the interviews.

Those words from  Aviad Ezra are so encouraging, Julia wrote her own blog about "Can mocking make difference?". First time she learns to work with people, share with people, learn from people on small things, like presenting her face in the centre through the video, ask good questions, give good hint, form a quick friendship etc.

In the following, Julia uses Leetcode 212 to help herself review Trie data structure and learn how to apply same algorithm as Boggle classified in Leetcode.



Leetcode 212 - word search II


Review Leetcode 212 last practice using Trie. The link is here.

It is so surprising that learning Trie and practice depth first search is most fun activities in the summer of 2017. Julia has to warm up the algorithm, play with one test case with Trie class, and also make the code more readable. Here is the warmup C# code using Trie data structure, recursive function calls. The solution is optimal and also pass online judge.

It is also a good idea to discuss why Trie is needed for better time complexity.

Brute force solution is to go over each word in the dictionary, and then try to find it in the matrix. The total number of search using DFS is m (words) * rows (matrix) * columns (matrix).

The brute force solution has timeout issue through Leetcode online judge. We like to review why the time complexity should be better.

Let us go over dictionary with 4 words, "aaa", "aaaa","aaab", "aaac". If we pre-process the dictionary and store all words in a Trie, and then we do not have to go over each words to search matrix. We only need to go over each element in matrix as start char in a word, search the trie to find match words using recursive function. The number of search using DFS is rows (matrix) * columns (matrix).

Second advantage related to the above 4 words ( "aaa", "aaaa","aaab", "aaac") is taking advantage of Trie data structure. The space complexity of Trie is better compared to hashset or hashtable. The same prefix "aaa" is only repeated once in the Trie.

This hard level algorithm applying Trie will be Julia's most favorite algorithm in the month of July 2017.

One of practice in 2017 is prefix neighbor on hackerrank, Julia asked the code review on stackexchange.com.


July 26, 2017

Trie against Hashset


Related to the test with a dictionary "aaa","aaaa","aaab","aaac","aaad", let us work together to talk about the difference.

For example, if the dictionary is saved in hashset, then go over each word in the dictionary, try to find word in matrix.
For example, "aaab", the first three letters has to be compared and they are the same first, then the last letter will be checked. Same will be applied to another 4 words. In total, the prefix "aaa" will be compared exactly 5 times in order to find those 5 words.

Can we do better? Just compare the prefix "aaa" once? Cetainly we can. We can save the words in a trie instead of hashset.

a
|
a
|
a
|\  \  \
| \  \  \
|  \  \  \
a  b  c  d



Trie efficiency talk 



It takes some time to get comfortable to design a Trie. So far, Julia has written a Trie implementation more than 4 times in C# last 3 years. Given the fact that she has worked on computer science more than 20 years, if she writes a algorithm every day, then she will write 60,000 algorithms. It is smart to focus on one simple thing, write code for algorithm and data structure, no matter life goes up and down, make it a hobby.

How to design a Trie so that the space complexity is minimum?
For example, the dictionary has the following words, "aaa","aaaa","aaaaa","aaaaaa".
How to store them in Trie efficiently?
a
|
a
|
a   word: "aaa"
|
a   word: "aaaa"
|
a   word: "aaaaa"
|
a   word: "aaaaaa"

The above diagram shows that those four words are saved in a Trie. How many char 'a' are saved in Trie, only 6, not 3 + 4 + 5 + 6 = 18 chars. Four words are saved along the trie nodes.

Every node can represent a word, it does not have to be a leaf node.

It is a smart decision to write down some test cases, so next time when Julia comes cross an algorithm, she can quickly relate to the test cases and figure out the advantage of using Trie.

Coding blog study

July 24, 2017

Plan to study the coding blog written by Aviad Ezra.

System Design: Predict User Purchase

July 24, 2017

Plan to do some research on a system design topic called "Predict User Purchase". 

Julia came cross the system design small talk in Chinese, she likes to look into the design: 

Predict User purchase
(先分析什么因素判断用户买不买这个商品,浏览记录,购买记录,在页面停留时间,浏览这类商品的次数,现在火的top 100商品等等。然后分析架构,
给的答案是首先master slave避免single point failure,用户点击商品后先通过dymanic dns look up找到距离最近的CDN,然后http request传过来给那个cluster的master server, mater本身有cache看看这个请求的结果是不是已经cache过了有的话直接返回(这里cache的是这个请求对应的购物车html页面),没有的话master做负载均衡下传给空闲slave server(rmi call), slave有自己的local cache因为对这个预测结果每个slave cache可以不consistent, 可以不用时刻recon每个不同的server cache。所有的数据存储都用in memory database并设置time to live, 因为这个是一个读取大于写的系统数据也不需要持久化不用支持transaction, scale也更容易。master如果挂了重启就可以,因为都是预测数据丢失了也无所谓。如果要更优化可以在浏览器端也做一层cache,如果用户反复点击同样的商品,就不用每次都make http call了)

Plan to do some research on this topic. 30 minutes a time. 




Maximum Gcd and Sum (III)

July 24, 2017

Introduction


"Maximum Gcd and Sum" is the algorithm related to great common divisor, and prime number technique called sieve of eratosthenes is used in the optimal solution.

The algorithm is the first medium level algorithm in week of code 34 on Hackerrank. Julia spent more than a few hour in the Saturday of July 21, she did not come out the solution to fix the timeout and run time error issue.

Here is the optimal solution after the study of editorial notes.

Plan to do time complexity analysis on test case 1, 400,000 is the length of testing array.


Week of code 34 (II)

July 24, 2017

It is early in the morning 12:09 am. The contest just ended 9 minutes ago. Julia spent a few hours this Sunday from 6 pm to 12 am to work on the contest, but she did not score anything. She did not write any code either.

Sunday went away fast. Julia got up around 9:30 am, and spent one hour to work on the contest, and then she left home around 11:20 am for church service. She came back to home with friends to prepare lunch around 2: 30 pm, and then had good time until 5:30 pm.

It was really hard to work on the algorithm. Julia felt a little sleep around 6:00 pm, and then she spent one hour to talk over the phone.

Julia likes to work on those algorithm next week and catch up more on training. Stay positive.




Sunday, July 23, 2017

Leetcode 347: Top K Frequent Elements

July 23, 2017

Plan to work on Leetcode 347, the algorithm called "Top K Frequent Element".

C# solution using Dictionary and bucket sort. The link is here.

Path Statistics

July 23, 2017

Plan to work on the algorithm called Path Statistics which is expert level algorithm in the week of code 34. The problem statement is here.

Now it is 11:28 pm, 32 minutes before the contest ends.

Julia likes to write some code for this algorithm, and see if she has any chance to score anything.


Magic Cards

July 23, 2017

It is the first expert level algorithm in the week of code 34 on hackerrank.com. Julia likes to read the problem statement and spend 30 minutes to work on the problem first.

Here is the problem statement.

Now it is 6:27 pm, the contest will end in less than 6 hours.

Julia likes to read every algorithm in the contest. It is hard for her to work on the algorithm in such a short time.


Recurrent on a tree

July 23, 2017

It is the hard level algorithm in week of code 34, hackerrank contest. It is 5:24 pm July 23, 2017. Julia plans to read the problem statement in 30 minutes, and do some research on the algorithm in a hour.

The problem statement is here.

Leetcode 581: Shortest Unsorted Continuous Subarray

July 23, 2017

Plan to spend 30 minutes to read the solution of Leetcode 581 Shortest Unsorted Continuous Subarray. The solution link is here on Leetcode discussion section.

Saturday, July 22, 2017

Leetcode 152: Maximum Product Subarray

July 22, 2017

Plan to work on Leetcode 152: Maximum product subarray.


Same occurrence

July 22, 2017

It is the second medium level algorithm in Hackerrank week of code 34. Right now, Julia has to start the algorithm and try to make some progress. It is 10:17 pm. Julia likes the challenge.

Plan to study Leetcode contiguous subarray related algorithms first.

Plan to work on Leetcode 53 (easy) and Leetcode 152 (medium level) first.


Maximum Gcd and Sum (II)

July 22, 2017

It takes a lot of time to move forward with timeout issue on this algorithm. Julia likes to check her progress and stay positive all the time.

Here is her code submission in second time, now it is 8:00 pm, 7/22/2017.




The original points for the algorithm is 25, but so far only 16.4 available for Saturday player. Julia only made 20% of available points 16.4. Continue to work on it!

It is 10:27 pm. Julia worked on timeout issues, now she came cross runtime error issue. Most of her issues are runtime error, only two cases are timeout.



Follow up after the contest


July 24, 2017

The code submitted in the contest is here. The idea used in the algorithm is to find prime factors for each number in the array.


Prime number factors

July 22, 2017

Plan to work on the algorithm called "Efficient program to print all prime factors of a given number".

Maximum Gcd and Sum

July 22, 2017

Plan to work on the medium level algorithm called "Maximum Gcd and Sum".

Analysis and investment of time


It is running late for Julia to work on week of code contest. Julia read all discussions and this medium algorithm only has single digit successful rate after a few days.

Julia likes to do some research to help herself to solve the problem. She could not afford to spend a few hours without gaining some new skills.

She decides to work on a few related algorithm first.

First one is called "Efficient program to print all prime factors of a given number".

Plan to read the topcoder article called "Prime numbers, factorization and Euler function".


Can I be a manager?

July 22, 2017


Introduction


It is a good topic to come into Julia's mind last few days for her next topic of research. Julia likes to do a short research, maybe 30 minutes, maybe more. One research topic is to be a manager. How to be a manager? Julia knows that so many of her friends at Florida Atlantic University back to 1998 to 2006 are managers and principle scientists right now.

It is more interesting to be a manager to manage a software team. One thing Julia likes to study is Amazon principle leadership. She also likes to follow managers on linkedin.com.

Recently, Julia visited her 2nd or 3rd connection with managers title working in Amazon, so she tried to follow every manager in her circle. But she only followed 2 managers yesterday and then Linkedin gave her warning messaging "Jianmin, you've reached the commercial use limit. Please upgrade to LinkedIn Premium Business Navigator, or Recruiter to get unlimited people browsing."

Julia likes to talk about warnings she got in her life last 6 months, and then how she works hard to get back to good standings.

Search for warnings


Julia was busy with her full time job and also training in algorithm and data structure. And then she had a car accident in February, 2017. It is such a surprise, but Julia analyzed the problem before. Every accident there is over 10 times warnings. Julia did not have time to catch them and then the accident happened finally.

Get a good thick skin


Another thing is how to keep up with her siblings. Julia has an elder sister who retired 2 years ago as a high school teacher in China, she has visited more than 20 countries. And she is enjoying life with no worry about working full time or part time. Julia was busy with her hackerrank contest and she also was busy with a lot of sports training ideas. So what Julia does not understand is that how important is to keep up with your family and get more fresh ideas about life and everything. Julia stopped attending church last 6 months and all her activities were limited to home office and office at work, one day she found out that she likes to get into other people's life, so she spent over 6 hours to watch Netflix TV series, she suddenly figured out that is most fascinating creative story in her last 6 months. Julia has to learn how to communicate with people retired with financial freedom, Chinese. Do not get hurt if you are joked how poor as a Canadian and how little wealth you have as a Canadian.


Stand on ground 


Now Julia knows that if she attends the church regularly, talk to her family regularly, she will feel less lonely, spend less time on internet on week days, on Chinese wechat social website, she may have a good sleep the whole week. She can maintain more healthy life style, and also maintain great productivity in other area.


Choose activities more grounded


Julia was busy with mocking interview last 3 months. She practiced more than 80 times. She tried to catch up people skills, learn how to work with people, specially on career growth, technical strength on data structure and algorithm.

Bible teaching is very good on this. Ecclesisters 4:10, if either of them falls down, one can help the other up. But pity anyone who falls and has no one to help them up. 

To gain technical strength, specially improve algorithm and data structure problem solving, you can not do it alone. The efficient way is to get connected to people in more meaningful way. One viewpoint is that Linkedin is not helpful, waste of money; Julia did some research on Linkedin connection, how much contribution comes from linkedIn last 12 months. How she makes connection last 3 months through mocking interview. How much knowledge and skills she gains to work with peers. 

One thing she compared is the difference. She met a person connected through LinkedIn after a meetup whereas she met a person through mocking interview second time or she got connected again through emails with the person after mocking interview. 

Face paralysis research

July 22, 2017


Life is a great teacher, if you live happy and healthy, and get along with friends and family, you will have a lot of lessons to learn. Julia is experiencing a lot last six months, she studies a lot of things.

Aging is the big topic for her to catch up. Julia is so busy with algorithms, Leetcode and hackerrank contest. And once a while she pushes herself to rewrite a program at work and she joked about she is writing a new book because of the code has over 100 pages long. She is such a great writer and she enjoys so much for the great performance of new updated program. She knows that her new schools taught her so many lessons and she was definitely happy to apply everything to her own work.

Recently in summer break, Julia has a young sister who is a college teacher, she shared her story about face paralysis. So Julia has to start to learn how to keep our face healthy, avoid face paralysis.




Mom with a dementia

July 22, 2017

Life is such a great teacher. Julia was taught so many lessons. Last 2 years her 86 old mom lives in 24 care hospital as a dementia senior citizen in China, she visited her mom every year and visited the facility, she knows how hard people are making a living once the aging is really getting those people. She watched her mom progressed from 80 years old to 86 years old, how she was panic four years ago since my sister as a physician told her that she will have dementia. My mom struggled to stay home with a full time care over 2 - 3 years and then finally moved in the 24 care facility in a hospital.

One of videos Julia recorded makes her almost cry to watch is to document her mom only remember her 20s songs but she could not memorize the latest activity. Video is here recorded 3 years ago.

Another video is about her mom to celebrate Chinese new year in 2014.

Last year when Julia visited her mom, her mom was not able to open mouth when some one feeds her. The nurse has to squeeze her nose in order to let her open mouth. And she lays on bed so that the career can feed her food. Life is such a gift for us, we have ability to eat, think and live independently.

Julia was so thankful to her sibling - her sister is a physician, a psychiatrist, she knows a lot about dementia, and helped my mom go over so many years struggle and still being able to live as a human being.


Face paralysis research

July 22, 2017


Introduction


Life is such a great teacher. Julia was taught so many lessons. Last 2 years her 86 old mom lives in 24 care hospital as a dementia, she visited her mom every year and visited the facility, she knows how hard people are making a living once the aging is really getting those people. She watched her mom progressed from 80 years old to 86 years old, how she was panic four years ago since my sister as a physician told her that she will have dementia. My mom struggled to stay home with a full time care over 2 - 3 years and then finally moved in the 24 care facility in a hospital.

One of videos Julia recorded makes her almost cry to watch is to document her mom only remember her 20s songs but she could not memorize the latest activity. Video is here recorded 3 years ago.

Another video is about her mom to celebrate Chinese new year in 2014.


Study 



Recursive function small talk

July 22, 2017

Introduction


It is most favorite thing to do in the world, write a quick and short solution using depth first search, and also in recursive function call. Julia wrote a blog about her recursive function practice a few days ago, called Maze.

Today Julia spent near 30 minutes to conduct a mocking practice, and then she chose to practice one more time.


One more practice 


Given a binary search tree, write a function to return the largest smaller value in a binary search tree. Here is the C# code.

It is the first time Julia wrote this recursive algorithm. She made a few correction through whiteboard testing. And then she argued that the algorithm should work, one thing is to prove that any number returned should be less than given value.


Time to share


It is so interesting that Julia did impress the peer after 60 minutes mocking interview, and the peer asked Julia how she practices. So it took extra 40 minutes for Julia to share her experience. Julia likes to get organized and give good advice to the peer.

Last 3 months Julia practiced the algorithm a few times, and she also used the algorithm as an interviewer. But she did not come out a correct solution first time.

Three things Julia shared her practice:

1. Leetcode 10 - the most important about recursion tree, return A || B || C, A is that b* stands for empty string, B is that b* stands for one b, C is that b* stands for more than once, like "bb". The recursion is in 3 branches.

It is the hard algorithm and Julia interviewed over a few people, only one person is very close to the perfect solution. The code was very clean and almost perfect. Julia learned through the experience, she was interviewed to write the algorithm twice, both of them were not correct, not very close to optimal solution at all. Julia shared honestly her experience on the algorithm.

This algorithm became Julia's most favorite one after she invested so many hours on it. She wrote a few blogs on this algorithm, the one she likes to share is here.

2. Code review on stackexchange website, her experience on code review. Link is here.
3. Refdash mocking interview.

It is the first time Julia was told to adjust the camera so that the peer can see her face impression, in first a few minutes. This is the second time Julia got complaint, first time the peer complained the echo sound, so she decided to use headset.




Friday, July 21, 2017

Do not count wrong doings

July 21, 2017

Introduction 


Bible teaching about love is the most important lesson Julia has. Love is patient, love is kind. One of Julia's favorite bible verse, Corinthians 13: 5, It is not rude, it is not self-seeking, it is not easily angered, it keeps no account of wrongs.  Every time Julia finds her own mistakes, she knows that she has to practice - no account of wrongs

It is still a good practice to talk about mistakes. It takes a long time to learn algorithm and data structure. Julia should complete more Leetcode algorithm after 2 years, so far she only submitted less than 100 algorithms.

Related to leetcode algorithm practice, starting from 2015, Julia found out that best place to find ideas is to go over Leetcode discussion section in March 2017. She searched everywhere, it is best place to read and learn, evaluate various solutions by going over Leetcode discussion.

It is a good practice not to blame yourself, treat yourself as a human being, accept yourself. Learn one algorithm a time.



Leetcode algorithm status report


84/620 Solved, Easy 21, Medium 41, Hard 22.




Leetcode: Meeting Room II

July 21, 2017

Plan to study the algorithm Meeting Room II.

Here is the discussion to review:
The idea is seen in the blog on segment fault. Link is here.

这题的思路和Rearrange array to certain distance很像,我们要用贪心法,即从第一个时间段开始,选择下一个最近不冲突的时间段,再选择下一个最近不冲突的时间段,直到没有更多。然后如果有剩余时间段,开始为第二个房间安排,选择最早的时间段,再选择下一个最近不冲突的时间段,直到没有更多,如果还有剩余时间段,则开辟第三个房间,以此类推。这里的技巧是我们不一定要遍历这么多遍,我们实际上可以一次遍历的时候就记录下,比如第一个时间段我们放入房间1,然后第二个时间段,如果和房间1的结束时间不冲突,就放入房间1,否则开辟一个房间2。然后第三个时间段,如果和房间1或者房间2的结束时间不冲突,就放入房间1或者2,否则开辟一个房间3,依次类推,最后统计开辟了多少房间。对于每个房间,我们只要记录其结束时间就行了,这里我们查找不冲突房间时,只要找结束时间最早的那个房间。
这里还有一个技巧,如果我们把这些房间当作List来管理,每次查询需要O(N)时间,如果我们用堆来管理,可以用logN时间找到时间最早结束的房间。


Here is the Java code to review.

Go  over the leetcode discussion and try to find out good ideas. Plan to study code provided by high reputation engineer Su Yong, code is here. And plan to spend time to read ofLucas to explain the Su Yong's design in detail in this discussion link.


Thursday, July 20, 2017

Leetcode 311: Sparse matrix mulitiplication

July 20, 2017

Plan to do some research on this algorithm called "Sparse vector dot multiplication". 

It is very interesting to learn something from great sharing in Chinese. 

sparse vector dot multiplication,这道题我当时并没有准备到,但是正因为如此,我认为我跟面试官的交流给我加分了不少。面试官首先问我每个vector很大,并不能在内存中存下,该怎么办,我说只需要存下非零的元素和他们的下标就行,然后询问面试官是否可以用预处理后的这两个vector非零元素的index和value作为输入,面试官同意后快速写完O(M*N)的代码,M和N分别是两个vector的长度。面试官说这两个输入如果是根据下标排序好的话应该怎么办,我说可以遍历长度较短的那一个,然后用二分搜索的方法在另一个vector中找index相同的元素,相乘加入到结果中,这样的话复杂度就是O(M*logN)。这时,面试官又问是否可以同时利用两个输入都是排序好这一个特性,我在这个地方有点卡住,但是在白板上写出一个test case,试着用可视化的方法帮助我来进行思考,同时面试官给了一些提醒,最后写出了O(M + N)的双指针方法,成功结束最后一轮面试.

Work on the algorithm based on the time complexity: 
1. O(M*N)

2. O(M*logN)

3. O(M + N)

Read the algorithm on code review

Read the leetcode discussion. Link is here

Coding blog from grandyang. Link is here

Google search, Leetcode 311: Sparse matrix mulitiplication. There are a lot of coding blog on this algorithm. 





Leetcode 15: 3 Sum - optimal time complexity

July 20, 2017

Introduction


It is most challenge work to read a paper related to Leetcode 3 sum, called "Threesome love triangle". 24 pages paper, read 30 minutes a time.


Paper reading 



It is so interesting to learn the algorithm and data structure research. Julia spent over 30 minutes to study one of authors - Seth Petti who works for university of Michigan computer science department. The ranking is very top in USA universities.

Julia joined the community of theorectic computer science on stackexchange.com first time in March 2017 and tried to explore the depth of the knowledge and get more interested in computer science theory. One of her professors is Aaron Meyerowitz in Florida Atlantic University. Julia took set theory math graduate course from 1996 to 1997 in Florida Atlantic university, she had a very small class with a few math graduate student. First time she understood what makes a great professor, just check the problem he works on and how difficulty it is. Julia admires hard work spirit.

What does Julia look for when she browses the research of a professor? She believes that this is one of top-tier theory professor in the world.

Relate to personal research and course study, it is two times decision for Julia to skip mathematics graduate research in her career. In 1989 she chose to change major from math to engineering in Shanghai Jiaotong university, and then in 1996 she chose to change math Ph.D. program to computer science master program in Florida Atlantic University.

Do Julia like complicated math problem? How does she work on her problem solving skills?




Leetcode 486: predict the winner

July 20, 2017

Plan to work on Leetcode 486: predict the winner.

Wednesday, July 19, 2017

Leetcode 179: Largest Number

July 19, 2017

Plan to work on the algorithm which is a medium level called "Largest Number".

Week of Code 34

July 19, 2017

Introduction


It is time to play a hackerrank contest again called "Week of Code 34".

Passion is gone



Julia got her first gold medal in the week of code 33 because she worked hard on the contest.

Now it is time for another week contest, but Julia was too busy in weekdays, she did not have time to work on any algorithm. Another thing she missed is her passion for the contest. Passion is so easy to go away, Julia was busy first two days in the week to review coding practice last 3 months, and the rest 3 days after work, she played tennis Wednesday, and Thursday she rested and Friday she worked on other algorithms.


Sponsor application project

July 19, 2017

Introduction


It is very interesting to work on sponsor application project. Julia started to watch videos related to the sponsor application project, and she started to learn things day by day. She likes the project.

Study 


It is better to write down her most favorite videos about the sponsor application process. 

Why the delays? Link is here

Sunday, July 16, 2017

Leetcode 146: LRU cache

July 16, 2017

Plan to study the algorithm LRU cache through the leetcode discussion. The practice in 2016 is documented in the blog.


Recursive function design talk

July 16, 2017

Train insane or remain the same - Get recursive function training one more time!



Maze algorithm


Given an array, there is only one item is value of 9, all others are 0 or 1. 0 stands for the exit is not availabe, 1 is ok to continue. Make a judgement if starting from (0,0), 4 directions: upper, down, left and right, and see if there is path to find 9.

Plan to study the code written in Java first. The code is here.

Practices


Using queue, the C# code is here.

Using queue, but four directions are written more clearly, C# code is here.

After 90 mocking interviews, Julia knows that it is important to write a short version solution in less than 5 minutes, without any bug. So she decided to write a recursive solution using depth first search, she ran into stack overflow issue. It took her over 10 minutes to figure out the issue, mark the node visited on line 46.

Here is the C# version code using recursive function. The goal is to write in less than five minutes, and pass the test case in less than 10 minutes.

In order to shorten the time to write code, Julia spent hundreds of hours to learn recursive function. One of her most lesson learned through mocking interview is the bug she found, documented in the blog called Leetcode 10: regular expression match.

Ask a vote?


Which version of code you will choose to write? Julia learned the lessons through years, she learned from 90 mocking interviews, she still could not nail down the most important solution using recursive solution in less than 5 minutes, today, July 18, 2017.


Just like a song, Julia you have to memorize the lyrics, you only have 4 sentences to remember. First one is to return false, second one is to return true, third one is to set to 0 as marking visited, and then fourth one is to call recursive function for 4 possible neighbors. In other words, here is the transcript to remember:
Line 8           return false
Line 13         return true
Line 18         maze[row][col] = 0
Line 21 - 24 four recursive function calls concatenated by || operator

Shortest Job First

July 16, 2017

Plan to study the algorithm called "Shortest Job First". There are a list of jobs with execution and arrival time, shortest job will be processed first, and then average waiting time will be calculated.

Problem statement here is in Chinese.

一个处理器要处理一堆request,一次只能处理一条,如果它有几个积压着的requests,它会先执行持续时间短的那个;对于持续时间相等的requests,先执行最早到达处理器的request。问平均每个request要等多久才能被处理。input:requestTimes[],每个request到达处理器的时间; durations[] 每个request要处理的持续时间。 两个数组是一一对应的,并已按requestTimes[] 从小到大排序过。

Plan to study code written in Java first. 



Practice

C# practice using SortedSet, the code is here. 


Fix the bug in previous C# code because the average time should be 3.29. C# code is here, the correction is on line 71. 

Minimum spanning tree

July 16, 2017


Plan to study the algorithm called minimum spanning tree. The problem statement is written in Chinese like the following:

给十几个城市供电,连接不同城市的花费不同,让花费最小同时连到所有的边。给出一系列connection类,里面是edge两端的城市名和它们之间的一个cost,找出要你挑一些边,把所有城市连接起来并且总花费最小。不能有环,最后所以城市要连成一个连通块。
不能的话输出空表,最后还要按城市名字排序输出,按照node1来排序,如果一样的话再排node2。
输入:
{“Acity”,”Bcity”,1}
(“Acity”,”Ccity”,2}
(“Bcity”,”Ccity”,3}
输出:
(“Acity”,”Bcity”,1}
(“Acity”,”Ccity”,2}
补充一句,test case一共有6个。


Plan to study Java code implementation. The link is here

Write C# code based on the above Java implementation. The code has run time error. Code is here

Review Kruskal algorithm to implement the minimum spanning tree. The past practice is documented in the blog

Leetcode 207 - Course Schedule

July 16, 2017

Plan to study Leetcode 207 course schedule again. Read a few solution through leetcode discussion first.

Plan to study Java code. The link is here.



Order Dependency II

July 16, 2017

Plan to study the algorithm again.

It is the great to talk about the algorithm - topological sorting.

How to detect if there is a cycle in directed graph.

Using coloring to determine if there is a loop. Read the introduction of algorithm to figure out.

3 color scheme: white, gray, black

white  - the node has not been visited before
gray    - the node is visited by DFS search
black  - it is visited before, and DFS is completed?

The basic idea is to visit white node using DFS, visit the white node and then mark it to be gray color. If the visit node is black, do not continue. However, it is a gray node, that means the loop is existing because it is second time to visit the same node.

If there is no loop in the graph, all nodes will be marked in black color.

Detail please read the blog written in Chinese, link is here.

Plan to study Java code implementation first. The study code is here.

Order dependency (I)

July 16, 20217

Introduction


The algorithm is similar to Leetcode 210 Course Schedule II. The topological sort is the classical algorithm name. The practice for course schedule II is here.


Algorithm study 



Plan to study Java code first, and then write a C# version code.






Rotate matrix

July 16, 2017

把一个m*n的矩阵旋转90度,给一个flag规定是向左转还是向右转。


Plan to study code written in Java. The link is here

input 
1 2 3
4 5 6
7 8 9

output1
3 6 9
2 5 8
1 4 7

output2
7 4 1
8 5 2
9 6 3


LRU Cache Count Miss

July 16, 2017

LRU Cache Count Miss

Plan to study code written in Java first. The link is here


Round Robin algorithm

July 17, 2017

一个处理器要处理一堆request,一次只能处理一条,每次执行一个任务最多执行时间q,接着执行等待着的下一个任务。若前一个任务没执行完则放到队尾,等待下一次执行。
假设只要有任务开始以后cpu是不会空闲的,也就是说cpu开始后如果空闲了就说明没有任务了,另外Robin Round最后返回值是float。




Java code is here to study. 

Tree Amplitude

July 16, 2017

Tree Amplitude

In a binary tree T, a path P is a non-empty sequence of nodes of tree such that, each consecutive node in the sequence is a subtree of its preceding node. In the example tree, the sequences [9, 8, 2] and [5, 8, 12] are two paths, while [12, 8, 2] is not. The amplitude of path P is the maximum difference among values of nodes on path P. The amplitude of tree T is the maximum amplitude of all paths in T. When the tree is empty, it contains no path, and its amplitude is treated as 0.
For exmaple.

Input:
         5
       /   \
     8       9
   /  \     /  \ 
  12   2   8   4
          /    /
        2    5
Output:
7
Explanation:
The paths [5, 8, 12] and [9, 8, 2] have the maximum amplitude 7.
Code:
public static int amplitude(TreeNode root) is answer, others are helper functions for testing.

Java code is here to study. 

K closest points

July 16, 2017

K Closest Points


Problem:
Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large. You need only use standard math operators (addition, subtraction, multiplication, and division).
Code:


Study code: Java code is here


Plan to review C# practice using SortedSet and ICompare first, and then write a C# code for this K closest points. 



Saturday, July 15, 2017

Coding challenge

July 15, 2017

Introduction


It is very challenge task to compete in less than three hours contest. Specially hour rank on Hackerrank. Julia did a few of Leetcode weekly contests, one algorithm Leetcode 605: Can plant flower, one time she spent over 30 minutes on easy algorithm, but she learned to write a solution after the contest in less than 10 minutes.

How to prepare a coding assessment challenge? How to review Leetcode algorithms? How to warm up a few hours before taking the test?

Challenge 



July 20, 2017
It is important to work on a few algorithms, write some blogs, and document real learning experience. Julia enjoys the algorithm problem solving, she also noticed that she should take some time to review what she learned last 3 months.

Julia spent one week to prepare, she did study a few algorithms and enjoyed most of them. The best one is to work on the algorithm called maze. The idea is to work on simple things, implementation, time to complete the coding, comparison among various solutions, learn to write a quick and complete solution in less than 5 minutes.

She spent last 3 hours to print out all source code she worked on Leetcode last 3 months, almost 30 algorithm. She reviewed all of them one by one, spent a few minutes on each of them. She was so touched by her hard work, she did learn a few things through those practice.

So when she started to work on code challenge, she was very calm. She shifted her focus on things she could control. She felt that she was mature enough for another assessment, since she reviewed and also learned something new. She likes to check honestly if she can handle challenge, solve problems.

Sponsor application project

July 15, 2017

Introduction


To be a competitive programmer, Julia has to train herself plan her time very well. Disciple herself, relax herself, and work efficiently with her limited time and resource.

One of the ideas is to do it yourself. What she has to do is to learn the project she works on. No matter what project is, even if it is not related to the software programming. Julia likes her to learn as a beginner, and then take the risk, work on it 30 minutes a time, one hour a time.

Think about this way, in order to make $3000 net profit at minimum wage job, Julia has to put 300 hours labors, and then she has to spend time on the road to get the place, back and forth, not counting time to prepare meal for the work.

This sponsor application project will be taken by a professional immigration consultant if Julia likes to pay $3000.00 dollar. Therefore, Julia has to work on the case more, invest more time, and get more update with the others.

Now it is 11:09 am, Julia likes to take two hours to work on the case.

Sponsor application project




Friday, July 14, 2017

Leetcode 130: Surrounded Regions

July 14, 2017

Surrounded regions algorithm is very good depth first search algorithm to practice. Here is the C# practice Julia did.

Thursday, July 13, 2017

Can I be a data scientist?

July 13, 2017


Introduction


It is a good research topic for Julia to work on. Can I be a data scientist? Julia works on the small manufacture company over seven years, and she works on the sales, accounting analysis and then she felt so much confident to play with the data. She likes to look into the area she should work on in order to be a data scientist.

Should I learn a new language used by data scientist? Can I create a big impact if I know data science very well. What courses should Julia look into?

Julia worked on a lot of algorithm on hackerrank contests, she had difficult time to work on those advanced algorithm, huge data, she did not have time to play with those data set. She tried to stay on basics, and work on the advanced algorithm or data structure, focus on mathematics instead.

Her experience of over 18 contests tells her something. The data science is nothing new. As bible said, Ecclesiastes 1:9
What has been will be again
what has been done will be done again; 
there is nothing new under the sun. 

Julia, stay focus and work on the foundation of computer science. 




WTA No. 1 - Karolina Pliskova

July 13, 2017

It takes 90 minutes to go over the twitter account of WTA No. 1 - Karolina Pliskova, and Julia started to watch around 12:00 am and she finished around 1:30 am on July 11, 2017. And she did in Tuesday, and she sacrificed some sleep and she had to get up for work around 8:00 am.

It takes some time to figure out how ranking works in WTA. Here is the video to show progress of ranking with points - Karolina Pliskova.

2016 Cincinnati champion   +900
2016 US Open Finalist         +1300
2016 WTA Finals Qualifier  +500
2017 Brisbane Champion     +470
2017 Doha Champion          +470
2017 Indian Wells Semifinalist +390
2017 Miami Semifinalist          +390
2017 French Open Seminfinalist +780
2017 Eastbourn Champion          +470

Julia likes to play tennis, and she met so many top players in China last October. She likes to learn how professional players handle pressure, train themselves.

Know one player a time. It is such great time to learn a new No. 1 player.

Julia also spent over 15 minutes to study No. 1 website, figure out if the design is good one or can be better based on her experience.

Difference talk between two algorithms: Leetcode 200 and Leetcode 547

July 13, 2017

Introduction


It is interesting to look into two algorithms: Leetcode 200 and Leetcode 547, what is the difference?
Julia likes to answer the question and see if she can find something to work on later.

The depth first search using recursive function, check deadloop, mark visited node, it is always most short and quick solution.




Tuesday, July 11, 2017

Sponsor application project

July 11, 2017

Introduction


It is the interesting journey to file a sponsor application project as a Canadian citizen. It is a lot of work and take some planning.

It is getting better to work on paper work preparation. But it takes some time to get more familiar with the process of the application.

Julia decided to file the sponsor application herself one week ago. Since she started the project last July, Julia knew that the most important thing is to prepare early and work hard to learn the process. Almost 12 months passed, Julia decided to stay focus on the task one or 2 weeks, stop working on algorithm practice, mocking interview, and then spent more time on her application.

Being a competitive programmer, there are a lot of things to learn. It cannot be finished in one or two weeks.

Her favorite philosophy is so surprising to match the following reading she had recently. She likes to share here and it may bring some good thoughts for future work. Why a software programmer should consider cooking at home?

From the article: Cooking At Home.

If weight loss is your goal, you’ll get better results by simply cooking everything at home and counting your calories. Exercise is great too, but it’s not nearly as effective as diet.
America is this bizarre place where everything we do seems to get filtered through some corporate entity that charges a convenience fee. Over the course of a lifetime, those convenience fees add up and result in each us spending more of our lives mandatory working for someone else.
We want a refreshing drink, so we buy a Coca Cola. But Coke has sugar and calories that make us fat, so we decide to get a gym membership to burn them off. Then we decide we need a nice new car to get to the gym, which adds all sorts of fees and insurance. It’s even worse if we decide to buy that car on credit — many of us do!
Most of our problems stem from a few simple choices. Those choices create a vicious cycle of consumption that forces us to spend our lives on things that don’t matter.
What happens if we drink water instead? What if we go on a run outside, or buy a cheap set of weights? What if we decide to walk more places instead of driving?
This is an article about cooking, but it might as well be an article about taking more control of your life in general.


Lessons learned



A smart programmer learns to write great code, but she likes to learn basics as well. Like cooking at home, and sports. She likes to learn to write down her lessons one a time, she likes to break a vicious cycle starting from 17 years ago.

Back to 1999, she only has 2 miles to drive to work, she bought a brand new car, sports utilities vehicle, even though Florida is such a flat terrain area to drive, and it is on the credit, a factory loan from Ford company. And she bought a 3 years Bally gym contract, she only showed up less than 20 times in 3 years. One time she got 20 dollars class inside the gym.

Back to 2008, She did take three time IELTS tests in 2008 in order to meet Canada immigration minimum score. She did 3 times in a row in 3 months time range and she achieved her goal. And six month later she got denial application result, then she started to appeal case over 10 months from January to October 2009, she did almost flunk her appeal against Canadian Federal court even though she did everything by herself, but she won the judge approval for a court date in June 2009.

Back to 2009, Julia got an offer to pay 1000 dollars and the immigration lawyer will write a letter for her to the immigration department to appeal her denial of decision in January 2009. Julia decided to write a letter by herself, and filed an appeal case by herself in 60 days after the denial. She worked on the appeal for leave more than 10 months, and got settle offer in Sept. 2009. It is a miracle that Julia did not go to the court and settle down outside the court. The statistics shows that 90% of case settles outside the court.

Through the immigration lawsuit, Julia knew how important it is to work with people very carefully, and gain the trust and support from the people. First time she understood that how important a judge can make a difference in her life. The Canadian immigration judge gave her a chance to go to the court even though she just learned to file the lawsuit document by herself, she studied over 20 immigration lawyers website, case studies. She tried to write down notes to help her to find laws, facts, where are the good arguments. It was so much fun to work on her own case through those months, she learned the first time she had to write document each step, and stayed focus on each step.

She understood that it is most important thing in the life called immigration, and it is very important to study every detail by herself even if she decides to ask the help from the full time consultant.

In 2017, Julia chose to work for herself instead of using licensed immigration consultant for sponsor application.

Best teacher is to learn your own mistake, experience failures, she likes to get the application file again as soon as possible. And also she likes to write down her process, so she can overcome her procrastination problem, learn how to get into the zone of filing, and preparing process.

Julia wrote a blog on July 1 Canada day, and then shifted her focus on the sponsor application instead of Hackerrank contests, and Leetcode algorithms, and mocking interviews after work and weekends. Being a responsible person, make a plan, and follow through the plan. That makes a person success, it does not matter if the project is algorithm and data structure practice, or other thing like sponsor application.


Leetcode 547: Friends Circle

July 11, 2017

Plan to work on Leetcode 547: Friends Circle. The problem statement is here.

C# practice using depth first search is here.

JavaScript study code is here.

Algorithm talk 


It took Julia over 20 minutes to think about this medium algorithm. One thing Julia likes to do is to study over 10 implementations, and then write them using C# one by one. And also try to figure out the best way to identify the problem as a depth first search algorithm, and separate from advanced algorithm, time-consuming implementation.

Learn a few ideas of classical algorithm implementation, like disjoint set, union find algorithm. Review the past practice as well.

Study one of C++ solution, the link is here.
Write C# solution - link is here.

Disjoint set implementation in C#, link is here.

Leetcode 200: Number of Islands

July 11, 2017

Plan to study Leetcode 200.

Plan to go over union find alogorithm on this discussion link.


Leetcode 49: Group Anagrams

July 11, 2017

Introduction



Group anagrams is Julia's favorite algorithm 5 months ago. Julia asked the question on the code review site, here is the link. So far, there are only 102 views. Here is the coding blog about the practice on Feb. 4, 2017.

Plan to go through the discussion of Leetcode 49 group anagrams algorithm. It is the great learning experience to go over difference ideas, and practice one by one using C# programming language.


Algorithm study 


Here is one of the C# practice. The idea is very simple, sorting the char array so that the anagram string can match the key of hash table. 


Sunday, July 9, 2017

Am I good programmer?

July 9, 2017

Introduction


It is exciting to spend 30 minutes to do some research at the night of Sunday. The topic Julia chose is "Am I a good programmer?". Julia likes to be very competitive hackerrank contest player, good at computer algorithm and data structure. But also Julia likes to be a leader, enjoy the journey by sharing her struggle, learning process of hard topic on algorithm, data structure. How does she advance herself as a software programmer, learning as a system designer, and she also likes to pick up other skills. Like good humour, strong and healthy physical body and strong mental toughness, and good sense of humour, master a sports - tennis.

Julia made a few choices, chose to work on Leetcode algorithms, work on the coding blog, work on code review, Leetcode discussion. 


It is hard work to reinvent myself as a software programmer. Julia spends last 3 months to meet people and conduct mocking interview, in her career as a full time programmer last 7 year, it is the first time she starts to learn how to work with a peer through 60 minutes time range. She wrote a blog about common mistakes in mocking.

Last weekend Julia spent more than three hours to watch the show on netflix called Quantico, the actress Priyanka has more than 17.9M followers on twitter. Julia likes to spend some time to read how the actress develops skills and build a good connection with peers. The actor Jake wiki page is here.

Coding, learning algorithm, reading and also mocking, Julia starts to get good habit to practice daily. But it is better to take Sunday off . Say no to algorithm and data structure, mocking interviews on Sunday, learn to relax more in the summer. Also Julia has to spend time to work on the sponsor application project.

Julia still calculates how much time she spends on the internet in the week days, she did waste a lot of hours. Instead she should plan better to work on more meaningful activities, like attending Sunday church service, get connected to friends and family, play more sports like tennis single matches, make life more fun and exciting.


Study topic 



It is the great experience to serve 8000 views last month. Most of time the blog serves Julia very well, she has chance to keep tracking of her progress on algorithm and data structure, and also keep her motivated and focus very well. So far there are over 150,000 views on the blog.

Over 10 years ago, Julia spent over 3 months in 2006 to study how to apply teaching job but she never got too far. She remembered that the bible verse teaching about seeds, how to grow the confidence. Seed and soil, Matthew 13 - The Parable of the sower.


Julia spent whole month in the city of Canada, so 25% traffic is from Canada. In other words, Julia serves 75% traffic for other people while she enjoys her own blog with 1700 views. 



By integrating Leetcode with mocking interview algorithm, Julia also learns to serve other people, help herself as well to learn better on algorithm and data structure. Here is the list of Leetcode algorithms last 3 month Julia worked on. Also 30% of peers were happy to connect Julia on linkedin, total count is 33. 

The mocking interview totally changes the view of Linkedin, for a long time, Julia found out that she does not have time to get connected to people face-to-face, work on something together. 


Let us look in LinkedIn statistics and figure out something here as well. 


Julia spent time on mocking interview last 3 months, 90 mocking takes 90 hours; And Julia worked on related Leetcode algorithms more than 30 hours. She added 33 new Linkedin connections, total 201 views, 15% traffic is related to the new connections. 26 found you via Who Viewed Your Profile, in other words, Julia did some study on linkedIn profiles, 10% traffic is related to the activities. 75% traffic of 150 views are random traffic, Julia could not control and make some influence on it. 

Last 3 months Julia did not spend a lot of hours on code review. Here is her profile:


Julia found her most favorite website to study and get great ideas for algorithm, and learn C# programming, for example, C# class SortedSet is good to start. . It is called Leetcode discussion board. Here is Julia's profile on Leetcode discussion. 
A few issues needs to be addressed, but Julia will find time to solve them. 


Leetcode algorithms



Last 90 days, Julia worked on 52 leetcode algorithms. Here are the list:

52 Leetcode algorithms 

Leetcode 10 regular expression match
18

23

33
37
39

44
45
47
48

54
55
57

69

72
76
78
79

114

121
122
123
128

140

151
153

189

212

220

239

295

300

416

459

480

516

551

572
575

582
591

605
606
609