Adobe Interview Question Software Engineer / Developers
its like select any random bolt and for try with each nut. Now u will know all the nuts which are larger than this and smaller than this. this bolt will be like pivot and again you would have two search domains. again sort these domains like quick sort.
wont work...this is because u wont know if the next nut u pick wud be smaller than previous or not....so again u have to search the whole set of remaining bolts
srry.... on second thought i got it...actually correcting ur lines the solution is:
its like select any random bolt and for try with each nut. Now u will know all the nuts which are larger than this and smaller than this. NOW WHEN YOU PICK NEXT BOLT THE NUT FOUND OUT IN FIRST (AND NOT THE BOLT) will be like pivot and again you would have two search domains. again sort these domains like quick sort.
Each bolt will have its matching nut.
Now, say first time, when you choose a bolt and try to match its nut with each of available nuts. Here, if choosen nut is smaller to fit the bolt, put it in left side else put it in right side. Finally, in first pass, you will have a matching nut-bolt and some nuts on left(smaller than matching nut) and some nuts on right(bigger than matching nut).
So, for second bolt, try the bolt with previous matched nut, if it is smaller, then you need to search only right side collected nuts. And if it is bigger in size, then you need to search only left side collected nuts.
This way.. You will have a search to logN steps. First pass took N.
So, O(NlogN)
apply quick sort technique, here compare function will be comparing NUT with Bolt.
- Anonymous May 20, 2010