Monday, April 30, 2018

System design: Messenger service like whatsapp or wechat - interview question

April 30, 2018

Introduction


It is so good feeling to watch a 25 minutes system design video again. The title is called Messenger service like Whatsapp or Wechat, here is the link. The author is an Amazon software engineer Ramon Lopez.


Code review: Array quadruplet

April 30, 2018

Introduction


It is so happy for me to continue to practice Array quadruplet algorithm since last March. What I have learned through over 10 rounds mock interview is that I have to continue to learn the algorithm through each practice.

It is the big surprise when I chose the algorithm to ask the peer last Saturday 10:00 PM mock interview. I tried to test a senior in the university how good he is since he told me that he had ICPC contest experience in high school.

Build a hashmap on the fly


I like to answer my own question asked five months ago on stackexchange.com. Here is the question's link. Here is my answer's link.

Leetcode 4 sum discussion panel


I have to push myself to learn from others. One drill is to read as many discussion as possible, and try to figure out new ideas, creative thinking process. I spent 30 minutes to read through the discussion, and also wrote a reply. Here is my reply link.

I noticed that I had some issues, since I keep checking code review my answer link. I know that it is waste of my time. I should spend time to read more discussion on Leetcode 4 sum.

Sometimes I notice that I have to push myself to show concern to others, people in the community, and also give out support for other people's good thoughts and work they share.

To be selfish or pessimistic, it is not working very well in this fast-paced software industry. This is the first time I make this argument.


Here is my post to show my idea and answer for Leetcode 18: 4 sum. I did spend 30 minutes to read my submission eleven months ago and then I decided to write a new solution based on my practice on array quadruplet.

One step further


Here is the reply I gave to the most view answer 6.1 K views. I shared the tip to lower down the time complexity to O(n * n).




Sunday, April 29, 2018

Being interviewer: Array quadruplet

April 29, 2018

Introduction


I had a mock interview with a young undergraduate student with ICPC contest experience. So I like to ask him to solve my favorite algorithm Array quadruplet. I think that he did one on dynamic programming, and then I tried to evaluate how good he is.

Biggest surprise was that he gave me the solution I could not understand. And then I asked him a few question, ask him to explain using example. He did perfect job to explain the algorithm.

It turned out the algorithm is optimal solution. I like to post the answer for my own question asked more than 6 months ago. Here is my question link.

Mock interview


Here is the algorithm the peer wrote. At the end of interview, I asked him to connect to linkedin, it turned out that he worked for facebook as an intern already.

I could not believe that my mock interview practice was so many surprise and I just enjoyed the talk. Somehow I complained to the peer that I do not want to study so many system design interview, I do not want to try to memorize so many things, I like to work on the algorithm with the peer on mock interview instead.

We met and talked about one hour fifty minutes until the mock interview terminated the discussion. I could not believe that I enjoyed the discussion of the algorithm so much, I never expected that I will meet a super talent later in Saturday evening.

Time complexity


The algorithm provide by the peer is better on time complexity, since the two sum preprocessing is conducted on the iterating of the array in the same time, what ever in the hashmap should be with smaller indexes. We do not need to go through the list of the items in the key value since any one of them will work. 

It is similar to all other algorithm like merging 2 packages


Feedback from the peer


You just do as you do in the mock interview practice session, you should be able to do fine in any interview. That is my advice.

Being interviewer: Leetcode 152 Maximum product subarray

April 29, 2018

Introduction


It was my 10:00 pm mock interview. We both finished our algorithms in first 30 minutes. Then we spent extra one hour 20 minutes to work on algorithms together. I asked two algorithms for the peer to solve.

Here is the first algorithm called Leetcode 152: Maximum product subarray

Mock interview


The peer worked on the solution, and then we had discussion and then our discussion lasted more than 30 minutes.

Here is the transcript.

The peer wrote a brute force solution in less than 2 minutes, code is from line 54 to line 64. Two days ago, I helped a young undergraduate student to work on the brute force solution more than 10 minutes. What is big difference. I was so amazed and could not stop expressing my biggest surprise.

And then we had discussion about optimal solution using time complexity O(n). I tried to explain to the peer that his algorithm is not so good since it could not apply to the double array. And then he said that if it is a double array then it is another problem.

One more argument we had is about the algorithm he proposed from line 88 to line 112. The problem is that I could not understand his algorithm, I was too lazy to think and I need to run a simple example first.

I decided to give out the hint, I wrote the hint from line 32 to line 45. I like to introduce the dynamic programming algorithm, and help the peer to follow the idea.

And then the peer continued to work on his idea, he wrote down the notes from line 66 to line 86. The peer is very good at writing pseudo code and explain thing.

He did told me that he worked on ICPC contest in high school, and he found out that mock interview algorithms are easy etc. We talked about codeforce contest etc.


Being interviewee: H-tree

April 29, 2018

Introduction


It was so nice to have a mock interview at 10:00 PM. I had chance to work on H-tree algorithm, and then I wrote a test case based on the advice of the peer. The peer finished his algorithm open bracket less than 7 minutes, I said so many good things about his performance; and then I told him that once I finish my algorithm, I will ask him a few algorithms and see how good he is. I finished my algorithm in less than 20 minutes.

Mock interview


Here is my C# code.


Being interviewee: Open bracket

April 29, 2018

Introduction


It is my April 28 8:00 PM mock interview, I need to write open bracket algorithm.

Mock interview


Here is my C# algorithm.


Being interviewer: Root of a number

April 29, 2018

Introduction


It is my learning experience to be a nice interviewer to work with a second year undergraduate student who studies in NIT university in India. The peer asked me the hint to solve the root of a number, so I explained to him the algorithm using line 59 to line 66. The peer was very smart and then he came out the idea to apply binary search.

Mock interview


I was not a very nice interviewer, I surfed my internet to read something about system design interview. But later on I noticed that the peer wrote a very good binary search algorithm. Better than I did when I worked on binary search algorithm first ten times last year.

Just share the fact that I have worked on binary search algorithm over 50 times last 12 months.

But this time the peer and I worked together over five minutes, we could not find the bug. It turned out that Math.pow(base, n) call is wrong, base and n two arguments are switched in the order.

I could not believe that I need to train myself hard to do trouble shooting. I need to train myself to think logically.

Here is the transcript with C++ code. I was so patient and let the peer worked on the algorithm first 40 minutes or so.





Being interviewee: Merging 2 packages

April 29, 2018

Introduction


It is my April 28, 2018 6:00 PM mock interview. I had to write the algorithm called Merging 2 packages. I also met a peer who works in Silicon Valley, and he asked me where I practice the algorithm, so I wrote down a few places I practiced.

Mock interview


Here is my C# code and also a few lines of notes to share my experience. The peer also shared system design link and he strongly recommended it to me.


Saturday, April 28, 2018

Being interviewee: Find smallest substring containing all keys

April 28, 2018

Introduction


It is my algorithm called find smallest substring containing all keys. I was so happy to write a perfect solution in 30 minutes, but I noticed that I had to slow down, work with the interviewee since he was not so strong in terms of coding. I may have to focus on the explanation of the algorithm, and also work on a small example to walk through the algorithm.

