MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Become a Premium Member and unlock a new, free course in leading technologies each month.

Solved

Posted on 2008-06-16

Bob has a set A of n nuts and a set B of n bolts, such that each nut in A has a unique matching bolt in B.

Unfortunately, the nuts in A all look the same, and the bolts in B all look the same as well. The only kind of a comparison that Bob can make is to take a nut-bolt pair (a,b) such that a is in B, and test it to see if the threads of a are larger, smaller, or a perfect match with the threads of b. Describe and analyze an efficient algorithm for Bob to match up all of his nuts and bolts.

Unfortunately, the nuts in A all look the same, and the bolts in B all look the same as well. The only kind of a comparison that Bob can make is to take a nut-bolt pair (a,b) such that a is in B, and test it to see if the threads of a are larger, smaller, or a perfect match with the threads of b. Describe and analyze an efficient algorithm for Bob to match up all of his nuts and bolts.

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

- Help others & share knowledge
- Earn cash & points
- Learn & ask questions

7 Comments

That would run in O(N^2) time. So when the question says "describe an efficient algorithm", it wants something better than the obvious.

continue until matching y is found.

Get bolt x2, compare with y1. if y1 is larger go to "small" pile and search. dividing into small 1 and small 2. If y1 is smaller then go to "large" pile and search, dividing into large 1 and large 2.

If not found in already searched piles, go to remainder of original pile of nuts. again dividing into large and small.

get bolt x3, compare to y2 and y1 to determine which of the prior semi-sorted nut piles to look through.

continue through each bolt, compare to previous bolt's nuts to try find smaller piles to search. As you go through the bolts the piles should get smaller but more numerous with each being closer and closer to a full sort by size.

If you can get any kind of inter-bolt comparison or inter-nut comparison (which it sounds like you've already eliminated) then you can make it more efficient. but if you can only compare bolts to nuts then I think semi-sorted piles is about as good as you'll get as it will let you derive a sorting that will help over a simple n^2 comparison

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Title | # Comments | Views | Activity |
---|---|---|---|

Find k nearest restaurants to customers | 15 | 617 | |

stack peek and pop methods to get binary of number | 12 | 132 | |

Plotting confidence bands from data fitted using Levenberg–Marquardt algorithm. | 6 | 154 | |

how to find out if an array contains all true or all false or partially true | 7 | 103 |

In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This video…

- Shell Scripting
- Programming Languages-Other
- Scripting Languages
- Notepad
- AutoHotkey
- *Scripts, Programming

Course of the Month3 days, 2 hours left to enroll

Join the community of 500,000 technology professionals and ask your questions.