Thursday, January 5, 2017

The kth largest element from two sorted arrays

January 5, 2017

Introduction
Spent over 2 hours to study Leetcode 4 and Leetcode 215: the medium of two sorted array, and then Leetcode 215: the kth largest element from the array, and then, Julia spent over one hour to work on the code for the algorithm: the kth largest element from two sorted array.

Workout

Here is the C# practice: binary search, time complexity: not O(lg n + lg m), smaller one: O(lg(n+m)), n, m are the length of two sorted arrays.

Julia likes to work on the test case a little more time, 20 - 30 minutes, and then post the algorithm on stackexchange.com for a code review.

Read the article again, learn more about the analysis.

January 9, 2017
The most important feedback about the code - code review:
Just so you know, your solution appears to be O(logk(n+m)). The reason is that ArraySplice() makes a copy of the array, which takes either O(n) or O(m) time. If you would just avoid doing the copy and instead pass a starting index for each array to your function, you would be down to O(logk) time. – JS1

Actionable Items:

1. Read a few articles about the algorithm, list here:

2. Write a new version of algorithm to solve all issues, post it on code review. Learn by doing.

3. C# practice with the correction of time complexity issue - array splice. Code is here.

No comments:

Post a Comment