Monday, January 8, 2018

Leetcode 684: redundant connection

January 8, 2018

Introduction


It is another 10:00 PM mock interview. I asked the peer to give me another algorithm for interview, and he gave me the algorithm Leetcode 684.


Algorithm analysis


It is very good discussion between two peers. I shared the transcript here.

Here are the search results of union find practice in my past 12 months. I have practiced over 6 times union-find algorithm on Hackerrank.

Mock interview


Mock interview can be such a good activity, I thought about hiring a tutor met on mock platform, and then sent messages and talked to a few Chinese graduate student met on mock platform, none of them showed the interest. I know that I am out of date on this tutoring idea.

So I just go for the mock interview, if I meet a strong talented peer, just ask the peer to give me a tough algorithm to work on. The peer chose this one and it is the medium level. After the mock interview, I went to bathroom and looked at mirror, I almost cried since I felt that a drop of tear came out. Life is tough, mock interview is tougher than hackerrank contests. You have to push yourself to understand the algorithm, ask good questions, and then argue to myself to define the problem related to the given example, solve a well-defined simple problem. This algorithm can be solved with the experience of the union find algorithm. I do have over 10 times to work on the union find algorithm last 12 months by tracking coding blog, I played contest, asked code review called value of friendship, and practiced to write C# code, but I still miss the important part, solve the problem and present to the peer.

In my mock interview, I read the problem statement loud, 2 or 3 times, in order to understand the requirement, and then I told the peer that the graph has a cycle, we have to determine if there is a cycle. Usually the depth first search can be conducted to explore the graph.

We can go over any node and then start from it to do depth first search and determine if there is a cycle. One thing is to go back to the root node.

After 10 -15 minutes discussion, I told the peer that depth first search may not be necessary, I saw that the algorithm can be solved just using hashset or hashmap.

My personality


Definitely I have some personality, and then I have to figure out what to do with it and make most from own personality. One thing I noticed is the pressure from the peer. Usually the programmer working in silicon valley has more pressure, the peer may prepare onsite interview of tier 1 companies. It is hard to be the peer and relax all the time.

One thing I like to do is to review the Chinese blog about union find algorithm, and write down notes, and write an English version blog. I really find the blog author is such a good writer and work hard to present nice and rich graph to explain the algorithm.

I could not tell the quick find and union find difference right away. And also my mock interview algorithm does not require me to work on edges in detail, just need to check if it is in the graph or not. I tight the constraints to make my problem hard to solve.

Here is the blog about union find algorithm.


Quora post


The things to work on from a facebook recruiter quora.com answer. The link is here.


Follow up 


March 14, 2018

Plan to read disjoint-set data structure wiki article.


No comments:

Post a Comment