Leetcode 4: Median of two sorted array

Dec. 17, 2017

Introduction

I had a mock interview at 10:00 AM, and after the mock interview, the peer asked me how to solve algorithm in Leetcode 4.

After more than 20 binary search algorithm practices last 6 months, I just gave a talk how to solve the problem.

Algorithm

The problem statement:
To find the median of two sorted array.

Optimal solution is O(lg(n + m)), n and me is the length of two array.

My analysis

If two arrays are sorted, and then we try to find each median of sorted array first, and then see how we can relate the median to those two median values.

So we can not merge two sorted array, since it will take O(n + m) to merge two sorted array using two pointer techniques.

The idea is to simple, each sorted array we divide into two halves and then we have to decide to get rid of which half.

Code to share

The peer was really busy but the peer said that if you have the code, please send me an email. So I thought about the problem and remembered that I worked on the similar problem and asked code review before.

I was so proud of myself, so I sent the link. In less than half hour, the peer sent me email about test case failure.

Here are the report about complaint.

Input: [1, 3]
[2]
output: 1.00000
Expected: 2.00000

So I started almost 90 minutes to debug my code.

C# code review 

Here is the C# code to pass all test cases on Leetcode 4. 

And then, I wrote an email at 3:27 PM to the peer, here is the email I wrote:

Thank you to point out problems. Here is the code to pass all test case of Leetcode 4. 

 https://gist.github.com/jianminchen/4cdbf6bf2a4906e421d241044dad7c3e

 I modified the code based on your input. 

 First, line 10 I prefer to use meaning variable name, firstIndex, whereas line 12 lastIndex is used. 

 Line 30, 32, and 39, the function getKthLargest function is used. Remember that kth smallest number is matching your original input. 

 The rest are the bugs in my code, a few of bugs:

 1. line 52, add +1 to the formula nthSmallest, this is missing one bug. 

 2. line 74, it should be start2 + k - 1, missing start2

 3. line 79, should be start1 and start2, not 0, 0

 4. line 86, 87, missing start1 and start2

 5. line 97, missing start1

 6. line 113 missing start2

That is all. I am surprised that my code has 6 bugs. Without Leetcode test cases, I write buggy code. 

Sincerely, 

jianmin chen 

And the peer sent me an email saying that: Me too 

Actionable Item

Need to put some review on code review, fix the buggy code I wrote.