Being an interviewer: Root of a number

March 28, 2018

Introduction

It is a binary search algorithm called root of a number. The hint I gave in the mock interview as an interviewer is to explain how many numbers to search for x = 8, n = 3, it is from 0, incremented by 0.001 to 8, total is 8000 numbers to search.

Binary search algorithm

Here is the binary search algorithm I reviewed written by the peer. The algorithm still has issues to pass a few test cases. I like to look into as well.

I like to get organized and review all my past practice.

Code review

Actually the code should be updated in two places:
1. Line 44 and 45, return (double) m/ 1000;
2. Line 56, return (double) s/ 1000;

The argument is that when s == e on line 37, the return value should be s, not -1 or 0.0.

Incremental value 

It is better to change the design, and use 0.0001 as a different number to apply binary search. Here is C# code.

Given the example x = 8, n = 3, instead of search 8000 numbers, we choose to search 80,000 using binary search. Incremental value is 0.0001 instead of 0.001.

Being an interviewer, it takes some time to figure out how to guide the peer to lead the optimal solution and pass all test cases.

Leetcode 152: Maximum product subarray

March 27, 2018

Introduction

I like to work on this algorithm Leetcode 152: Maximum product subarray, and I find that it is similar to the algorithm I practice so many times called float numbers and operators.

Algorithm practice as an interviewer

I chose the algorithm to interview the peer in mock interview. The peer is very talent programmer, he had a facebook onsite last December, and he prepares for Google onsite. what I found out is that he needs some hint to come out dynamic programming solution, but his coding ability is very strong, and also the analysis ability.

Here is the transcript.

Being interviewer: Sudoku solver

March 25, 2018

Introduction

It is such great experience to work with a software engineer from Israel 10:00 am mock interview.  The peer also told me that she works for one of top four software company in the world. She worked on Sudoku solver.

As an interviewer, I like to write down some highlights for my code review.

Code review

Here is the solution I reviewed. First of all, the peer wrote down the analysis very clearly and asked me if I followed her idea after she wrote some of the code from line 21 to 44. After she wrote the solution to call recursive for next iteration, she asked me the feedback.

Highlights of my code review:

1. line 25 to line 26, I added those two lines. I explained that there is a bug to find next position of '.' char. Line 23, I changed column = j to column = 0, and add line 25 and line 26 to start from (i, j).

2. line 56, I explained to the peer that no need to check, HashSet.Remove can handle the case if the char is not in hashset.

3. line 88 to 91, I explained to the peer why backtracking is necessary. Her argument is that next iteration the element will be replaced by the available number. And then I gave her the example, first row with first two elements 5 and 3, and 3 empty space with '.', if we work on the third '.' and try the last available number but fails, we need to put '.' back and then continue to work on second '.'. Recover the original status.

Using graph like the following:
5 3 _  _   _
              _ fail ->'.', work on third dot, (0, 4)
          next iteration to work on second '.'

4. work on nextRow and nextCol calculation. Originally the peer wrote (emptyRow + 1)% n, (emptyColumn + 1) %m,

Actionable Items

It is very good to work with the peer on this algorithm. Today is Sunday. I choose to stay at home and work on mock interview. Yesterday I spent over 90 minutes to work with a peer on budget cap calculation. Later I talked to my roommate Emma, she told me that I have to think for other people. If I meet  a strong player on algorithm and data structure, I will talk over 90 minutes. Think about the other way, same applies to the peer I met as well.

Emma is a very good IELTS teacher, and she told me to work on cleaning the living room table together. What I did is to learn and stay organized. We both laughed about the shopping I did in Seattle, and I did make a mistake to purchase too many Nike shoes for myself. I bought 3 pairs of Nike shoes, one pair I wore two days, it broke my skin near my ankle. I went to Seattle with my friend from Shanghai, she laughed about me how I can wear 3 pairs of sneakers. It turned out not cheap for 3 pairs of shoes, $150 Canadian dollars.

