Google Interview - Celebrity Problem

Celebrity problem:

You have a room with n people. A celebrity walks in. Everyone knows the celebrity, the celebrity knows no one. Non-celebrities may/may not know anyone in the room. Give an algorithm to find the celebrity. Discuss the complexity.

 

Mathematical formulation. Let G = (V, E) be a directed graph (represented by, say, its incident matrix). There is a vertex for each of the n people, and an edge from u to v if person u knows person v. We define a sink of a directed graph to be a vertex with indegree n − 1 and outdegree 0. A celebrity corresponds to a sink of the graph. We note that a graph can have at most one sink.

 

Brute-force solution. The graph has at most n(n − 1) edges, and we can compute it by asking a question for each potential edge. At this point, we can check whether a vertex is a sink by computing its indegree and its outdegree. This brute-force solution asks n(n − 1) questions. Next we show how to to do this with at most 3(n − 1) questions and linear place.

 

An elegant solution. Our algorithm consists of two phases: in the elimination phase, we eliminate all but one person from being the celebrity; in the verification phase we check whether this one remaining person is indeed a celebrity. The elimination phase maintains a list of possible celebrities. Initially it contains all n people. In each iteration, we delete one person from the list. We exploit the following key observation: if person 1 knows person 2, then person 1 is not a celebrity; if person 1 does not know person 2, then person 2 is not a celebrity. Thus, by asking person 1 if he knows person 2, we can eliminate either person 1 or person 2 from the list of possible celebrities. We can use this idea repeatedly to eliminate all people but one, say person L. We now verify by brute force whether L is a celebrity: for every other person i, we ask person L whether he knows person i, and we ask persons i whether they know person L. If person L always answers no, and the other people always answer yes, the we declare person L as the celebrity. Otherwise, we conclude there is no celebrity in this group.

  

Correctness. During the elimination phase, we maintain the invariant that is there exists a celebrity, then the celebrity is on the list. We can prove this by induction on the number of iterations. Thus, when elimination phase ends, either person L is a celebrity or there is no celebrity.

 

Analysis. The elimination phase requires exactly n − 1 questions, since each question reduces the size on the list by 1. In the verification phase, we ask L n − 1 questions, and we we ask the other n − 1 people one question. This phase requires at most 2(n − 1) questions, possibly fewer is L is not a celebrity. So the total number of questions is 3(n − 1). To efficiently implement the elimination phase, we maintain a queue that contains the remaining celebrities. Initially, we insert all n people to the queue. At each iteration we remove the top two elements off the queue, say v and w, and ask v whether he (or she) knows w. Depending on the outcome, we either insert v or w at the end of the queue. Each queue operation rakes Θ(1) time, so the whole process takes Θ(n) time.

public int findCelebrity(int[] persons) {
	Queue<Integer> queue = new LinkedList<>();
	for(int p:persons) {
		queue.offer(p);
	}
	while(queue.size()>1) {
		int a = queue.poll();
		int b = queue.poll();
		if(hasAcquiantance(a, b)) {
			queue.offer(b);
		} else {
			queue.offer(a);
		}
	}
	int c = queue.poll(); // possible celebrity
	for(int p:persons) {
		if(p == c) continue;
		if(hasAcquiantance(c, p) || !hasAcquiantance(p, c))
			return -1;
	}
	return c;
}

 

我们还可以使用Stack来实现：

public int findCelebrity(int[] persons) {
	Stack<Integer> stack = new Stack<Integer>(); // 或者可以使用队列Queue
	for(int person: persons) {
		stack.push(person);
	}
	Stack<Integer> verifyStack = (Stack<Integer>) stack.clone(); //供最后验证用
	int A = stack.pop();
	int B = stack.pop();
	while(stack.size() > 1) { // 直到剩余一个人为止 
		if(hasAcquiantance(A, B)) { // A认识B，说明A不是名人  
			A = stack.pop(); // 舍弃A，取出新的人代替A继续查找  
		} else {
			B = stack.pop();
		}
	}
	// 因为最后一个人还没被检查，所以要把C和A，B比较，有可能为名人
	int C = stack.pop(); // 保存名人
	if(hasAcquiantance(C, A)) {
		C = A;
	}
	if(hasAcquiantance(C, B)) {
		C = B;
	}
	
	while(!verifyStack.isEmpty()) {
		int E = verifyStack.pop();
		if(E != C) {
			// 如果C认识E，说明C不是名人，因为名人不可能认识别人  
			if(hasAcquiantance(C, E)) {
				return -1;
			}
			// 如果E不认识C，说明C不是名人，因为大家都认识名人  
			if(!hasAcquiantance(E, C)) {
				return -1;
			}
		}
	}
	return C;
}

 

Reference:

http://webcourse.cs.technion.ac.il/234247/Spring2006/ho/WCFiles/Celebrity.pdf

http://www.cs.princeton.edu/courses/archive/spring13/cos423/problem0-1.pdf

http://www.geeksforgeeks.org/the-celebrity-problem/