Celebrity Problem - Medium

Problem : In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn't know anyone in the party. We can only ask questions like “does A know B? Find the celebrity in minimum number of questions.

This is a very interesting problem. The answer, ie the least number of questions required, changes based on what's given. Are we guaranteed there's one celebrity in the party? Does every non-celeb know every other non-celeb? ( not very ideal, but under a best case scenario. )

Once again, the rules

• There is at most one celebrity at the party
• Everyone knows the celebrity.
• The celebrity knows no one.
• We can only ask the question "Does A know B?"

When we ask the question, we can get a "yes" or "no". Each conveying information about both the participants in the question. Let's see those outcomes...

If the Answer is "Yes", we know A is definitely not a celebrity. But B is a candidate for a celebrity.

If the Answer is "No", we know both A and B are both candidates or both are Non-Celebrities.

Turns out, we can do this in linear time. We love those kinds, don't we?

Here we simply assume the first guy is a celeb. Each time you will ask a question

Does my assumed-celeb know the current-guy ?

 There are two outcomes,

• If the answer is "Yes", we know our assumption was wrong,we can eliminate our assumption. But the next-guy could be a celeb. So we make him our new assumption.
• If the answer is "No", our assumption is holding strong, we can safely eliminate the current-guy.

Evidently, every time you ask the question, one guy gets eliminated from candidacy. So we'll need to ask (n - 1) questions to get one strong candidate.

At this point, if we were assured there was one celeb we can end the algorithm here. If there's a possibility, there was no celebrity, we'll have to perform one more scan to eliminate the end guy as well.

Theoretically, that's (n - 1) questions. So we need to ask a minimum of 2(n-1) questions to figure out the celebrity. I'll attempt to prove the lower bound some other time, will be handy for my Algorithm class.

	import random
	N = 10
	#prepare testcase
	R = range(N)
	rand_celeb = random.randint(0,N-1)
	m = {}
	for i in xrange(N):
	if i != rand_celeb:
	m[i] = [random.randint(0,N-1) for j in xrange(10)] + [rand_celeb]
	else:
	m[i] = []
	def knows(i,j): #i knows j?
	return j in m[i]
	def find_celeb(n):
	celeb = 0
	for i in xrange(1,n):
	if not knows(i,celeb):
	celeb = i
	for i in xrange(n):
	if i != celeb and knows(celeb,i):
	return None
	return celeb
	print R
	print "Actual Celeb : ",rand_celeb
	print "Found Celeb : ",find_celeb(len(R))

view raw Single Celebrity Problem hosted with ❤ by GitHub

Let's extend this a bit, assume there were multiple celebrities at the party (or None). (A celeb doesn't know another celeb.) Although, I don't claim this is the most efficient algorithm, it certainly works. The first part of the solution remains the same, we find a celebrity, any one will do. Notice the original algorithm will do this for you. We include one more pass at the end, asking the question "Does X know Celebrity?". If the answer is "No", we KNOW that X is another celebrity. Here's the code.

	import random
	N = 100
	#prepare testcase
	R = range(N)
	rand_celeb = list(set(random.randint(0,N-1) for i in xrange(5)))
	m = {}
	for i in xrange(N):
	if i not in rand_celeb:
	m[i] = [random.randint(0,N-1) for j in xrange(10)] +rand_celeb
	else:
	m[i] = []
	def knows(i,j): #i knows j?
	return j in m[i]
	def find_celebs(n):
	celeb = 0
	for i in xrange(1,n):
	if not knows(i,celeb):
	celeb = i
	celebs = []
	for i in xrange(n):
	if i != celeb and knows(celeb,i):
	return None
	if not knows(i,celeb):
	celebs.append(i)
	return celebs
	print R
	print "Actual Celeb : ",rand_celeb
	print "Found Celeb : ",find_celebs(len(R))

view raw Multiple Celebrity Problem hosted with ❤ by GitHub

Lovely question, Thanks to CodeBunk for posting it.