Mock interview


The peer actually asked a few questions on the test case I chose. After that, he asked me to give him some advice how to prepare algorithm and data structure interview.

I gave 5 minutes talk at least, and also wrote down some notes.

Here is the transcript.


Being interviewer: Array quadruplet

April 28, 2018

Introduction


It is my job to be friendly to the peer no matter the peer can solve the algorithm problem or not. The algorithm is called Array quadruplet. The peer was nervous since he spent time to write a test case first, and then tried to write a brute force solution after 12 minutes past. I stepped in to help and explain how to write a brute force solution.

Mock interview


I understand that the peer needs more practice on mock interview. As an experienced interviewee, I  will work on small test case, and ask for hint if I cannot solve the problem.

Here is the transcript for our discussion. The mock interview was such great experience.


System design interview questions: DESIGN A PARKING LOT

April 28, 2018

Introduction


It is time for me to watch a system design interview asked at Google, Facebook. Here is the video link. It is 29 minutes video, I finally found time to complete the video from 9:18 PM to 9:47 PM.

System Design

The lecture is very structured. Let me write down some notes.

 Abstract Vehicle
 - string licensePlate
 - enum color

Car implements vehicle, same applies to MotorCycle, Bus, Truck. The size of car is Small, Medium, Large, Extra Large.

class ParkingLot(zipCode: int)
- Spot: placeVehicle(vehicle vehicle)

class Spot(id: Long, size: enum)

4 stacks
  placeVehicle  + put in hashMap
   O(1)
  Spot: removeVehicle(vehicle:Vehicle)
     -> Lookup hashMap





System design introduction for interview

April 28, 2018

Introduction


Learning system design is kind of challenging. What I like to do is to watch a few videos on youtube.com first, and then I like to come out the idea how good those videos are.

This one I chose to watch is made by an Apple engineer. Here is the link. Let me rate this video as 10 out of 10.

I like to write down those topics I need to learn basics.

System design


Here are some notes I like to write down.

Ask good question. What features to work for, how much to implement.
Don't use buzzwords.
Clear and organized thinking
Drive discussion (80-20 rules)

- Features
- Define APIs
- Availability
- Latency performance
- Scalability
- Durability
- Class Diagram
- Security & privacy
- Cost effective

Let us move on the topics for system design:

- vertical vs horizontal scaling
- CAP theorem
- ACID vs BASE
- Partition/ Sharding Data
  - consistent hashing
- Optimistic vs pessimistic locking
- Strong vs Eventual consistency
- Relational DB vs NoSql
- Type of NoSql
   . key value
   . wide column
   . document based
   . graph based
- Caching
- Data center/ Racks/ Hosts
- CPU/ Memory/ Hard drive/ Network bandwidth
- Random vs Sequential read/write on disk
- http vs http2 vs websockets
- TCP/ IP model
- Ipv4 vs ipv6
- TCP vs UDP
- DNS lookup
- Https & TLS
- Public key infrastructure & Certificate Authority
- Symmetrix vs Asymetric key


Being an interviewer: Meeting planner

April 8, 2018

Introduction


It is the algorithm to find the overlap in two intervals. And I like to learn from the peer how he solved the problem first time with the correct algorithm, and also very good skills to write Java code.

The peer has very good working experience to work on biggest software companies in the world, China and USA. I had good understanding the programmer who worked for Tencent, Amazon and Microsoft, compared to my first practice, he is much better and also strong in the analysis of the algorithm.

The algorithm is challenging and very time consuming even for the top talent programmer in the world first time.

Mock interview


Mock interview is fun and I watched a few times through the video, how the peer got family support and work on the mock interview very hard, since his wife passed by behind in the living room. So I talked to the peer that relax, let me play with my medicine ball, take your time to come out the correct algorithm.

The peer was very busy to come out the overlap calculation, and also go through the discussion of advancing the pointer of one slots.

Here is Java code I reviewed. I also like to point out the analysis is perfect. I like to use it as my reference to come out the analysis.




Being an interviewee: Flatten dictionary

April 28, 2018

Introduction


I had 10:00 AM mock interview this morning and I had to work on flatten dictionary algorithm. What I like to do is to avoid memorizing the solution, but I like to learn something from this mock interview.

I cannot believe that I met a peer who had work experience in China, Amazon and Microsoft, :-) I found out after mock interview. But in the mock interview, I still have issues to write down the code, a few of them, I like to work with the talent programmer in 30 minutes. I spent at least 5 minutes to write down the analysis, and then worked on coding around 20 minutes. Last few minutes I worked on bug fixing, code cleaning. I ended my algorithm in 28 minutes.

Mock interview


Let me write down what issues I came cross in the mock interview. Here is my C# practice code with the analysis.

1. I need to look up stackoverflow, and then find C# code:
type check to see if value object is Dictionary<string, object>

2. I need to handle prefix function argument. The definition of prefix is kind of confusing, in algorithm analysis, I did not write down the detail of the design. But in mock interview, I had to play with the code, and then I had a few minutes discussion with the peer. And then I cleaned up the code, wrote three lines of code: line 36 yo line 39.

3. I need to move out the code related to newKey (line 23 to line 27) outside if statement line 29 as the peer advised. I need to remove the redundant code.

Actionable Items


I have 300 mock interview experience, but I still have to learn something each time to work on mock interview. What are those things I have to work on?

I could not believe that I like to practice mock interview, even this Saturday, I have to work on tax return, system design. I still book a few mock interviews to keep myself busy and learn something inside my small home office.

It is time for tax return

April 28, 2018

Introduction


I like to write a few sentences for my tax return of 2018. I really like the Canadian immigration department did good job to process my sponsor application and also the related principle applicant job. As a Canadian citizen, it is my turn to file the tax return in time and also get some help from my friend Jessie this Sunday.


Counting down the time


Let me count down the time. I like to start to work on it 30 minutes a time.

April 29, 2018

I spent over two hours to go over the documents, review my rental business, and also other documents. It takes me a lot of effort to understand how I performed last year in the city of Vancouver.


Object oriented design interview question: Design a Car Parking Lot

April 28, 2018

Introduction


It is the Saturday morning. I browsed some wechat posts and then moved on this 30 minutes video. Since I came cross this quora post first, how to approach object oriented design questions in programming?

Here is the link of 30 minutes presentation.

Design is getting easy


I like to learn design and relate to my current job experience.

Time I spent is from 8:30 AM - 9:00 AM. I like to play the video again and write down some notes here.


Friday, April 27, 2018

Cap theorem and system design

April 27, 2018

Introduction


It is my task to study system design and I am planning to write 10 blogs related to system design study. One is to study CAP theorem and learn that it is important to consider CAP theorem in system design.

I like to learn first, reading is the first step. I read some funny story about CAP theorem today, so I found one with more technical detail. Here is the link.


CAP theorem 


I still remembered that I got second interview on interviewing.io, and the interviewer told me that I should start to work on system design. Cap theorem is one of topics he told me to work on first.

What is CAP theorem?

Among Consistency, Availability, Partition-tolerance - pick any two.

Here is the answer on quora.com, here is another answer for CAP theorem related to ACID, SQL, NoSQL.


