1

Consider a set A of n bottles and set B of n caps, such that each bottle in A has unique cap in B. But bottle in A and caps in B all look the same. The only comparison that can be made is pair (a,b) of a bottle in A and a cap in B and test whether the threads of a are smaller, larger or perfect with threads of b.

Give an efficient algorithm to match up all bottles with their caps.

PS: This seems like I haven't done anything to get the solution, belive me, I did. Please just give me an answer.

ChrisWue
  • 18,612
  • 4
  • 58
  • 83
IRock
  • 127
  • 3
  • 11
  • 1
    It would help if you showed your work. Otherwise it really sounds like you're trying to get someone to do your homework for you. A rigorous proof for the correct algorithm is about 1/2 a page, by the way, so you can probably come up with it after a bit of thought. – Matt Bryant Oct 02 '13 at 20:19
  • [This](http://stackoverflow.com/questions/14415881/how-to-pair-socks-from-a-pile-efficiently) may help you. It is another matching algorithm question. – Benjamin Trent Oct 02 '13 at 20:19
  • If the thread property of bottles and caps is comparable, you can sort the sets. – Ted Hopp Oct 02 '13 at 20:24

1 Answers1

1

Nice problem but as it was pointed before it seems a Homework, why you don't try something like this:

you should cycle for each bottle (without any logical order) you should have the caps in a kind of structure that is a dynamic sorted array of caps sets, this array is initialized having only one element (that is the set B).

and for each bottle you should travel in your array using Binary Search when you get the "potential" set of caps, you check cap by cap

  • if the cap is smaller you let it in the same set (marking it to not taking again for that bottle
  • for the first greater cap, you need to insert a set between the current set and the next one and put the cap there
  • for the following greater caps you put them in the previously created set
  • if you find the correct cap you have a match and continue splitting with the same bottle the remaining caps of the set, after that you continue with the next bottle
  • if in the current set you dont find any cap, but all the caps you have checked are greater you can travel using binary search for the lower caps
  • if in the current set you dont find any cap, but all the caps you have checked are lesser you can travel using binary search for the bigger caps

Edit: i have seen the posted coment and indeed it is duplicate from Two sets of items. Each element of set A a unique match in set B. Match each item of set A to item in set B in O(nlogn) time and the solution is explained here http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html

quite similar to mine, but bottles can be partitioned also.

Community
  • 1
  • 1
Qsebas
  • 458
  • 3
  • 15