## Microsoft Interview Question

• 0

there are N people in a room one of them is a celebrity .At least one person knows other but all knows celebrity.Celebrity doesnt know any one.There is an api isKnown(a,b) which returns true if a knows b.y.
I gave the O(n2) answer.
But I think this can be done in O(n) .We have to compare call isKnown(a[i],a[i+1]) && iskNown(a[i+1],a[i]) returns true remove both frmo the array else remove that a[i] which return true, this will reduce the array to the celebrity. order will be O(n) then.Your thoughts ??

Team: bing
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

Well, Graph will work but I feel like making extra structure for nodes will be a little complex.

How 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.

Comment hidden because of low score. Click to expand.
0

let's say A knows B and B knows C and C knows A.
How do you handle such cases??.I dont know my wuestion might be wrong too.

Comment hidden because of low score. Click to expand.
3
of 3 vote

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?

Comment hidden because of low score. Click to expand.
0

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"?

Comment hidden because of low score. Click to expand.
0

!!! Sexo soln. perfect..:)

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry "Interviewer said we can use Graph I dont know how?" this was not for this question !

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?
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.

Comment hidden because of low score. Click to expand.
0

As per the question, there is a celebrity for sure. So no need to re-verify celebrity. Eliminating part is sufficient to find celebrity.

Comment hidden because of low score. Click to expand.
0
Comment hidden because of low score. Click to expand.
0
of 0 vote

Graph solution is:
Make all person as nodes. Now connect each from A->B s.t: A knows B. The celebrity will be one with indegree = n-1 and out degree =0

Comment hidden because of low score. Click to expand.
0
of 0 vote

a knows b also means b knows a ??
if so, this problem can be solved in o(n).

Comment hidden because of low score. Click to expand.
0

i know president of india.. but the president of india dont know about me..

Comment hidden because of low score. Click to expand.
0

Superlike..!!!

Comment hidden because of low score. Click to expand.
0

lol read questions properly :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

isKnown(a,b), if it returns true that means... a is not celebrity (as a knows b) and if it returns false that means b is not celebrity ... it implies that after each call we can eliminate on candidate to be celebrity as there are n ppl, n-1 comparison will be needed....

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int findcelebrity(int[] A){
int i=0,j=0;
int n = A.length;

for(i=0; i<n;){
for(j=i+1;j<n;j++){
if(! isknown(a[j],a[i]){
break;
}
}
if(j==n){
break;
}
else{
i = j;
}
}
return i;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]))
{

}
}
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);

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
}
}

}``````

Comment hidden because of low score. Click to expand.
0

Eventually, there is one left in unknown, which must be the celebrity

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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?

Comment hidden because of low score. Click to expand.
0

Creating adjacency list itself is a O(n^2).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.