Interview brainteaser asked at Google

Problem.
You are in the room with n computers. Some of them are good, and some of them are bad. You can query any computer about the status of any computer in the room. Good computers will always tell you the truth. Bad computers can answer anything. You also know that there are more good computers in the room than bad ones. How will you find a good computer in the room, and how many queries will you need?

Solution.
The idea is to construct a sequence of queries that produce the sequence of answers of the form “good -> good -> good … -> good”. We should be able to do so because we know that there are more good computers in the room than bad ones. After we queried all computers in the room and are left with this chain, we know that there is some good computer in the chain. Therefore, the last computer will be good. To be concrete, we can go as follows:
Pick any computer and query it about the status of some other computer. If it answers “good” – add it to the back of the chain; if it answers “bad” – discard both and don’t query them any more. Pick another computer and query it about the status of the last computer in the chain (if the chain is empty pick any computer that has not been discarded before). If it answers “good” – add it to the back of the chain; if it answers “bad” – discard it along with the last computer in the chain (so that chain shrinks by one in this case). Keep doing it. Your chain is guaranteed to be non-empty after all computers are queried because you always discard as many bad computers as good ones.
The number of queries required is n – 1.

Advertisements
This entry was posted in Interview, Math and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s