Being interviewer: Array index and element equality

July 1, 2018

Introduction

It is the binary search algorithm with extra constraint, lowest index. The peer wrote the algorithm with a few bugs but she showed me how good she did reasoning using test cases at top of the code, two test cases, and she always used them to test her code. This is the first time I saw some one to do that. Very smart and I like to learn it as well.

Binary search algorithm 

Here is the algorithm I helped as a reviewer. I did help to fix the bug, add global variable initialization on line 17.

Byte to byte - Algorithm and data structure problem solving coaching

June 23, 2018

Introduction

I met a young graduate student and we worked together on mock interview algorithms 90 minutes. I worked on Sudoku solver, and he worked on binary search Array index and Element equality. He recommended me to watch Byte to Byte video on youtube.com.

It is such a good conversation with the young graduate, we did talk about a little theory about binary search algorithm, common mistakes, base case, dead loop, and lowest index, recursive function vs iterative solution.

And we talked about more about internship, onsite interviews. I really learn a few things about young graduate  student, a very good engineer and quick to write and work on coding all the time. Compared to him, I am kind of slow to get along with the peer, and not so good to work on a test case, and try to figure out things on the fly, make thing work.

One fact is that I practice binary search last 6 month over 50 times through mock interview, the peer only did once. I did see a lot of issues in the coding part. But I also learn how to judge a person with good thinking process and how to take hint and move forward. I treat the algorithm problem solving likes sports, there is no way to avoid hard work. Embrace it.

Research 

Academic research is such a great topic and I wish that I have time to get into more on a topic.

One video to watch

Here is five minutes called "Increasing your creativity and solve any coding interview problem".

Spend 15 minutes to go over all possible solutions first. We should not go to optimal solution right away.

Take the time to really think and even wild ideas. What sort of things will work, what sort of things will not work.

Light speed to learn binary search algorithm

January 24, 2018

Introduction

It is another 10:00 pm mock interview. I met a peer and then I observed how quickly the peer came out from the Newton method, and in less than five minutes, he came out his own style of binary search algorithm and solved the problem.

The peer told me that he learns the programming by himself.

Code review 

Here is JavaScript code.

The peer wrote a few lines of console statement, and then he just quickly removed them once the code passed all test cases. Just unbelievable the peer can learn the binary search in light speed.

The code is not perfect, but the peer showed me how good he can learn and how fast he can learn to write the algorithm and also solve the problem.

Since it only takes a few minutes for the peer to learn, I called it light speed.

Follow up 

Feb. 21, 2019
The interviewee joined Google in July 2019.

Code review: Find kth largest element in the union of two sorted array (Follow up)

Dec. 17, 2017

Introduction

It is so challenge to work with the algorithm called Leetcode 4: the median of two sorted array. It is hard level algorithm. I have been worked on the algorithm more than two hours today.

First I wrote a bug-free code based on Leetcode 4 online judge. And then I wrote a code review to review my own code Find kth largest element in the union of two sorted array (Follow up) written more than 10 months ago.

Here is the code reivew I did in last 60 minutes.

Actionable Item

It is kind of fragile thing to perform algorithm practice. In order to write bug-free code, I documented every step and it shows that it takes over 10 months to learn one algorithm related to binary search, and actually it also takes a senior level Microsoft engineer to help me to find the bugs after mock interview.

The algorithm is so hard to write and we have issues without a lot of test cases from Leetcode online judge Leetcode 4.

Timeline of algorithm practice

11 months ago, I posted the algorithm question on code review, here is the link.

With the feedback of JS1's code review , 10 months ago,  I posted second algorithm to follow up. Here is the follow-up.

Today I practiced my mock interview over 100th times since this March 2017, I always meet the highest top players who works hard to prepare top level onsite interview like Facebook or Google in less than one month.

I have to share my practice and then work more than 2 hours to work on bug fixes, and coding style and all other engineering stuff. Be a writer first instead of just writing code.

Today I wrote a code review to fix my own mistakes over 10 months ago. Here is the code review link.

Binary search practice

Dec. 12, 2017

Introduction

Binary search algorithm is getting easy to write and I wrote one more time on Dec. 11 10:00 PM mock interview. I wrote the algorithm using C# language and the code passes all test cases.

Code review

Here is C# code.

Line 50: return binarySearch(x, n start, end);

I forgot to write a recursive call as line 50 shows. After the whiteboard testing, I wrote the test case Root(7, 3) and then I found out the bug.

Follow up 

Dec. 19, 2017  10:14 PM

Binary search range should be discussed based on x value, if x > 1, then the search range is [0, x]. But if x < 1, then search range is [x, 1] instead.

The mock interview practice has a bug related to range to search.

Binary search algorithm

Nov. 28, 2017

Introduction