Yup education software startup study

April 27, 2018

Introduction


I like to do some research on education software startup. The company is named as Yup.com. I had two mock interview on April 26, 2018 evening. First one is at 8PM, I met a peer who works for Microsoft and stayed in California area. And then I had a mock interview as an interviewer at 10pm, I met a programmer who stays in California as well.

I was so glad that I have time to reach out to people and then have time to work on algorithm and data structure together. It is also good time for me to learn more about startup companies in silicon valley area.


Short research


I plan to do research like 20 - 30 minutes.




Good news of my sponsor application

April 27, 2018

Introduction


It is 12:14 AM. 14 minutes past 12:00 AM, I need to stop working and go to bed to prepare for tomorrow's work.

I like to write down good news, I got emails from my sponsor application for my nephew on April 25, 2018. The principal application is updated with physical examination and other documents.

I need to spend time to catch up all related issues.

Being a very good sponsor


I like to be super talent sponsor. Actually I have to read the document and understand the process first. I need to provide document as well as a sponsor.

Proud to be a sponsor


I know that life will give me a surprise if I choose to give up a lot of things in my life. I start to give up a lot of things in my life after I got in Canada.




Be humble and stay positive

April 27, 2018

Introduction


It was a busy week, I had one week vacation from April 12 to April 18. I came back from China vacation last Wednesday, and I enumerated my three mistakes after I came back from vacation.

I like to get myself time to recover, specially on my hay fever, coughing problem and also jet lag etc.

My three mistakes I shared multiple times, I just like to share that I am a human being. I need to forgive and also be forgiven.

First mistake I had is that I took the skytrain from Richmond airport to water front station in April 18 after I got off from international flight over 10 hours, I got on skytrain around 1:30 PM, I fell sleep on my seat but I was safe with my luggage and handbag. When I woke up around 2:20, I was back to one station to Richmond airport, another direction.

Second mistake I made is that I called the second day after I got back from China vacation, I had to go to office later, and then I noticed that my computer showed that it is Thurday August 19. I got extra 15 hours since time difference between China and Canada. I still have one more vacation day since the time difference.

Virus software 


I experienced the virus software malfunction issue. This Monday I was so busy to recover from the bug on my daily duty website maintenance. I had to deal with the issue, the commercial virus software found a virus on my database file, and then deleted the file last Friday. I was luck since I came back my vacation last Wednesday, I had time to recover since I was in the office whole week, I fixed temporary until Tuesday we decided to remove virus software from website database server.

Let me write down some virus threat information here:



Source: AvastCloudCare
Description: AV has detect a threat.

Virus_action2: "DELETE"
virus_type2: "MALWARE"

threat_description: HTML: HideMe-F[Trj]
virus_action2: DELETE
virus_type: MALWARE


The commercial virus software makes this kind of error? Unbelievable! I am confused and then spent more than one hour to look into this virus called HTML: HideMe-F[Trj].


Thursday, April 26, 2018

Being interviewer: Leetcode 152: Maximum Product Subarray

April 26, 2018

Introduction


It was very nice experience to be an interviewer. I helped the interviewer learn a brute force solution first and then we had very good discussion on the optimal solution using dynamic programming. The peer is preparing Google phone screen, I may come cross a Google future employee this time.  I met a senior undergraduate student who also works full time for a startup company in silicon valley area.

Mock interview


Of course I could not tell from the person how good she will be, specially when a peer is undergraduate student. But it is very easy to communicate with the peer.

Here is JavaScript code we worked on together, around 60 minutes. I also had chance to learn JavaScript from the interviewee.

I also learned from the peer. I challenged her code using comment line 63, I told her that line 68, temp_max *= arr[i] * arr[j], and then she added a few lines of comments from line 64 to 67, and then I understood her idea to use dynamic programming. She fixed the bug, and line 68: temp_max *= arr[j], arr[i] is removed from the product.





Being interviewer: Busiest time in the mall

April 26, 2018

Introduction 


It is my 8:00 PM mock interview. I was the interviewer and then I learned most important lesson. No matter how many years you work, what company you work for, you have to go through the learning process by yourself in order to be a very good problem solver.

You can be a senior developer, you may go through Google onsite, but you still have to work on those foundation algorithm, practice and get good feedback, work on improvements.

I did not copy the code written in C#. But I experienced the pain the peer went through and struggle he had.

Mock interview


It was the great experience for me as well.

Being interviewee: Matrix spiral copy

April 26, 2018

Introduction


It is my most favorite algorithm called Matrix spiral copy. I told the peer that I like to write a solution to automate direction change but use extra array to store visited information.

I was nervous since last time I wrote the solution was months ago. I am kind of memorizing the solution. What I did is to use wisdom learned through 300 mock interview experience, I tell the peer that I like to visit first row 5 elements 1, 2, 3, 4, 5. How will I do it?

Mock interview


I had discussion with the peer and the peer questioned me the problem I had to visit first element 1 twice. I missed the reset of row and column variables from line 44 and line 45, and also line 42 to set visited array on nextRow, nextCol true.

How come I discussed the solution with the peer with 2 most important task missing? I told the peer that my code will pass all test cases.

I failed last test case and then I noticed that I need to add line 44 and line 45. I need to reset row and col variables. And then I still failed another test case, I noticed that I need to set visited array; and then I still failed the test case, I noticed that I need to set [nextRow, nextCol] instead of [row, col].

What a mock interview!

I need to structure my mock interview better, guard with the whiteboard testing.

Here is my C# code.

Good thing is that I spent less than 20 minutes to write the code with the analysis. The bugs is very easy to fix and code is minimum. It took me less than five minutes to fix all the bugs.

The challenge part is to write correct code and do whiteboard testing by myself.


Wednesday, April 25, 2018

Being interviewee: Word count practice

April 25, 2018

Introduction


It is my favorite algorithm but also it is hard to write a complete solution in 30 minutes. The algorithm is to lower the sentence, remove special char \', and then split words by delimiters such as chars in the string " .:;,!", and then save the words to the dictionary, and then sort them by value. From the dictionary, apply the sentence word order, save words in the bucket to apply bucket sort, and then output in descending order of value.

Mock interview


I tried to write the code and pass test cases in 38 minutes, but I could not make it. After the mock interview, I spent over 20 minutes to debug and fix bugs in two places.

Here is C# code written in today's mock interview 8:00 PM. On line 48, I need to remove the statement: if(item.Length == 0), actually the statement: continue is deleted by cleaning process; and on line 106, the word may not be in the dictionary.


And here is C# code written after the mock interview to fix the bugs.

Chatting


It is such a nice experience to practice the algorithm with a software engineer from expedia.com. I was asked if I work for Microsoft since I choose to use C# programming language. I couldn't believe that the peer wrote the optimal solution quick and correctly. I just could not believe that I keep meeting a very talented programmer again, in an ordinary Wednesday. I spent 38 minutes on my algorithm, the peer spent less than 20 minutes on his algorithm meeting planner.

Action items


I need to design some drills for me to work on those algorithms similar to those mock inerview algorithm, play with the error message, so I can think about how to identify issues quickly once I read some error message.

