Interview Question
Country: United States
Interview Type: Written Test
1. Initialize a min-heap of size k.
2. Insert the first k elements from the list of n numbers.
3. Next, for each number in the list of n compare with the heap root.
4. If more, then extract from heap and insert the element from the list of n.
5. After a linear sweep of all the n elements, you will have a list of k numbers whose sum is max from the heap elements.
6. Time Complexity: O(nlogk)
hi should this be O((n-k)logk)? since when a number is exacted from the heap, it will never go back.
@Cod: Doesn't matter since we don't know the order relationship between n and k, and so the upper bound is O(nlogk).
1. Use Selection to find the k-th element: O(n)
2. Go through the array and output all elements that are less (not less or equal !!) than the k-th element.
3. Fill in the remaining gap between the number of output elements and k, with that many copies of the k-th element.
Step 2 is important because if you have an array like [5, 5, 5, 5, 5, 5, 1, 2, 8] and you want to output the smallest 4 elements, your 4th element will be 5, and if you had >= sign, then in step 2, you'll output [5, 5, 5, 5] instead of: [1, 2, 5, 5]. That is why we first output the smallest elements and then we fill in the gap.
I agree with the question above. If all I want it K numbers whose sum is highest, then is it the set of largest K elements from the list of size n? I can use merge sort in O(nlogn) time and then pick the first K elements.
public static int[] findMostK(int[] test,int K){
if(test==null){
return null;
}
if(test.length<=K){
return test;
}
int[] result=new int[K];
for(int i=0;i!=K;i++){
creatMinHeap(result,test[i],i);
}
for(int i=K;i!=test.length;i++){
if(result[0]<test[i]){
result[0]=test[i];
adjustMinHeapFromTop(result,0);
}
}
return result;
}
public static void creatMinHeap(int[] result,int newItem,int index){
result[index]=newItem;
int parent=(index-1)/2;
while(parent>=0){
if(result[parent]<=result[index]){
break;
}
else{
swap(result,parent,index);
index=parent;
parent=(index-1)/2;
}
}
}
public static void adjustMinHeapFromTop(int [] result,int index){
int left=index*2+1;
int right=index*2+2;
if(right<result.length){
int nextIndex=index;
if(result[nextIndex]>result[left]){
nextIndex=left;
}
if(result[nextIndex]>result[right]){
nextIndex=right;
}
if(nextIndex==index){
return;
}
else{
swap(result,index,nextIndex);
adjustMinHeapFromTop(result,nextIndex);
}
}
else if (left<result.length){
if(result[index]>result[left]){
swap(result,index,left);
}
}
return;
}
public static void swap(int[] result,int o1Index,int o2Index){
int tmp=result[o1Index];
result[o1Index]=result[o2Index];
result[o2Index]=tmp;
}
Can you clarify ? What is K here ?
- jk October 02, 2012