It is my most favorite algorithm last six months. My last practice was in less than a week ago, and I made a mistake about the edge case.

On Nov. 27, 2017, I had chance to review the peer's binary search algorithm and I gave out some code review.

So interesting to work on mock interview, I like to write more about mock interview in general on binary search algorithm.

Common mistakes in binary search algorithm

Let me choose a topic and then I write something around the topic.


Focus on middle value

One time in mock interview, I did start value checking in the base case, and then later peer told me that I should focus on the middle

value. The depth first search is about base case, about middle value. Write simple code as possible, avoid discuss start value.


Structure your code very well


There are two ways to write binary search algorithm. Either recursive or iterative, the structure of code should be well structured.

Continue to work, kind of loop

Do some work for base case

Some logic checking to reduce the range of search to half


End of loop

Edge case 

Sometime half of range is only one node. In order to include the node into the first half range, the condition should be considered carefully to allow equal sign in comparison. One example is here.

The practice of binary search with the edge case bug is documented in the blog called binary search algorithm is always my favorite.

Converge concern

The binary search is to remove half of nodes every step, the base case is to check if the middle value node is satisfied the condition. In

case the search will not converge, it is better to narrow down the next range as (middle, end] or [start, middle. Exclude middle, at least one node is removed each iteration. There is at most n iteration, where n is the length of the size to search.


References:

Past practice 1: blog is here.

Binary search is always my favorite

Nov. 23, 2017

Introduction

Binary search algorithm is my most favorite algorithm. I like to write it as a depth first search, recursive solution, and learn to write base case as the first thing in the function.

Code review 

Here is the C# code I wrote tonight. The mock interview started from 10:00 PM.

But the code smells, do not repeat yourself. DRY principle is violated.

The above code could not pass Leetcode 33 online judge, failed test case: [3, 1], 3, since the left half range can only include one node, so the fix is to include = sign in statement line 35.

Instead of "var firstHalfAscending = startValue < middleValue", it should be "var firstHalfAscending = startValue <= middleValue".

Follow up

Nov. 23, 2017

After the mock interview, I thought about my solutions in past practices. I should find a more simple solution.

In mock interview, peer asked me to explain the idea again to divide into two half range, one is in ascending order. I failed to make the idea very clear to a veteran programmer working over 10 years in Microsoft.

In other words, my code smells. Because I used the copy and paste in the mock interview, there are four recursive calls instead of traditional two recursive calls for binary search algorithm.

Based on the mock interview standard answer, it is to find pivot point first, and then apply binary search algorithm. Instead I applied binary search algorithm directly without concerning the pivot value.

Why? How did I make the different choices?

Of course, I spent hours to read all kind of solution on discussion panel of leetcode 33: Search in sorted rotated array before. I knew that there are almost millions of submissions, so many ideas. But bottom of my heart, I like to say that I went through mathematical training of analysis, I like to introduce two lemmas before I write code.

Lemma 1

The sorted array with length bigger than one is rotated to left with unknown n numbers, given the number n, n can be determined in the first half by the following checking:

Based on the fact that the first half range's length is not smaller than one.

How to determine if n can be searched in the first half range?

If the range is in ascending order, in other words, array[start] <= array[middle], and if n is in the range of [array[start], array[middle]], then n will be in the second half. Get rid of second half.

If the first half range is not in ascending order, then at least there are two elements in the first half range. It can be inferred that second half range is [array[middle], array[start] - 1]. The search number n is not in the second half range. Either the search number n is not smaller than array[start] or n is smaller than array[middle].

End of Lemma 1

One good solution with example

The C# code is here:

Here is the example to explain one inclusive range or two exclusive range to search:

More detail, exclude the range [4, 8] which is in ascending order in the above picture, two ranges are checked, one is >= 9 and the another one is < 3.

Nov. 24, 2017

Continue to update the code, use more meaningful variable names. C# Code is here.

How do I get here?

I have to get organized, so I went through blogs and reviewed all past practice on this algorithm, and also checked leetcode 33 submission history. I did not submit anything on Leetcode 33 before Nov. 22, 2017.

Past experience is documented here.

Sept. 16, 2017

The mock interview practice is documented here.


March 23, 2016

The practice is documented here.

Nov. 23, 2017

Leetcode 33, Search in Sorted Rotated array, C# code passes online judge.

Binary search practice

Sept. 22, 2017

Introduction

I had a mocking at 10:00 pm and then I was told to write the program to find a number using binary search. I failed 5 out of 6 test cases, index out of range, and then I was told to comment out the code of binary search function, and then nail down the bug related to implicit typing "var" on line 47.

Algorithm practice 

My binary search practice is here.

Coding with style 

I spent almost 40 minutes to chat with the peer about coding. I really like the conversation between two programmers. I advised the peer to write self-documented code, in other words, do not write variable name l, h which l stands for low and h stands for high. Express the intent, define a meaningful explanation variable. And also I advised the peer to do whiteboard testing, and showed him an example, run the code line by line and execute the code with the result calculated by myself.

Write simple and clean code

The peer asked me how I can have so much time to play hackerrank contest, ask code review algorithm questions, and then write blogs.

I shared a few things:

1. The blog I did code review for myself, the triangle algorithm.

2. Edit distance dynamic programming post on quora.com. The link is here.

Thoughts after mocking

I think that writing coding blog is easier compared to write code at work. To ask a question on code review website is also easy compared to solve problems at work. I think that the experience of writing blogs is very rewarding experience, my blog is becoming my best reading library.

Leetcode 33: Search in Rotated Sorted Array

Sept. 16, 2017

Introduction

It is the wonderful learning opportunity for me to practice the algorithm again last night at 10:00 pm. I chose to write the idea I thought about and read about, but I had not written it before. The experience told me that binary search basically is also like a depth first search, the most important is to work on base case.

The more detail is like this, I spent first 15 minutes to exchange ideas with the peer, and then only 13 minutes left, I need to write some code, and I chose to write a binary search combining normal binary search in sorted array and shift array binary search. My argument is that the normal one is just special case of shifted array binary search. The iterative solution is hard to avoid duplicate logic and coding. I just could not believe that I made it the first writing without any bug or grammar error.


Leetcode 33 is a medium algorithm, I wrote down the algorithm in less than 13 minutes, and most important thing I did is to move base case "middle value" (line 29 - 32) to the first thing inside the while loop, moved those 4 lines out of if block from line 36 to 46.

Tip to share 

I got the complaint about my practice of binary search tree. The peer told me that the most important part is to work on middle value in the binary search tree. Focus on middle value, do not consider start value at all.

Algorithm practice 

C# code practice is here. 

Count Solutions - ad infinitum18

June 10, 2017

Problem statement

It is 2:50 pm, here is the progress report.

It is very good learning experience. Julia will try some ideas to solve the time out issues. Julia solved the timeout issue by going over the detail, using binary search etc. But now the issue is wrong answer.

Now it is 11:28 pm. The best bet is to work on this algorithm, try to figure out why the answer is not correct. 11 answers for test case 1 to 10, 12 are wrong answers. The maximum score of the algorithm is 40.

Follow up after the contest 

It is June 11, 2017 11:48 am. Julia plans to look into test case 1, and figure out that why her binary search algorithm failed the test case 1.

Last Sunday morning she worked up to 1:40 am and then tried to figure out why her binary search algorithm failed the test case 1 - 10. She had good reasoning to use the curve of binomial x² + by analysis of top/ bottom node, two sides of top/ bottom node are in ascending/ descending order.

Julia thought about that it is most possible algorithm she could have gained more points if she can put some test cases in the contest.

Julia's C# code in the contest is here. Score 2.11 out of 40.

Julia's C# code in the contest using brute force, score 4.0 out of 40, code is here.

Leetcode 33. Search in Rotated Sorted Array

June 5, 2017

Problem statement

Leetcode 33: Search in sorted rotated array

March 23, 2016

understand the algorithm - good analysis graph in the following blog:
http://fisherlei.blogspot.ca/2013/01/leetcode-search-in-rotated-sorted-array.html


using this analysis in the blog:
First, Julia, you have to find out which half is sorted; only one of them;
Second, use sorted half to determine if the search is in the sorted half or not;
Then, you go to sorted half/ unsorted half.

Code can be optimized, if it is in sorted half, then, go to normal binary search
otherwise, go to unsorted - modified binary search - use recursive to write a solution first.

http://bangbingsyb.blogspot.ca/2014/11/leetcode-search-in-rotated-sorted-array.html


Julia, in your practice, you discuss that the middle point is a peak element/ valley element or not; and then, both halves are sorted, which is the special case.

Lesson learned:

1. In your analysis, you have to make the test case as simple as possible, as you see in the above blog:
use 0 -7,
原数组：0 1 2 4 5 6 7
情况1：  6 7 0 1 2 4 5    起始元素0在中间元素的左边
情况2：  2 4 5 6 7 0 1    起始元素0在中间元素的右边

2. And then, you have to be careful, how many cases are then discussed. The above, two cases, using 0 as search element

3. 两种情况都有半边是完全sorted的。根据这半边，当target != A[mid]时，可以分情况判断：
Actually, you should add one more restriction, search half is sorted in ascending order. 

because the half of 6 7 0 1, 6 > 1, in the descending half, it must include going up and then going down. but, 
in the ascending half, 1 2 4 5, just pure ascending. <- you can argue that, it is a fact!