Train myself to read the error message, and also get used to pinpoint the place by interpreting the error message correctly, specially for those error message without line of code information.

My ideal practice is to fix bugs in one minute. I should be able to quickly identify the code's issue.

Tuesday, April 24, 2018

FLAG salary research

April 24, 2018

Introduction


It is so interesting to have a mock interview this 8:00 PM. The peer told me that I am such a nice algorithm and data structure teacher, I should go for a teacher job. No one spends over 3 years to learn algorithm and data structure so well. I laughed about it, and then I said that the teaching is paid by a course.

We had a few minutes to discuss about the code review, what kind of feedbacks I got from the Sudoku algorithms?

So my research of today from 10:50 PM - 11:10 PM twenty minutes is about the salary of FLAGS. Let me review the article again. Here is the link.

FLAGS salary


Here is the article in Chinese.

Follow up 


April 28, 2018

I met a person through mock interview 12:00 PM, so I was told to check the website called levels.fyi. I plan to spend 30 minutes to look into the website.

May 7, 2018

Here is the survey called Canada new graduate offers 2017 - 2018.

Being interviewee: Busiest time in metro town

April 24, 2018

Introduction


It is the algorithm I like so much called linear scan algorithm, by checking next row to make sure that current time stamp is the last row to finalize count of people left in the mall.

Mock interview


I had good time to write and test the code. I tried to write down some notes before I wrote the code in the mock interview.

Here is my C# code. Here is my feedback.



Being interviewer: Sudoku solver

April 24, 2018

Introduction


It is so interesting to meet the peer second time in less than a week. I had good time to learn Go language through the peer's performance. One major advice I had after the peer ran the web compiler test cases is to add back tracking on line 35, so the code could pass all test cases. I explained to the peer that parent node will ask child node to back track the element to its original dot value since parent node will try its next option.

Mock interview


This mock interview is so much fun, since last time I was complained not to give out any hint, leave first 30 minutes for the peer to reach his full potential. The peer gave the time complexity analysis and mentioned that he learned the recursive tree through cracking code interview book.

Here is Go code I reviewed, which also passes all test cases.


10+ rounds of mock interviews

April 24, 2018

Introduction


It took me more than one hour to figure out how many rounds of mock interview I had starting from March 2016. I learn that it is important for me to get organized, and try to get some insights from those mock interviews.

Mock interview 


Here is the summary to show my ten rounds of mock interview.


Learning is so much fun


I used to attend church and had good time in Willingdom small group from 2010 to 2015. I used to go out with over twenty people to hiking and enjoyed trails near the city of Vancouver. But I never imaged that learning algorithm and data structure can be the similar experience. You can learn from one peer a time, and then learn from hundreds of players. Only thing is that I have to force myself to work on those 30 algorithms again and again. But it surprises me that I learn better from those 30 algorithms.

What I believe is that once you learn how to master a hard algorithm like Leetcode 10: regular expression matching and Edit distance, you just apply to other algorithms.

Bible teaching always uses seven to remind us to forgive a person. But learning algorithm Leetcode 10: regular expression matching takes me more than 7 times, more than 14, 21 times. With so many peers to work together on the algorithm, I start to think and understand how I learn the algorithm thoroughly. That is a lot of hard work and a lot of patience to allow myself master the algorithm.

C# source code


It takes time for me to put together all C# source code I wrote for each round of mock interview. Here is the folder to check on github. I will add one by one for each algorithm or all algorithms for each round.


Reference:


All the algorithm and problem statements can be looked up here.

Monday, April 23, 2018

Being interviewee: Find smallest subarray length containing all numbers in target array

April 23, 2018

Introduction


It is the classical algorithm called find smallest substring containing all keys. I have practice the algorithm over ten times last 12 months. I learn so many things through the practice, and it is my most favorite algorithm.

I wrote an algorithm using exactly same idea to apply to integer array.

Mock interview


Here is my C# code.


Follow up after mock interview


It took me a while to write and simplify the code from line 60 to line 66 during mock interview. What I did is to go over in detail if the left char of sliding windows is not in the dictionary, or in the dictionary. And then discuss one step a time.

Other way to think to expedite the process is asking myself four critical question:
1. When to break the while loop 51?
2. When to decrease the variable numbersFound
3. when to decrease the dictionary for the key if the left char is in the dictionary
4. Please move the left point one step forward to start a new sliding window

Being interviewee: Find smallest length of subarray

April 23, 2018

Introduction


I spent 30 minutes to write a brute force solution and I learned something from the interviewer.

Mock interview


Here is my C# code.

Follow up after mock interview


My mock interview experience is very good learning experience. First of all I made a mistake on brute force solution. The subarray should start with value equal to first element of target value, and the last value should be equal to the last element of target array. 


What I did is wrong. Any position of the array can be start of subarray, any position of the array bigger than start value can be the end of the subarray. I did not consider the target value to filter out those unmatched values. 

The time complexity of brute force should be O(n^2) instead of O(n^3). 

After line 76, I should add one more statement.

77   break; 


What if



It is the first time I experienced the strong connection to one of peers I met on mock interview. Since we practiced mock interview together more than three times, I know that he is my best connection right now.

It does not matter how good I am, if I keep meeting strong players on the market to prepare next important phone interview or onsite interview, I will definitely learn how to catch up to match the skills of peers.

This year 2018 is so special. First three months I experience over 10 people to prepare for Google onsite or phone screen, I did tell myself calm down, and learn from those peers, and also ask myself what to work on. I remembered that I thought about a dynamic programming algorithm while I took skytrain to Vancouver donwtown Microsoft to attend a hackerthon event, I was busy thinking about the solution.

My training of 2018 first 3 months are top of world classical training, I only used two mock interview platoform and then I connected to peers over the world. I believe that best of training or education of algorithm and data structure I got for myself is such revolutional, and help me to gain so rich experience.

It is most exciting part of my life as an adult last 8 years.

Leetcode 140: word break II

April 23, 2018

Introduction

Here is one post I like to study for Leetcode 140: word break II. I need a few hours to play with the algorithm so that I can understand better.

David Anderson: A well-written article about Amazon leadership

April 23, 2018

Introduction


It is 12:20 AM, 20 minutes past 12:00 AM. I could not stop reading the article written by David Anderson. I like the article since I like to be a better engineer. I like the great thinking and reasoning in the article.

Reading time


Here is the article link.

Sunday, April 22, 2018

The friendship

April 22, 2018

Introduction


I like to write a blog on the friendship over 30 years. My college classmate from 1984 to 1988 visited Vancouver in March 2018, and then I also had chance to visit Shanghai, and enjoyed the visit of my friend's home in Shanghai near high speed railway station. It takes 8 minutes to Pudong international airport from LongYang station to the airport.

Friendship


I like to write something about friendship. Life is such a great teacher.


Amazon architecture

April 22, 2018

Introduction


I like to plan to learn some system design in next four weeks. I know that it is so challenge to do very well on system design. I like to read some article and at least I learn a few concepts first.

Here is my first step to learn system design on April 22, 2018.

Amazon architecture 


I like to read the article called Amazon architecture.


Being an interviewer: Get A different number

