Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Time Complexity O(n) where n ==length of 1st N values to return
public ArrayList<Node> firstN(int n,Node curr1,Node curr2)
{
//note please do these 2 steps using bitwise divison using strings to avoid integer overflow error
int noMaxInt=n/Integer.Max;
int remainder=n%Integer.Max;
ArrayList<Node> toSend=new ArrayList<Node>();
for(int i=0;i<noMazInt;i++)
{
for(int i=0;i<integer.Max;i++)
{
if(curr1.value<=curr2.value)
{
toSend.add(curr1);
curr1=curr1.next;
}
else
{
toSend.add(curr2);
curr2=curr2.next;
}
}
}
while(remainder !=0)
{
if(curr1.value<=curr2.value)
{
toSend.add(curr1);
curr1=curr1.next;
}
else
{
toSend.add(curr2);
curr2=curr2.next;
}
remainder--;
}
return toSend;
}
}
Returning k element in sorted order.
public static String returnElement(ArrayList<Integer> first, ArrayList<Integer> second, int k) {
String res ="";
int time = 0;
int left = 0;
int right = 0;
while(time < k) {
if(first.get(left) < second.get(right)) {
res += first.get(left) + " ";
time++;
left++;
} else if(first.get(left) > second.get(right)) {
res += second.get(right) +" ";
time++;
right++;
} else {
res += first.get(left) + " " + second.get(right) + " ";
left++;
right++;
time++;
}
}
return res;
}
pseudo code
// L1 and L2 are the two sorted list, and RL is the return list
ArrayList<int> GetFirstKElements(ArrayList<int> L1, ArrayList<int> L2, int k) {
int i, j, len1, len2, count;
i = j = len1 = len 2 = count = 0;
ArrayList<int> RL = new ArrayList<int>();
len1 = L1.size();
len2 = L2.size();
while(count < k) {
if(i<len1 && j<len2) {
if(L1.get(i) < L2.get(j) {
RL.add(L1.get(i));
i++;
} else {
RL.add(L2.get(j));
j++;
}
} else if (i>= len1 && j<len2) {
RL.add(L2.get(j);
j++;
} else if(i<len1 && j>=len2) {
RL.add(L1.get(i);
i++;
}
count++;
}
return RL;
}
The solution looks fine. If you could write the logic before giving the code it will be easy for everyone to understand. That the only reason I could guess for the downvote.
If you don't care about whether the returned numbers are in order (which the problem doesn't ask for) I think you can get a log(k) solution by using a form of binary search to decide how many numbers from each list you want. Start by looking at the k/2 element from each list. Whichever one is smaller, switch to the k/4 element of that list and the 3k/4 of the other list. Then, depending on which of these is smaller, add k/8 to one side and subtract k/8 from the other. Once 2^n is more than k, you can stop and the position of the pointers will tell you how many numbers to return from each list.
Assuming these are arrays and not lists:
here 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).
Your algorithm seems to be incorrect.
Consider the case,
List1: 1, 4, 6, 10, 11
List2: 2, 3, 20, 40, 60
And you need to find the top 2 elements. Using your algorithm we compare 4 and 3 and end up picking 2, 3 from List 2 as the answer.
- echen57 February 09, 2014