Microsoft Interview Question

  • microsoft-interview-questions
    0
    of 0 votes
    21
    Answers

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

    - softy on July 15, 2012 in United States for bing Report Duplicate | Flag
    Microsoft Algorithm

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.

- Vannu on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymzz on January 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 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?

- Liton on July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- airfang613 on July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

!!! Sexo soln. perfect..:)

- abh007 on July 25, 2012 | Flag
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 !

- softy on July 15, 2012 | Flag Reply
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?
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.

- Yoda on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
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

- Yoda on July 15, 2012 | Flag Reply
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).

- han on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cobra on July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Superlike..!!!

- Gupta on July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lol read questions properly :)

- cs on July 23, 2012 | Flag
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....

- vishal sharma on July 18, 2012 | Flag Reply
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;
}

- Annonymous on July 19, 2012 | Flag Reply
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]))
{
//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();
}

}

- anuprao85 on August 19, 2012 | Flag Reply
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 
  }
}

}

- Vincent on September 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vincent on September 24, 2012 | Flag
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?

- cobra on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on July 17, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More