April 22, 2018

Introduction


It is my 10:00 PM mock interview on April 21, 2018. I had chance to observe how the peer wrote the perfect solution.

Mock interview



Here is C# code I reviewed. On line 32, I advised the peer to extract an explanation variable so that the code is more readable.


Being an interviewee: Array quadruplet

April 22, 2018

Introduction


It is my favorite algorithm called array quadruplet. I did talk about the analysis of the algorithm and then wrote down the algorithm without any bug and pass all test cases first time. Only thing I did is to include library using ..., I explained to the peer that I have worked on the algorithm multiple times, but one time a young lady who was preparing facebook onsite, she told me that I should simplify the code to check if dictionary contains key or not. So I only need to write three lines of code from line 57 to line 62, before I need to write if/ else and then update list in both cases.

Mock interview


Here is my C# code.

I still remembered that the first time I worked on the algorithm on mock interview platform. I had such difficult time. After I worked with over ten people on this algorithm, I followed every peer and understood how they think and analyze. So it is also very good experience to help the peer to work on the algorithm the first time. Here is the blog I wrote to give the feedback to the peer. 





Being an interviewer: BST inorder successor

April 22, 2018

Introduction


It was my 6:00 pm mock interview. I had chance to help the peer to come out the solution in 40 minutes. I enjoyed to be an interviewer and then helped the peer to come out the optimal solution.

Sometimes it is so relaxing to watch how the peer worked hard, and then took hint quickly and reached the optimal solution.

Feedback


Here is the feedback I wrote on mock interview platform. I like to encourage the peer to work hard.

Things you did well

The peer took the time to think about the solution, started from inorder traversal and then moved to optimal solution by going up or down through height of tree to search. The peer wrote the code with bugs, and then worked on cleaning and removed all bugs and redundant code. 

Good thing the peer did is to stay calm, and also very good communication with the interviewer. The peer took hint quickly and then worked on the detail. It is very good to be able to come out the correct solution first time. 

The peer tested code with four test cases and make sure that the code works perfect. 

Things you should work on

Recommend the peer to work on more mock interviews. There are a lot of talent people out there, you will meet a lot of peers and then find ways to improve and go above the average performance. Work hard! 

You as an interviewer

I presented two solutions, and then the peer chose one for me to write. Also the peer asked a few questions and I think that the peer is very curious and like to improve. Good to work with the peer. 

C# programming language

April 21, 2018

Introduction


I like to do some research how to advance my C# programming skills before I have to move on Java programming language.

I used to tell people and stop learning C# as C# programmer, I rate myself 7 instead of 9 or 10 last July. I know that it is very challenging for me to be trusted to write solid code using C# programming language for a medium size software company.

How to advance my C# skills?


I bring up the topic and will look into next week.





Saturday, April 21, 2018

Being an interviewer: Sudoku solver

April 21, 2018

Introduction


It is challenge for me to train myself to be an excellent interviewer. I noticed that I checked wechat and read my own blog while the peer worked on C++ code. The first 30 minutes the peer could not pass all test cases, I told her that I am not in the rush, let me review her code and find the bug together.

The problem is that I should give the peer hint every step she writes the code, and point out the bug in her process. But the peer was trained and advanced to ICPC national contest in Brazil, and she wrote the idea kind of new to me. I let myself skip the whole process, and then catch up last minute how the code works. Specially she got some help from a friend to play world contest of ICPC.

Mock interview


Here is C++ code. I learned a few things about C++ through mock interview. The peer told me that in C++ 1 means false.

I ended up talking to the peer one hour 40 minutes. She is preparing Microsoft onsite interview in May. I definitely learn a few things through her practice. I understand that ICPC contest is really good tool to help students to advance their problem solving skills in quick and efficient ways, specially before they start to work full time as a software programmer.

Highlights of code review:
1. line 6, k argument is not meaningful, it should say something like digit.
2. line 14, the peer mixed col/3 with row/3.
3. line 61, the peer told me the failed test has two 9 in the same column, so the call of fill should be checked and return false if the duplicate is found.


Being an interviewer: Find overlap interval

April 21, 2018

Introduction


There are a few challenges for me to be a good interviewer. I learn from every mistake. But today I made a few mistakes when the interviewee worked on the algorithm called find overlap interval.

The peer complained to me that I should give the peer chance to get the job, ace the interview, solve the problem. If there is the bug, I should give the hint and let the interviewee solve the problem. There are 30 minutes limit, he still has time. I cannot just give out the solution without considering being a good interviewer.

I learn a few things about Go as a language, and also I learned a few things about being a good interviewer.

Mock interview


I made a mistake and lost the Go code I reviewed.


Being an interviewee: Deletion distance

April 21, 2018

Introduction


It is 10:00 PM mock interview and I had to work on deletion distance algorithm. The peer asked me if I worked on the problem before, since I did very fast. I finished the analysis in less than 10 minutes, I went over the test case "heat" and "hit", and built up a dynamic programming table from scratch. I certainly told the peer that I worked on the algorithm more than 10 times, each time there is a new issue coming out.

I started to code and passed my test case and all test cases on the platform. And then I had a chat with the peer. The peer had very good leadership skills, he showed me how to explain things crystal clean, pay attention to the intonation, kind of like exaggeration.

I told the peer that people complained to me speaking too fast, my sister with over 30 years teaching experience complained to me that I was not in the same channel, sometimes I let my mind shift away. I do not answer people's question directly, rambling, or change the topic without any conscious. I am still working on it.

Sometimes I notice that I do not focus on one thing, do multiple things in the same time. In terms of mock interview, I have to respect the peer, stop playing wechat or checking my email or my blog while the peer is coding.

The peer is very considerate and supportive, he said that it may happen to him as well.

Mock interview


Here is my analysis and C# code.


Being an interviewee: Leetcode 10: regular expression matching

April 21, 2018

Introduction


It is hard level algorithm called Leetcode 10: regular expression matching. I had a mock interview 8:00 PM and the peer told me that I should hurry and complete everything in 30 minutes. I did finish coding and ran my own test case. But my code failed last test case "abaa" with pattern string "a.*a*".

Mock interview


I had difficult time to play with dynamic programming table. I have to match the index of text and pattern string to the dynamic program table, and then I need to build the recurrence formula.

Being a programmer, I learn to be patient again since I could not memorize the thing. I have to make mistake first and run a few simple test cases and fix the bug.

Here is my C# code.

The first twenty minutes was so exciting and nerve breaking. I just write down what I like to do. For example, I wrote something like // base case "" match "a*" or "a*b*", and then I can write code by looking up the comment.

I confused myself about -1, so I wrote down on line 20 as a comment, // pattern[col - 1].  Because I cannot declare an explanation variable because it may be out-of-range of the array. On line 21, I wrote down dp[0, col - 3] which should be dp[0, col - 2] because I confused dp table index with pattern string index.

It is kind of training I like under stress, work on whiteboard, and also work on communication with the peer, manage the peer to make sure the whole process is up to standard.

I wrote a comment like the following:
// base case "a" does not match "" - do not need to do anything - default false

