is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
Assuming these are arrays and not lists:
- Stefan March 26, 2014here is an algorithm similar to what jj suggested (actually identical, but explained differently).
1. compere elements in the first array and second array at position floor(k/2)
2. logically remove the first k/2 elements from the array which has the min and make then part of the answer(i.e. remember that the array now starts at position k/2).
3. repeat the exact same problem for k-k/2=k/2, i.e. find the smallest k/2 elements from the two new arrays.
this indeed gives logk time complexity
the nice thing is that the algorithm is generalizable:
given n sorted arrays, find the k smallest elements:
1. compere elements in the first array and second array at position floor(k/n)
2. logically remove the first k/n elements from the array which has the min and make then part of the answer(i.e. remember that the array now starts at position k/n).
3. repeat the exact same problem for k-k/n, i.e. find the smallest (n-1)k/n elements from the new arrays.
4. when k/n is 1 (or 2, or some small value), just dump them into a heap of size k (the newest value of k)
The complexity of this is "left as an exercise to the reader", because I have no clue how to compute it. Intuition tells me it is nlognk, but I have no idea how to prove it.(not even an upper bound)
Which bring us to the second problem: what if we have n sorted lists ?
1. we use a min heap of size n
2. we put all the first elements into the heap. We have n lists, and the heap is of size n, so that's nice.
3. we remove the min from the heap, add it to the final result, and insert the next element from the same list where the min was previously (min->next)
4. we continue to do step 3 k times (actually k-1)
complexity?
to build the heap of n elements is O(n). To do a replaceminwithnewelement in a heap of size n is O(logn) and we have to do it k times. So n+klogn. Lets check. if n=2 (we have 2 lists, and we keep moving the pointer in the list with the smaller element, which is essentially a heap of size 2), it will take k operations. Indeed 2+klog2 is O(k).