Yahoo Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
This is not correct might be a and b both dont know each other then you cant exclude both.
Valid point santosh but you fail to understand the logic here. We are not looking at two people knowing each other, we are interested in knowing if one knows the other or not.(a knows b doesnt mean b knows a).
If a and be dont know each other, they both will eventually get eliminated. Try this out, trust me it works!
Well, that's a good algorithm if you have the full (N+1)x(N+1) matrix of the "knows" relationship.
In that case the "a knows b" test has O(1) complexity.
If you instead have, for each a, an array of the persons known by a, the test would be a look up function, with complexity (in the worst case of unsorted array) O(N). This gives an overall complexity of O(N^2).
In this case, assuming that isEmpty(array) is a O(1) test, you can still have O(N) complexity but the algorithm would be pretty trivial: test all the persons until you find the empty list.
Well, that's a good algorithm if you have the full (N+1)x(N+1) matrix of the "knows" relationship.
In that case the "a knows b" test has O(1) complexity.
If you instead have, for each a, an array of the persons known by a, the test would be a look up function, with complexity (in the worst case of unsorted array) O(N). This gives an overall complexity of O(N^2).
In this case, assuming that isEmpty(array) is a O(1) test, you can still have O(N) complexity but the algorithm would be pretty trivial: test all the persons until you find the empty list.
Sorry for double posting. It seemed to refuse the comment so I thought it needed a real e-mail address...
This one is correct, I was asked the same question in a phone interview with Google.
The key point is to use elimination. In the end, there will be only one candidate left. Then check if it is a true celebrity.
This one is correct, I was asked the same question in a phone interview with Google.
The key point is to use elimination. In the end, there will be only one candidate left. Then check if it is a true celebrity.
@sreemana
I agree a knows b does not mean b knows a. But a knows b also does not mean that b does not know a. Let say a knows b we exclude a. now our probablity is b.
Now consider there are only 3 peapole a b c and let say c is celebrety
with the follwing relation
a->b. i.e a knows b
b->a
b does not know c.
c does not know a and b.
now can you expain how your algo will work. I am little bit confuse. I might be wrong but need some more clarification.
Santosh, Read the question.
If c is the celebrity, the possibility of b not knowing c is invalid.
It looks like your assuming that one person gets eliminated in every comparison. Then, maybe we have O(n). Assume that everyone in the room do not know each other, and each person knows only one person, the celebrity. What would you do? In other words, what if you cannot eliminate
a,b,c,d,e,f,g,h,i,j on comparison and
'n' is the celebrity?
My solution would be a quicksort like technique, with each iteration pushing people into categories 'knows the person', 'does not know the person' where the person under comparison is like the pivot element. After an iteration we are interested only in the partition that contains people who don't know the pivot point
Gosh!!! Why don't you guys read the question properly.
If nobody knows anybody else other than the celebrity it becomes all the more easier.
If a doesnt know b (b defn is not the celeb)
and b doesnt know a (a defn is not the celeb)
Then a and b both aren't celebrities. You can always eliminate people. READ THE QUESTION CAREFULLY!
Gosh!!! Why don't you guys read the question properly.
If nobody knows anybody else other than the celebrity it becomes all the more easier.
If a doesnt know b (b defn is not the celeb)
and b doesnt know a (a defn is not the celeb)
Then a and b both aren't celebrities. You can always eliminate people. READ THE QUESTION CAREFULLY!
Hi this is good solution, but the time complexity should not be O(n), it should be O(nlogn), coz you cannot guarantee you can eliminate n-1 in the first round, the worst situation you can only delete n/2.
The O(n) solution where we keep them in a row and compare the current possible candidate with next person in row to eliminate either one of them or both of them as a candidate (posted by sreemana@buffalo.edu) works but with one catch.
After we do the first pass, if we are left with one possible candidate, we need to do another pass to confirm that he is indeed the celebrity. (that everyone else, to be precise, everyone else before him in the row know this person and he doesn't know any of those persons). We can return that candidate only after that check otherwise there is no celebrity.
Let me explain with an example: Let's say we have persons a,b,c,d and here are the relationships: a knows b, c knows b, b knows d, d knows a (other than these all other possible pairs are "does not know" case), in this scenario, at the end of the loop, we will have 'd' as celebrity but he is really not.
Take any person A let it be set S {a1,a2,a3};
Go to each person ax in set S.
if the ax has a know person he is not a celebrity.
else if ax knows none, then he is celebrity.
This methods can be done in time o(n). this is when the set S is considerably large ~n.
in an average case it should be of constant order.
if the ax knows none how can you say he is celebrity...according to question non celebrity may/may not know anyone in the room.
ax can be non celebrity also.
Celebrity dont know anyone, but non-celebrity should atleast know the celebrity(questions says everyone knows the celebrity)
Exactly. Someone is a celebrity iff they know no one. That's because any non-celebrity would know at least the celebrity.
suppose the celebrity is at last and assume every non-celebrity knows no one except celebrity,now it takes O(n2) time for finding celebrity,but not O(n).
plz read the comments for the correct solution before posting your's..Not to be rude or anything, but im tired of having to explain time and over again how the solution is O(n) for absolutely all situations!
Here is my Algo.
Asumption : Each person will have information with him as follows. Let's say xyz is person then it will have info structure like {xyz : a, b, c,e} it means xyz knows a. b, c, e persons.
1. Draw a directed graph where a -> b means a knows b. Along with two extra variables no. incoming edges and no. out going edges.
2. While drawing the graph increase these variables when you add one relation in graph.
3. Now just iterate over the graph and find the point where incoming variable count is n-1 and outgoing count is 0.
Compexity :
1. For drawing the graph O(n)
2. For finding the max no. incoming edges and outgoing edges O(n)
3. total = O(n)+O(n) = 2O(n) = O(n). as 2 is const. we can exclude it
I think this is an overly complicated solution to a simple problem.
A lot of the details you've mentioned overlooks the coding complexity involved. Heres how:
1) Lets say Im making my graph, before I even start constructing the graph I(as a coder) need to all information about who knows whom. This information can get stored in a confusion matrix. So if I need to code this, I would have an extra memory requirement to store this information.
2) When you talk about iterating through the graph, you need to ensure that given a particular node, you should be able to reach every other node. What happens if no individual knows anybody else in the room other than the celebrity. How do you iterate through your graph then?
3) Considering directed graphs, you need to consider the possibility of having loops in them. If they do, you could easily end up in a typical infinite recursion scenario. Sure, you could maintain a visited flag variable for each node, but that again adds to your memory. Not asymptotically, but practically for small n.
4) If I give you this problem to solve in place, your graph method wont work.
5) My solution when implement in code, requires just one fuction bool knows(a,b) which simply returns true if a knows b and false otherwise. Your solution requires way more.
Your solution is valid, but you need to take the above points into consideration. As I said, this problem looks for an efficient algorithm, not your data structure manipulation skills.
Thanks.
We represent the people in the room as: a, b, c, d, ..., n
Stand these people in a line.
Ask the first person who all they know.
If the first person knows no one, then they are the celebrity.
If they know 5 people, then the celebrity is one of those 5 people.
Suppose a knows (b, c, d, e, f). Now, out of these 5 people, we only need to find the person who doesn't know anyone. The worst case complexity of this algorithm is O(n) which is when the first person we ask knows everyone. Then we have to loop through the n people to find out who doesn't know anyone. But if the first person knows only m people (such that m<= n), then our algorithm will run in O(m).
In our example, we will only need to find out who knows no one out of the 5 people that a knows.
Someone correct me if my logic is incorrect please.
Doesn't the process of finding if someone knows anyone or not take O(n)? If it does, then does your algorithm not fail to be a linear time running algo?
The O(n) solution where we keep them in a row and compare the current possible candidate with next person in row to eliminate either one of them or both of them as a candidate (posted by sreemana@buffalo.edu) works but with one catch.
After we do the first pass, if we are left with one possible candidate, we need to do another pass to confirm that he is indeed the celebrity. (that everyone else, to be precise, everyone else before him in the row know this person and he doesn't know any of those persons). We can return that candidate only after that check otherwise there is no celebrity.
Let me explain with an example: Let's say we have persons a,b,c,d and here are the relationships: a knows b, c knows b, b knows d, d knows a (other than these all other possible pairs are "does not know" case), in this scenario, at the end of the loop, we will have 'd' as celebrity but he is really not.
Suppose that we use a directed graph (not DAG cause we can have cycles). And graph represented as an adjacency list. Go though all vertexes and find first one which doesn't contains any edges. Time: O(V) Space: O(V+E)
1->3->2->6
2->6->5
3->5->6
4->6->3
5->6
6-> EMPTY
So "6" is celebrity.
The problem can posed as UniversalSink problem as explained in CLR's Algorithms book (Cormen). Isnt it?
If everyone knows the celebrity, why not just ask one of them who the celebrity is?? No algorithm involved in this. Since everyone knows the celebrity, they will mention who he is. If the first person you approach does not know who the celebrity is, then he is the celebrity.
this is fairly a simple problem can be solved on O(n) complexity
condider a set of people as a1,a2,a3... an and say an+1 is a celebrity..
randomly pick any one person say ak and check how many people it know..
if number of people known is 0 then ak is the celebrity else someone from the people known by ak is the celebrity..
now check this on all the people known by ak
Take any person and get all the peoples he knows.
Consider there 1..n people and person 1 knows k people (k <= n)
then we just have to iterate the k people and return the person who doesnt know anybody.
This will solve the problem in O(k + 1)
The worst case will be O(n) if person knows all the people.
// DFS ?
class Person{
private String adharId;
private Set<Person> circle;
public Person(String adharId) {
this.adharId = adharId;
this.circle = new HashSet<Person>();
// TreeSet<Person>(); //if you want to build relationship depth
}
public void addToCircle(Person person){
circle.add(person);
}
public String getDetails(){
return this.adharId;
}
public int getNoOfFriends(){
return this.circle.size();
}
}
public Person getCeleb(Map<Person, Integer> room){
//iterate thorough the values and return the poor man having 0 friends
return null;
}
Map<Person, Integer> room = new HashMap<Person, Integer>();
// DFS ?
class Person{
private String adharId;
private Set<Person> circle;
public Person(String adharId) {
this.adharId = adharId;
this.circle = new HashSet<Person>();
// TreeSet<Person>(); //if you want to build relationship depth
}
public void addToCircle(Person person){
circle.add(person);
}
public String getDetails(){
return this.adharId;
}
public int getNoOfFriends(){
return this.circle.size();
}
}
public Person getCeleb(Map<Person, Integer> room){
//iterate thorough the values and return the poor man having 0 friends
return null;
}
Map<Person, Integer> room = new HashMap<Person, Integer>();
How about we use people as nodes ( celebrity too ) and perform DFS on this graph. The node with the EARLIEST finish time will be the sink node .. (note that a sink node has no outgoing edges and hence the earliest finish time), The sink node will be the celebrity. This can be performed in O(n) time.
Shouldn't the worst case complexity be approxO(n2). When total number of comparisons is: (n2-n)/2. Consider the case when the celebrity is at the end of the row. And except everyone (other than celebrity) don't knows each other except celebrity. In a,b,c,d,e. If e is celebrity and if we start from a:
Comparisons will be:
a-b
a-c;b-c
a-d,b-d,b-c
a-e,b-e,c-e,d-e
find the node in the directed graph with the most inward coming edges and no outgoing edges
sure, because drawing graphs and finding the node with the maximum number of incoming nodes is what people do when a celebrity is in a room right!!!!
Ok heres the solution. SantiagoYMG is pretty close.
- sreemana@buffalo.edu March 27, 2012The solution is O(n) in time complexity.
Make all of them stand in a row.
Lets say the people are a,b,c,d,e,f,g,h,i,j,.......n
Compare a and b.
if a knows b => a is certainly not the celebrity. Probable celebrity = b
if a doesnt know b => b is certainly not the celebrity. Probable celebrity = a
In either case compare the probable celebrity to the next person in line ie 'c' and repeat the process. Each comparison should eliminate 1 person and have another as the probable celebrity. At the end, the probable celebrity who survives is the certain celebrity.
Complexity = O(n)