Good thing I did in the mock interview is to run a few simple test case first. When I ran the test case "b" match "b*", I ran into index-out-of-range error, so I fixed the bug on line 21.

My code passes all four test cases I wrote, but failed mock interview platform test case: "abaa", "a.*a*".

Bug fix 


Here is the code I fixed the bug. All my practice on Leetcode 10: regular expression matching can be looked up here.

Please compare my last practice March 29, 2018, here is the blog.

How to deal with tough interviewer?


I had a peer who has more than five year work experience at Microsoft. He is very strict on time limit 30 minutes, so I was in the rush to complete the code and run test cases. At the end of 30 minutes, the interviewer told me that he was very happy for my performance, and he thought that I should be able to fix the bug quickly.



Over 250 mock interviews

April 21, 2018

Introduction


Once a while I like to do a small research, write something for an interesting topic. I have completed more than 250 mock interviews. I have reinvented myself by getting connected to the world.


Stay connected


I was so busy in weekends and evening, I booked the mock interview on a few platforms, and in-between I had some one-to-one session mock interview to help a peer to prepare for important interview.

I used to stay alone and do not talk to people about coding every day. Somehow I have some bad habits formed and then I got complained about.

I used to call my mom every day from 2000 to 2010. I do not have a person to call every day. My sisters are super busy and they do not like to take my calls. One time my sister told me that I called her more than 3 times when I tried to plan to travel to China. Now I call her zero time and I just go ahead to plan things better and efficient.

I like to check wechat or wenxuecity.com website daily. I attend church and get connected to friends regularly. But I like to get more connected to the world, specially those hard working people who likes to advance their software programmer career, where to find those people?

Mock interview


I started to work on mock interview last March 31, 2017 again. It was not easy to build a new habit, specially I have to meet a stranger and also I have to work on algorithm problem solving. It was challenging and it takes some time to get used to practice mock interview. I did not practice from any mock interview from January to March 2017, even though I was advised to practice on mock interview platform.

Once I get used to practice mock interview, and I know that it is an excellent tool for me to learn algorithm, I set up mock interview 5 or 6 times a day in the weekend starting January. 2017.

It is not easy to write down every mock interview practice. I was too busy and I did give over 10 mock interview as an interviewer to ask same algorithm "Spiral matrix print" from January to March 2018. I did not write down one blog for each mock interview, good thing is that I can replay the video on the mock interview platform.


Being an interviewer: Decrypt the message

April 21, 2018

Introduction


It is 12:00 PM mock interview. The peer worked on the algorithm called Decrypt the message. I noticed something is different. The way the peer presented the algorithm is so clear and then I know that I met a very talent programmer.

Mock interview


I also joined the analysis of the algorithm with the peer. We talked about the difference between those numbers on line 8 and line 9.

Here is the analysis and python code. The peer managed to pass all test cases.


Being an interviwee: Root of a number

April 21, 2018

Introduction


It is 12:00 PM mock interview. I have experience to work on the algorithm root of a number over 10 ten times, 5 for interviewer, 5 for interviewee. The peer has strong talent with 1st place twitter big data hackathon. The peer worked on decrypt the message algorithm first, I rated him top 5 - 10% in all over 200 peers I worked last 12 months.

Mock interview


I like to write a binary search and also apply some technique I saw recently using integer to count the numbers.

The peer challenged me about the termination base case, 0.001 is the error range, how I assert that two values are equal using 0.001?

Here is my C# code.




Being an interviewee: Find the duplicate

April 21, 2018

Introduction


It is my algorithm called Find the duplicate in two cases, both sorted arrays has the size close to each other, or one is much larger than the other one. I had the mock interview, after the peer solved the Sudoku solver, I solved my algorithm next.

What I did is great, I gave the analysis of the algorithm for those two cases, I wrote down the analysis from line 95 to line 110. But I came cross a bug of out of memory for my solution to use two pointers. Usually it is show time for me to solve the problem in one try, less than one minute.

Based on my past experience, I was complained one time by a Ph.D. student of University of Florida who prepared for Google phone screen, he told me that I should focus on the error message, and then think about the possible places for the bug. Do not do wild guess trouble shooting.

Related to out of memory bug, it is not index-out-of-range, what is possible reason?

Actually it is a dead loop, but I turned to my first thought. I wrote brute force solution to replace duplicate.ToArray() on line 40 instead at the first try. I did not use my analysis in this trouble shooting.

After more than 250 mock interviews, I found another issue today for my practice.

After a few minutes, the peer told me that I missed two lines of code if the duplicate item is found. I need to advance two pointers.

Code review 


Here is my C# code and the code passes all test cases.


Being an interviewer: Sudoku solver

April 21, 2018

Introduction


It is my 10:00 AM mock interview. The peer worked on Sudoku solver, and then he chose swift language. What he did is to check given numbers on the board are following the rules - row/ column, small grid 3 x 3 matrix not duplicate.

The code he wrote for preprocessing is kind of buggy, so we started to talk and communicate on this piece of code. And then I told him that most of people do not do this preprocessing.

The interviewee wrote code but could not pass the test case, and then I walked through the code, and pointed out on line 18, variable name i is used the second time.

Code review 


Here is the swift code I reviewed for the peer as well. The code passed all test cases.

I gave the advice to write readable code, use meaningful variable names, and also I advised the peer to communicate more with the interviewer. I told him that I met a young master graduate, who was preparing Google onsite, and then he got offer. When I mocked interview him, he kept asking me "am I in right check", "do you think that my coding looks ok", he has determined goal, to write code to pass all test cases he prepared, he likes to develop a complete solution in less than 30 minutes.

I had a small chat with the peer who is preparing Uber phone screen. The peer got the Amazon offer but chose another offer a few years ago. Interesting story, a small world, stay anonymous, smart and hard working young programmer.



Friday, April 20, 2018

Fall in love with marathon

April 20, 2018

Introduction


It is the first time I start to look into how to run marathon, since I have hay fever recently and it brings my concern how to overcome the difficulty. I had chance to talk to one of my friends in 30 years reunion, and he shared his experience to run marathon.

April 27, 2018

BMO Vancouver Marathon


I like to do some research on 8KM Race, here is the link. Here is the link called training room traing clinics.


Thursday, April 19, 2018

Leetcode 126: Word ladder II

April 19, 2018

Introduction


It is the hard level algorithm and I like to spend time to go over a few more ideas through Google search and Leetcode discussion panel. What I like to do is to go over more detail how to address time and memory limit exceeded problem.

I spent over 30 minutes already to go over my past practice and a few ideas, I like to go over this blog.

Algorithm practice


I like to go over the notes written in Chinese in the blog, and then rewrite some of them, make it my own.

As a programmer, most of important for me right now is to be a good thinker. I like to search the blogs and find the idea to help me think clearly. Here is the notes:

LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题,但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化?

1. 将每个单词看成图的一个节点。
2. 当单词s1 改变一个字符可以变成存在于字典的单词 s2 时,则s1与s2之间有连接。
3. 给定s1和s2,问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。


How do I go over the notes above? 

1. Google search the shortest path in the graph. 
2. How to define a graph? Every word is a node in the graph. 
3. Node s1 and node s2 have a connection -> how to define it?