Decrypt the message

March 10, 2018

Introduction

It is the good practice for me to be an interviewer. I learn from every practice.

Interviewer practice

Today I had chance to give hint, and then I explained the algorithm asked by the peer. I made a mistake to try to help coding, I added the prefix sum sentence before source[i] is calculated.

Here is C++ code I reviewed. The whole interview only took 38 minutes for both of us.

How to make a successful mock interview as an interviewer?

Feb. 10, 2018

Introduction

It is the sixth mock interview on the second anonymous platform, so I had chance to meet programmers from top ten companies in west coastal area and also graduate students from top universities, and then I had chance to get some feedback about the algorithms I choose, and the behavior issues I have to correct.

First of all, I should give the interviewee the agenda, including how many algorithms I should give. This is the advice I got from Feb. 9, 2018 mock interview. I do not want to scare the interviewee when I ask the interviewee to stop the first algorithm, and I like to move on to the next algorithm.

My goal is to test how confident the interviewee is, how good the interviewee is on algorithm and data structure problem solving. I will continue to ask and then see if I can find any major issues through the interviewee. Since the interviewees are with experience both sides, and also with very good education, so usually I just pay more attention to learn something through the experience.

People varies in terms of soft skills, and learning new things outside the work. Sometimes people can not hide if they do not practice algorithm and data structure long time, like catching up in a month of two.

Algorithm

The interviewee asked me where to find the resource about the algorithm I asked in mock interview. I know that the interviewee is very confident and also independent thinking. So in order to prepare an algorithm to be my mock interview algorithm, I also try to build a profile for the algorithm. I share the algorithm float number and operations on the stackexchange.com website. Here is the link.

I continuously study one algorithm called spiral matrix, Leetcode 54. First time I learn that it takes so much time for me to catch up so many ideas and then I know how smart people are to get the good idea to survive in a mock interview and write a perfect working solution in ten minutes.

Yesterday the interviewee took over ten minutes to read the problem Leetcode 54 and came out the idea, and then he tried to use extra space to avoid so many edge cases. I really like the idea, it is something I am looking for in mocking interview.

I honestly told the interviewee yesterday that some one did much better than him, passed through all four algorithms I gave to him in first 35 minutes, and he did 30 minutes system design interview as well. If you work for a big company, basically you are competing with your coworkers. The anonymous interview is supposed to be hard, difficult to pass the interview. Do not get frustrated if you get low rating. I just make sure that you are guided to the optimal solution, so you learn something and do not waste time on mock interview.

The precondition is that I also have to learn the mock interview algorithm from all the interviewees, I have to build depth and breadth of knowledge of the algorithm.

What I have learned as an interviewer

I did find one thing through the mock interview. I have to learn how to take turn to express my idea and also try to catch the right time.

Deletion distance dynamic programming

Feb. 6, 2018

Introduction

I still have difficult time once a while in terms of solving dynamic programming solution. The underneath recursive design of dynamic programming takes more time to practice.  I had a mock interview last weekend and the peer showed me his way to solve the deletion distance.

It is such nice learning experience from the peer. The code is written in Java and the link is here.

Most of important is that the peer showed me how he proved that recurrence formula is correct. Here is the transcript of the analysis.

Follow up 

I asked the peer in mock interview and then we discussed the formula why distance("heat","hit") = distance("hea", "hit").

Here is the discussion:

 //$dog and $frop,
  //$hit, i =   3 $heat, j = 4
  //f[$hit][$heat] = f[$hi][$hea]
  (f[$hit][$hea] + 1)
  (f[$hi][$heat] + 1)
  (f[$hi][$hea]  <- minimum
    min(f[$h][$hea], $f[$hi][$he]) + 1
  )


Let me write down the explanation given by the peer on March 12, 2018. First let me read his explanation and then figure out his reasoning.

First the peer thinks that it is better to add extra char to stand for empty string "", using '$' char.

