The Galactic Patrol

Saving the Universe from Boskone and Bugs

think you're good at puzzles? try this one.

I ran across this puzzle a little while ago.  I’m still working on it – now you can too:

You have a port that you are reading numbers from. You know that there is one number that is generated in more than half of the cases.  You keep reading numbers arbitrarily long until you are given a command to stop. When you stop you have to return the number that has occurred in more than half of the cases.

(Hint: you don’t have enough memory to store all the numbers)

Published Tuesday, December 09, 2003 2:41 AM by bwill

Comments

 

neil said:

read the first number - that's it
December 9, 2003 3:39 AM
 

Bruce said:

neil: that doesn't work, because you don't get to decide when to stop. "you are given a command to stop."
December 9, 2003 11:09 AM
 

Gp said:

I solved it. int n = readPort() int nplusone = readPort() HashMap list = new HashMap() while(not told to stop) { if (nplusone == n) { list.put(n, list.get(n) ? list.get(n)+1:1) } n = nplusone nplusone=readPort() } int count=0; int number; foreach(key in list) { if(list.get(key) > count) { count = list.get(key) number = key } } return number
December 11, 2003 7:59 PM
 

Gp said:

Oops, I think I found a case where that algorithm doesn't work. I think that the proper algorithm is to mark the longest chain of consecutive numbers, the number with the longest chain is the one you are looking for. Pidgeon hole principle I think.
December 12, 2003 1:25 AM
Anonymous comments are disabled

This Blog

Syndication

© 2009 Microsoft Corporation. All rights reserved. Terms of Use  |  Trademarks  |  Privacy Statement
Microsoft
Page view tracker