Let me work on the notes in the following:

无论是求最短路径长度还是求所有最短路径,都是用BFS。在BFS中有三个关键步骤需要实现:

1. 如何找到与当前节点相邻的所有节点。
这里可以有两个策略:
(1) 遍历整个字典,将其中每个单词与当前单词比较,判断是否只差一个字符。复杂度为:n*w,n为字典中的单词数量,w为单词长度。
(2) 遍历当前单词的每个字符x,将其改变成a~z中除x外的任意一个,形成一个新的单词,在字典中判断是否存在。复杂度为:26*w,w为单词长度。
这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说,长度大多小于100,而字典中的单词数则往往是成千上万,所以策略2相对较优。

2. 如何标记一个节点已经被访问过,以避免重复访问。
可以将访问过的单词从字典中删除。

3. 一旦BFS找到目标单词,如何backtracking找回路径?



Wednesday, April 18, 2018

Celebration of 30 years graduation

April 18, 2018

Introduction


It is the reunion to celebrate the birth of Shanghai Jiaotong university 122 years, and also we met in Shanghai to celebrate 30 years since we graduated together back in 1988 with mathematics degree, we stayed together from 1984 to 1988, and took all courses together. For my case, I stayed with other six girls in the same dorm, and we discussed so many math problems together, and we went out together for so many activities. 

One picture


One thing I like to do is related to my experience to the current China highly developed as a country and also open to new entrepreneurship. What I like to do is to relate my class 70141 to one of top celebrity in Forbes 2018, therefore it is very easy to make connection to the whole world, how education helps people to grow, nurture future leaders and motivate each other to work hard.

I sat in the front row, and rest of my class was in the classroom, including the third row Shen Neil, a billionaire and a Yale graduate. Great thanks to the math professor Xiang Longwan, our instructor of mathematics course took the picture and shared with us after 30 years, on April 14, 2018. My favorite reading of professor Xiang is here, who wrote the recommendation letter for my Florida Atlantic University mathematics Ph.D. program back in 1996.


My favorite reading from Shen Neil is here.


One week China vacation

April 19, 2018

Introduction


It is so interesting to write down my one week vacation experience from April 12 to April 18. I learned so many things from my classmates, Shanghai Jiaotong University alumni. We got together from April 13 to April 15, 2018.


Leetcode 359: Logger rate limiter

April 18, 2018

Introduction


I just came back to the city of Vancouver, Canada this April 18 around 1:00 PM. I had so exciting one week vacation, using Air Canada, GaoTie train with speed over 250KM/ h, and met so many friends in the class of SJTU 70141. We shared stories and fond memory, one of professors showed up a picture of whole class, I sat in the front row, I could not believe that every one of us found in the picture, laughing and such great experience.

One campaign I like to do is to work on ten algorithms to celebrate the China vacation. Also I like to see ideas to recover hay fever I still have and hopefully I can recover sooner and go to work healthy. I have to work on seriously to recover.

First algorithm


It is the algorithm I choose to work on after one week vacation from China. First, I like to study one of blogs related to the algorithm. Here is the blog's link.

I like to go over the blog about Google onsite interview, and find some interesting algorithms to work on.




Tuesday, April 10, 2018

Being an interviewee: Find the duplicate number

April 10, 2018

Introduction


It is my favorite time to play mock interview with a peer third time. I know that it is very hard for me to improve a lot in less than one month. The algorithm I was asked is to find the duplicate number.

Mock interview


Here is my mock interview transcript. I will add some notes later.




Being an interviewer: Find the duplicate number

April 4, 2018

Introduction


The algorithm is my favorite one. I learned a few days ago by a peer, he tested my algorithm problem solving. Here is the quora's link related to the algorithm.

In order to learn better on the algorithm, I gave it to the peer who is preparing Google onsite. I like to figure out how he will solve the problem.

Problem solving


Here is the script for the mock interview. I will write down a few lines of notes for the mock interview later.


Being an interviewer: Leetcode 84: Largest rectangle in histogram

April 10, 2018

Introduction


It is my favorite algorithm and it is hard level algorithm in Leetcode.com. I chose this algorithm to interview a friend met on mock interview. He is preparing next week Google onsite, and I gave him another hour mock interview.

I practiced the algorithm recently, but I found out that I still missed something important. The optimal time complexity is O(n), and it has to use stack to save the index of rectangle left boundary when ascending. The stack is always keeps non-descending heights. Here is the link for my past practices.

Learning is fun


The peer is very organized and also very good at explaining the algorithm. I specially like the way he structured the content.

Here is the script for the mock interview.


Sunday, April 8, 2018

Missing Florida summer 2009

April 8, 2018

Introduction


I spent 14 years to live in Florida from 1996 to 2010. I miss the fun to live in the city of Boca Raton and like to document some fun memory. I also like to clean up all photos and videos I took for those years. I like to get some idea how to make good memory for my life events.


Florida Atlantic University campus





Saturday, April 7, 2018

2010 Buntzen lake hiking trip

April 7, 2018

Introduction


It is such a fascinating world. I had such great time in Florida from 1996 to 2010, I always stayed near Florida Atlantic University campus, so I worked on my computer science PH.D. study from 2001 to 2010, so I hanged out with Ph.D. students and scholars all the time. I landed to Canada in April 18, 2010. At that time, I did not have a job waiting for me, I just landed as a permanent resident.

In May 24, 2018, after one month I landed in Vancouver, looking for a software programmer job in the city of Vancouver. I was invited to go out hiking with my Shanghai Jiaotong university's classmate Zhuang and her family.

First time challenge


I used to stay in Florida all the time. So it is so surprising that I had difficult time to do hiking trip with a group of 20 people. So amazing, I experienced the joy and nature beauty of Canada and people I started to get to know.

At that time, I only had two Shanghai Jiaotong university graduates I knew working in the city of Vancouver.

Instagram photos


I like to post some photos for the hiking trip. And also one video.

I like to take some break and think about how important it is to enjoy a Saturday, hold on my plan to work on mock interview, algorithm problem solving, pluralsight.com course responsive website etc.






One video - I like my voice


I talked to my roommate Emma and she said that my voice is not aging at all. I like my voice. Here is the video I recorded at the top of mountain with my friend Zhuang and all other families. I missed the fun.


Count down China vacation

April 7, 2018

Introduction


I will have a very short vacation to China this April 12 to April 18. This is the first time I made the choice to vacation in April.

First of all, we have get-together after 30 years, we graduated with applied mathematics from Shanghai Jiaotong university. We chose one week just after Shanghai Jiaotong University 122 years birthday April 6 celebration.

I spent a lot of time to read wechat group 500 people of Shanghai Jiaotong university just setup for Shanghai Jiaotong university 1988 graduated students. Suddenly, I had to challenge my memory to recall all those faces. I have no clue who they are. But once the pictures together with 30 years before/ after, my memory is coming back.

Life is such a beautiful thing with so many talent friends graduated in 1988 sharing the memory together using wechat.

Not all of us are huge success and very good career. We do have some of us to complain that they work for the big manufacture business, and went through the hard time to lose the stable job, and then the transition to the challenging life.