There are 3 choices to determine the deletion distance between two string "$hit" and "$heat". There are three choices, in other words, here is the expression:

f[$hit][$heat] = Math.Min(f[$hi][$hea], f[$hit][$hea] + 1, f[$hi][$heat] + 1),

We should be able tell that minimum one is f[$hi][$hea].

Follow up 

July 9, 2018

The peer contacted me to ask practice together. I was so surprised since he won ICPC regional contest in 2012. It is the first time I have a peer to practice together with highly competitive skills in contest.

I just quickly looked up his review back in Feb. 3, 2018 6:00 PM. What I did is to check date connected on linkedin, and then found the mock interview round login, and then looked up algorithm. And then I found the blog, and mock interview feedback.

Leetcode 10: regular expression matching

February 1, 2018

Introduction

I understand that there is no hard algorithm, only lazy student. I have spent over 10 times to practice Leetcode 10: regular expression matching last eight months. Usually the peer writes a perfect solution and it takes 30 minutes, I experience a lot of good learning experience from those peers.

Last two months I start to write dynamic programming solution as well to solve the problem.

One hour practice

On January 31, 2018 I had a mock interview, and then I spent one hour to be interviewer. The peer  wrote a perfect dynamic programming solution. And the peer shared his argument that one time for b* pattern is not necessary in implementation.

Argument to think about

b* can repeat zero time, more than one time. But one time can be covered by zero time and more than one time this two cases.

Here is the transcript I reviewed.

Leetcode 684: redundant connection

January 20, 2018

Introduction

One of ways to learn the algorithm is to ask the peer to solve the algorithm after mock interview. I met a peer this morning 10:00 am mock interview. He is graduating from K.I.T. a university in German. He likes to apply Switzerland Google instead of German one.

Algorithm problem solving

The peer came out the idea of the algorithm Kruskal's algorithm. And he also talked about minimum spanning tree. How does the edge joins the union by determining if the node is belonging to the union or not. If both of nodes of edge is in the same union, then the extra edge is found.

I asked him what is last time he worked on the Kruskal's algorithm recently. He said that he did not work on. But he worked on video project, cycle detection, filter, or canvas, video, use interface, when the video start time clip something related to the algorithm.

Aha, how do you compete with some one with super talent, and also hands on with projects outside the university, job?

And also the peer is super calm when he worked on the algorithm. He said that let me think about 1 to 2 minutes. And then at last, I asked him if I gave him the hint, he said no.

Matrix spiral print algorithm

January 6, 2018

Introduction

It is another 10:00 AM mock interview. The peer worked on the algorithm called the matrix spiral print algorithm. So surprisingly, I learned a new way to write the solution and also the code is much simple and easy to follow.

Code study

Here is C++ code to pass all test cases.

It is so interesting to read the blog I write back in March 2016, the first time I practiced the same algorithm on mock interview platform. At that time, I was so shy and the code I wrote was not so clean and readable. And I even read the code I wrote back to 2015.

Code review: Leetcode 10: regular expression matching

Dec. 26, 2017

Introduction

It is another mock interview 12:00 PM. I had chance to help the peer solve Leetcode 10: regular expression matching. I did not expect that the peer can solve the problem almost perfectly. I was so surprised to learn from the peer how he wrote an elegant recursive function using while loop.

Code to study

Here is the peer's C# code. I like the implementation.

The above code failed last test case, "abaa" and pattern string "a.*a*". It should return true.

Here is the code to fix the above bug. The code passes all test cases on mock interview platform. But it failed on Leetcode 10 online judge.

Index out of range error, Line 28: System.IndexOutOfRangeException: Index was outside the bounds of the array. Last executed input: "ab" and ".*c"

Line 28: If(text[tIndex] != pattern[pIndex])

Actionable Item

After spending over 30 minutes to debug the issues using Leetcode 10 online judge, I learned that the recursive solution has a lot of issues. Later I will revisit the solution and give more objective comment on this solution.