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.

K largest elements in the array - various ideas

July 29, 2016

Top k values in the array - review the following article: 

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

1. sorting the array   O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics

7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case

 http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array.  Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...

7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).

7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.