Google Interview Question
I think this is the first sensible answer on this thread.. Well Done!! I am pretty sure this will work, it is a small twist on QuickSort
Yes, this is known as "matching nut and bolts" problem. However, your O(nlogn) analysis is not quite correct. The recurrence is like:
T(n) = T(k) + T(n-k) + O(n)
which basically leads to O(n^2). However, O(nlogn) algorithm exists which was published in 1995 at some journal - which is too hard to grasp!
@lol
You are right. But I can define partition function to get exact O(nlogn) using median of five approach for partition. Adding the partition cost in the analysis still makes it O(nlogn) the recurrence will then become:
T(n) = T(n/5) + T(7n/10) + O(n)
Source: Wiki selection_algorithm
Quick sort and binary search. Pick one pivot cap and try all pens, eventually you will pair the first cap with its pen and successfully partition all the pens -- those smaller to the left and bigger to the right. Then pick the next cap. How to determine the which partition?. Try on the pen(s) you already capped. When we have more pens, it will looks like a binary search.
Using this method, to be able to find immediately the partition in which a cap would belong, you need to keep track of every partition made so far.
You can instead sort the pens and loop through the caps, binary searching among the pens for the right one.
complexity in sorting approach is N sqaure , in above approach it is much less. please feel free to correct me.
Maps caps by size, then iterate through pens and matches then.
Space: O(n)
Time: O(n)
public static void match(Cap[] caps, Pen[] pens) {
Map<Integer, Cap> capSize = new HashMap<Integer, Cap>();
for (Cap cap : caps) {
capSize.put(cap.size(), cap);
}
for (int i=0; i<pens.lengh; ++i)
caps[i] = capSize.get(pens[i].size());
}
I guess the question already says, you can't compare two caps or two pens, which means you can really tell which cap/pen's size.
construct a Binary tree
take a cap and using that as reference to break the pile into "loose" and "does't" fit. you would definitely find the pen that fits the cap.
take the second cap and compare with the pen that fits to root cap, if the new cap is too loose, select the to tight pile, if the cap is tight select the loose pile. now using this new cap as reference break the pile into loose and tight again.
approximate complexity is n + n/2 + n/4 + n/8 + .... + n/2^k = O(n log(n))
This approach achieves time complexity but its hard on space complexity.
Instead
int i=pens.length - 1;
int j= caps.length - 1;
while (i>=0) {
int k = j;
while (k >= 0) {
if(pens[i].fits(caps[k]) {
temp = caps[j];
caps[j] = caps[k];
caps[k] = temp;
i = i -1;
j = j - 1;
}
}
}
time complexity = n + n-1 + n-2 + ... + 1 = O(n^2)
Thinking out loud:
- Rohith August 05, 2011Can this be thought of as variant of quick sort. For eg: Take a cap and partition the pens depending on whether it is loose or tight. One will exactly fit. Use that pen and partition the caps too. Now do this recursively on the two partitions. O(nlogn).
Comments/Suggestions welcome.