4 ms·
Sure "only allowed to examine each ball once" should be "only allowed to examine each bucket once"? Otherwise you have to keep track of which balls you've looke
by to3m 11y ago
Sure "only allowed to examine each ball once" should be "only allowed to examine each bucket once"? Otherwise you have to keep track of which balls you've looked at already after swapping. Also, I can't figure out how to do it that way :)
- seabee 11y agoWell, the correct solution means you never want to examine each ball more than once anyway. It's the kind of constraint you can consider as existing 'outside' of the algorithm.
- white-flame 11y agoDescriptively, scan through the slots in order, stacking reds up on the left, and blues up on the right, leaving greens in the middle. You only need to remember how many reds & blues you've stacked up. Programmatically: LastRed = -1, LastBlue = numSlots - If the observed ball is red, swap with ++LastRed. Move the observing arm forward, as you've already observed the one swapped in. - If the observed ball is blue, swap with --LastBlue. - If the observed ball is green, leave it there. It might get swapped with a red later as LastRed grows. Move the observing arm forward. If the observing arm is at LastBlue, we're done. Loop.
- to3m 11y agoThanks! I managed to work it out in the end, after the other comment said it was possible :)
- maxlybbert 11y agoIt's highly unlikely that a candidate would recognize this as Dijkstra's Dutch National Flag problem ( http://www.drdobbs.com/cpp/a-classic-example-that-off-the-end-itera/240168707 http://www.drdobbs.com/cpp/a-classic-example-that-off-the-en... ).