Puzzle: The Celebrity Problem

9333 views
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 does not know anyone in the party. We can only ask questions like does A know B? . Find the stranger (celebrity) in minimum number of questions.

We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, false otherwise.
We measure the complexity in terms of calls made to HaveAcquaintance().
12 Vote Up   |   Post Answer

By  Ic Admin





Sangeeta Haldhar Sangeeta Haldhar   11 years ago

N-1

Reply    1 Vote Up   0 Vote Up


Roshan Roshan   11 years ago

Also known as the “mayor problem” or “mayor puzzle”, this is a directed graph puzzle where a group of people have single directed relationships. That is person A knows person B, but person B may or may not know person A. The puzzle is to find a person in this group that everyone knows, but he only knows himself. To phrase it differently, this breaks down to two conditions:
1) person C must be known by everyone, and
2) person C must know no one but himself.
Method 1(Brute Force):
The obvious solution is to compare every member to every other member and that would give you a solution that runs in O(n^2). If we’re given a function called 'HaveAcquaintance()' that accepts two arguments (and returns in O(1)), we can write a PHP function like this:
function celebrityMayor(){
$townSize = 5;
$candidates = array();
// 1) The mayor must know no one.
for( $i=0; $i < $townSize; $i++ ){
for( $j=0; $j < $townSize; $j++ ){
if( HaveAcquaintance($i,$j) && $i != $j )
break;
if( $j == $townSize - 1)
$candidates[] = $i;
}
}
// 2) Every one must know the mayor.
foreach( $candidates as $c ){
for( $i=0; $i < $townSize; $i++ ){
if( !HaveAcquaintance($i,$c) && $i != $c )
break;

if( $i == $townSize - 1 )
return $c;
}
}
}
Method 2(An efficient Approach):
While this may work, it's hardly ideal. We need a way to disqualify a candidate with every iteration over the list. This way, with one pass over the list we can remove anyone that is not the mayor / celebrity.
function celebrityMayor(){
$townSize = 5;
$mayor_set = array();
for( $i=0; $i < $townSize; $i++ )
$mayor_set[] = $i;

for( $i=0; $i < count($mayor_set); $i++ ){
for( $j=0; $j < count($mayor_set); $j++ ){
if( $i == $j )
continue;
if( HaveAcquaintance($i, $j) ) {
// 1) The mayor must know no one.
unset($mayor_set[$i]);
} else {
// 2) Every one must know the mayor.
// if i doens't know j, then j can't be the mayor
unset($mayor_set[$j]);
}
}
}

return array_shift($mayor_set);
}
Reading the algorithmic complexity of this code can be tricky. Seeing a nested for loop usually means O(n^2), but in this case we are eliminating one element from the $mayor_set with every iteration so we only require one pass to find the mayor, i.e O(n). This does require enough memory to hold the a list of identifiers for the entire town, so this algorithm may not work on very large data sets.

Reply    0 Vote Up   0 Vote Up