There is a city of N people. The government learnt that some unfriendly nation planted a spy there. A spy possesses unique characteristics: he knows everybody in the city, but nobody knows him.
You are a counteragent sent by the government to catch the spy. You may ask the people in the city only one question: "Do you know the person X?" You may ask as many people as you wish, and one person may be asked as many times as you wish. All the people, including the spy, always answer honestly. How many questions you need to find out who is the spy? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