But we do have a lot of successful stories, in my class 70141, there are principal scientist, professors, deans of universities, math teacher and bankers one of 3600 banks in China top executive etc. We are lucky since we chose to study mathematics,  we had less than 30 people in the mathematics major in Shanghai Jiaotong university admitted in 1984. But at that time, we have more than 6 class of mechanical engineering major, material science major etc.




Friday, April 6, 2018

Leetcode 312: Burst balloons

April 6, 2018

Introduction


It is a hard level algorithm, so I like to work on the algorithm over ten times. I like to spend time to read this blog written in Chinese, and then try to understand better about the algorithm.

Here is the gist I created for blog study.

My favorite algorithm


It is the first time I read this analysis in Chinese. I could not believe that the analysis is such a good one.

I have to learn how to break into two subproblems and also two of them are independent.


Algorithm study: 95 algorithm videos (VV)

Algorithm study: 95 algorithm videos (VIIII)

Algorithm study: 95 algorithm videos (VIII)

Algorithm study: 95 algorithm videos (VII)

Algorithm study: 95 algorithm videos (VI)

Algorithm study: 95 algorithm videos (V)

Algorithm study: 95 algorithm videos (IV)

Algorithm study: 95 algorithm videos (III) - Leetcode 5: Longest palindromic

May 4, 2018

Introduction


It is six minutes teaching video for Leetcode longest palindromic substring. Here is the link.


Algorithm study: 95 algorithm videos (II)

April 20, 2018

Introduction


It is hard level algorithm called Leetcode 312: Burst Balloons. And the video is 20 minutes, I spent the time to watch the video, staying at home for one day vacation. I enjoyed the learning of the algorithm.

It is interesting for me to learn the dynamic programming through the video. I like to evaluate the author and see how good he is. I know that he is working for Facebook.

Leetcode 312: Burst Balloons


I like to talk about a screenshot and discuss the layout of dynamic programming algorithm presented by basksetwangcoding.



First step, I need to define state for the dynamic programming algorithm.

Next step, I need to define initialization step.

Third step, I need to define the function, problem and subproblem how to connect each other.

[left][right] = Max(i: [left + 1, right - 1])

For each subproblem, coin[i] * coin[left] * coin[right] + [left][i] + [i][right - 1]

Fourth step, I need to define result: [0][n - 1]

I need to put together a simple example to explain the solution to the peer. Here it is the example:

  1    2    3    4   5   6   7  8  9

Algorithm practice


Here is my C# practice.

Algorithm study: 95 algorithm videos (I)

April 6, 2018

Introduction


It is a hard level algorithm called Leetcode 312: Burst Balloons in Leetcode.com. I like to study the algorithm again by watching the teaching video here.

I could not believe that I finally have time to write code for the algorithm on April 25, 2018.

Leetcode 312: Burst Balloons Algorithm practice


I started to work on the algorithm on April 24, 2018. I have to learn the algorithm by working on a simple test case [3, 1, 5, 8] with the maximum value 167 based on Leetcode 312 problem statement. What I did is to write C# code based on the idea based on the video provided by a facebook engineer.

I calmed down and thought about how to write this dynamic programming solution, I told myself that I should take the time to think and do not rush, read other people's source code.

Basic ideas are simple. Define the base cases first, and then bottom up build the dynamic programming table.

I spent more than 40 minutes to write down the code on the paper. I put the code in Visual studio and debug the code. Apply the test case [3, 1, 5, 8]. But the code does not work, the value is much bigger than 167. Actually it is 218.

Here is my C# practice with some bugs. I need to figure out my problem in the algorithm. 

I could not believe that I could not count the correct number. The number is too big. In theory, it should be the error from the base case, the logic of recurrence is simple and I copied from the facebook engineer presented in the above video. But I need to train myself on this bug finding process. 


Find the bug


It is time for me to read discussion panel of Leetcode 312, I read a few of them, but the dynamic programming idea is different. So I continued to google and read a few blogs. One of blogs is very good since the blogger works for Microsoft.

But I still could not apply my case. The dynamic programming method in those blogs are inclusive, not exclusive.


Questioning the base case


Finally I started to question my base case, what is the value dp[i, i+1], in other words, keep ith and (i + 1)th balloon, then there is no balloon to burst. My answer is numbers[i] * numbers[i + 1], that is too much. So I changed to one. I ran the code still not the correct. So I finally know that it should be 0.

Although it takes me a lot of hours to learn the algorithm, but I think that I do right thing for myself.

Here is my C# code to pass Leetcode 312 online judge.

Thursday, April 5, 2018

Algorithm study: 95 algorithm videos

April 5, 2018

Introduction


It is very surprising that those videos are very well prepared by a facebook engineer in Chinese language. I really like to learn something from the teaching.

Here is the video feed. Here is the author's profile on leetcode.com.

10 most favorite algorithms


I like to choose my 10 most favorite algorithms and write down some notes here. I like to study some algorithms so that I can prepare some good questions to be a mock interviewer for a peer who prepares for Google phone interview second round.

I just could not believe that I had last 2 mock interviews as interviewer, and two peers are preparing for Google onsite in a week. I can tell how good they are to prepare for the interview.




Leetcode 84: Largest rectangle in histogram

April 5, 2018

Introduction


It is time for me to learn this hard level algorithm again. I know that it takes at least 10 practice for me to learn a hard level algorithm. Today I chose to study the video prepared by basketwangcoding in Chinese. My last practice was on January 18, 2018. Here is the blog.

30 minutes video lesson


I like to write down some notes from the lecture.

Brute force solution


In order to learn the algorithm very well this time, I like to work on the test case, [2, 4, 6, 5, 3], explain to myself how to solve the algorithm using O(n^2) brute force solution first.



How many rectangles to be calculated? What is the maximum rectangle area's value?


Iterate the end position from i = 0 to 4.

i = 0, the rectangle is 2.
i = 1, the rectangle is 4.
i = 2, the rectangle is 6.
i = 3, the rectangle is 5 + 5 = 10
i = 4, the rectangle is 3 + 3 + 3 + 3 = 12.

So the maximum rectangle is 12.

For each end index, we can go backward to search until the array's value is less than end index's value.

Or I also can think about the alternative idea. It is to iterate the start position from i = 0 to 4,

i = 0, the rectanlge is 2 + 2 + 2 + 2 + 2 = 10.
i = 1, the rectangle is 4 + 4 + 4 = 12.
i = 2, the rectangle is 6.
i = 3, the rectangle is 5
i = 4, the rectangle is 3



Being interviewer: Leetcode 250: Count univalue subtrees

April 5, 2018

Introduction


It is my favorite algorithm in March, 2018. I had two practices on this algorithm, one is to write the algorithm in 30 minutes mock interview, and the second one is to review the peer's practice. I chose the algorithm to interview the peer on April 4, 2018 10:00 PM, but I could not give out the solution based on the peer's code.

Follow up 


Here is the code I reviewed in mock interview. The peer asked my advice, but I could not tell at that time the code was bug free.

Now it is 9:20 PM April 5, 2018, I like to write a C# solution based on the simple idea, using negative to represent that the tree does not have same value. Here is my C# code.