Interview Question
Country: India
"Leader is a person , who is being liked by all"
This suggests there is such a condition, unless the intended wording is:
"anyone who likes at least one person, must include the leader in his/her like-list"
If you assume there's a leader, then it has to be the one and only person who doesn't like anyone. If you don't assume that there's necessarily a leader, then you can conclude that there is no leader unless there is exactly one person who doesn't like anyone. If there is such a person, you still have to do a check to see if everyone likes him.
@Anonymous on December 28, 2011:- no doubt your solution is a good one. but if there are more than one people who don't like anyone then your algorithm will call all of them as leader. but this is not true. This problem can be solved by using simple if condition which checks:
if(there are more than one leader){ return false;}
but the same question can be asked by some good companies and they can add some more conditions where you may not just tell the answer by looking at the likeness table itself. so here the answer can be possible by following the below 2 approaches:
let there are m people.
1. take the integer array of size m and initialize to 0. for every person 'i' if he likes 'j', 'k', 'l' then increment the count of the array position 'j-1', 'k-1', 'l-1'. Check the likeness of the person 'a+1' where the value of array[a] == m-1. if the likeness of the 'a+1' person is 0, then he is the leader. this runs in O(n) time and O(n) space.
2. the same can be done by using a 2D integer array. if person 'a' likes person 'j', 'k', 'l' then set [a-1][j-1], [a-1][k-1]. [a-1][l-1] to 1. after that check each column. if ith column has (m-1) 1's and ith row has 0 1's then ith person is the leader. this runs in O(n) time and O(n^2) space.
3. graph and tree may work but the traversal is more than O(n) which makes it inefficient.
all constructive comments are always welcome. please notify if you find any problem with the answer. thank you all.
Take two pairs, test if they like each other, there are several cases:
1) they both like each other, then both of them can't be the leader
2) they both do not like each other, then both of them can't be the leader.
3) A likes B, but B do not like A, then A can't be the leader and B is the candidate for the leader,
Keep going, the survived leader candidate is the leader.
(1)I am not getting the concept of taking negative numbers.
(2)You can take an of size N.And initalize that array to zero.Now,if any person is liking someone then you can increase his count.And you should also take care of the case that person should not like himself.And in the end find out the index having count N-1.If their are having more than one person having N-1 count then reject the solution.
(3)If it sounds good to you then plz acknowledge me then I will try to write a code for this.
Hi,
My explanation is also almost similar.
In ur explanation , in step 2
: u mentioned like " And you should also take care of the case that person should not like himself".
so if if we find any other person who is being liked by this guy , then we need to substract -1 from count ( suppose , we have a group A,B,C,D. when A is being liked by b,d. we will increment value at value twice. if A likes any on in that group , we will decrement , value at A.
Finally if we find a person whose count is N-1 , we can say him as leader.
Graph Problem
A directed graph can be constructed, where the wdge goes from person A to person B, if A likes B.
Then do topological sort with the adjacency matrix. The Number at the last in the sorted list is the Leader.
Will this work. I think it assumes that there exist 1 person who is liked by all, and does not like anyone
Hi,
- Anonymous December 28, 2011Acc. to me the first person who does not like anyone is the leader, becauase all the others like atleast the leader. Only the leader has the authority not to like anyone.
Therefore, we can avoid the counters, and find the answer in O(n) time.
Correct me if am wrong.