Amazon Interview Question
Quality Assurance EngineersCountry: India
let's |S1|=n and |S2|=m
If the array is not sorted, it means we have to see each element at least once. So we can easily do a normal merge and then run Selection Algorithm on merged array. It would be O(n+m)
But the problem is interesting when both arrays are sorted.
O(K) approach is to simulate merge operation of merge sort and find the k-th element.
But It can be solved in O(logn+logm).
You can find a clear and comprehensive explanation and implementation in leetcode website. I can't copy the link here, so just search in google "finding kth element of two sorted arrays leetcode" and hit the first link!
1.Check if both lists are empty,then it should throw some error.
2.Check if one list is empty and other is non-empty,then also it should throw some error.
3.Check if both lists are non-empty.
4.Check if non-numeric lists are present.
5.Count totals no of element in both the list.
6.Merge list1 with list2.
7.while merging keep on removing,duplicate elements from list2 which are already present in list1.
8.calculate size of merged list.
9. check if size of merged list is smaller than kth element.
10.check if size of merged list is >= to kth element.
11.check if merged list is already sorted or not.
K size minHeap to solve the problem.
Loop through the two lists, insert the minHeap until size K. After size K, compare current value with minHeap.peek(). if more then the peek value, remove peek and insert current value, if less than skip. The kth largest number is the peek, after the whole loop.
My thoughts:
- rob September 14, 2015Firstly, pass inputs to test the merge:
1) empty lists
2) 1 empty / 1 nonempty
3) 2 non empty
Pass inputs to test finding the kth element:
1) size of merged list is less than k
2) size of merged list is greater than/equal to k
Also, will function notify programmer when lists of non numeric types passed to the function?
Compare outputs of functions to the programs specification. Do these inputs return the expected output? Eg, if lists are empty, should exception be thrown (b/c returning an int, such as a -1, could be confused as the kth to largest element)?