Microsoft Interview Question
Team: bing
Country: United States
Interview Type: In-Person
Step 1. Perform pair-wise comparison.
Total # comparison = N/2.
In every comparison
if isKnown(a , b) = true then
b could be a celebrity.
else
a could be celebrity.
Step 2. After step 1, there will be N/2 candidates for celebrity. Again Compare pair-wise among these N/2. Total # of comparison is = N/4. resulting in N/4 candidates.
Step 3. Similar to previous steps. Total compariosn is N/8 and results in N/8 candidate
4. Continue until one winner/celebrity comes up.
complexity : T(n) = N/2 + N/4 + N/8 + ...+1 = O(N)
Does it make sense?
this sounds like an interesting solution... but to be honest, I didn't quite understand OP's question, what does he mean by "at least one person knows other"?
Understand the basic premise:
If A knows B ==> A can't be celebrity, since celebrity knows no one
If A Does not Knows B==> B can't be celebrity, coz Everyone knows the celebrity.
Hence if you ask this ques to every one successively, at each call to isKnown() you eliminate one person. You need to ask everyone once to get a final person who may or may not be celebrity. Lets say this person is X
Now if it is not guaranteed that thr is atleast one celebrity you need to ask every one again 1)Do you know X?
and ask X
2) Mr. X Do you know a[i]?
The answer of ques 1) should always be yes and ques 2) should always be NO.
If this succeeds then we get our celebrity in 3n comparisons.
As per the question, there is a celebrity for sure. So no need to re-verify celebrity. Eliminating part is sufficient to find celebrity.
class person
{
public int id;
public int[] knownPersonId;
public person(int id, int[] knownPersonId)
{
this.id = id;
this.knownPersonId = knownPersonId;
}
}
class FindCelebrity
{
public person findCelebrity(List<person> candidatesforCelebrity)
{
List<person> p = GetCelebrityCandidatePeople(candidatesforCelebrity);
if (p.Count == 1) return p[0];
else
return findCelebrity(p);
}
public List<person> GetCelebrityCandidatePeople(List<person> candidatesforCelebrity)
{
List<person> newcandidates = new List<person>();
for (int i = 0; i < candidatesforCelebrity.Count; i++)
{
for (int j = 0; j < candidatesforCelebrity.Count; j++)
{
if (IsKnow(candidatesforCelebrity[i], candidatesforCelebrity[j]))
{
//candidatesforCelebrity.Add(people[j]);
newcandidates.Add(candidatesforCelebrity[j]);
}
}
return newcandidates;
}
return newcandidates;
}
public Boolean IsKnow(person a, person b)
{
Boolean know= false;
for (int i = 0; i < a.knownPersonId.Length; i++)
{
if (a.knownPersonId[i] == b.id)
{
know = true;
return know;
//break;
}
}
if (!know)
{
return know;
}
return know;
}
public static void main()
{
List<person> persons= new List<person>();
persons.Add( new person(1, new int[] { 2,3,4 }));
persons.Add( new person(2, new int[] { 1,3,4 }));
persons.Add( new person(3, new int[] { 1,4 }));
persons.Add( new person(4, new int[] {}));
persons.Add( new person(5, new int[] { 2, 4 }));
FindCelebrity c = new FindCelebrity();
person p = c.findCelebrity(persons);
Console.Read();
}
}
set unknown = createSet(All the people)
set notCelebrity;
while(size(unknown)>1)
{
randomly choose two people from unknown (first,second);
if(knows(first,second))
{
remove first from unknown and put into notCelebrity;
}
else
{
if(knows(second,first))
{
remove second from unknown and put into not Celebrity;
}
else
{
// first doesn't know second and second doesn't know first
remove first and second from unknown and put them into notCelebrity
}
}
}
By using adjacency list in directed graph, we can solve it
take a vertex say from 10 vertices and see the adjacent vertex(let it be 3 vertices)
now take only these 3 adjacent vertex and look for the vertex which doesnt have the adjacent vertex
this vertex is the celebrity
...
is there any other solution?
Well, Graph will work but I feel like making extra structure for nodes will be a little complex.
- Vannu July 15, 2012How about using QuickSort Algo. choose a random person let say Pivot.
ask all others whether they know him or not. people who know him will come to left of him and people don't know him will come to right side.
after asking everyone if Pivot is the rightmost then he is the celebrity ortherwise follow the same steps for right side people of Pivot(Pivot will be excluded from the set because right side people don't know him so he can't be celebrity).
Running time will be same as solving it with Graph.