Find the Influencer or Celebrity - Algorithms and Problem SolvingAlgorithms and Problem Solving
Find the Influencer or Celebrity
A celebrity/influencer is a person who doesn't anybody but is known to or followed by everybody. Given N peoples and a matrix for known or following information then find the celebrity or influencer among the group of N peoples.
Formally speaking, Given a matrix of following between N users (with ids from 0 to N-1):
* following[i][j] == true iff user i is following user j
* thus following[i][j] doesn't imply following[j][i].
* Let's also agree that followingMatrix[i][i] == false
*
* Influencer is a user who is:
* – followed by everyone else and
* – not following anyone himself
*
* Find an Influencer by a given matrix of following,
* or return -1 if there is no Influencer in this group.
For example, Lets suppose we have N=5 peoples {A,B,C,D,E} and the following matrix is as follows –
following[0][3] = 1;
following[0][1] = 1;
following[1][3] = 1;
following[1][0] = 1;
following[1][4] = 1;
following[4][3] = 1;
following[2][3] = 1;
following[2][4] = 1;
then clearly 3 is celebrity.
We can build a directed graph and then find the single vertex that has out degree 0 but in degree = N-1.
Computing in-degree and out-degree of a directed graph will take O(n^2) time. Can we do better? Note that, we can easily proof that there should be only one celebrity c with the two following properties –
1. Everybody knows c 2. c doesn't know anybody
So, we can compute the celebrity in O(n) time by testing each person for the above properties. We can select a person c as a candidate celebrity and then test if c is indeed a celebrity by testing with next person. If the next person doesn't know (or follow) the current candidate (or influencer) or the candidate knows the next person then the next person may be the celebrity. We can choose such a candidate and then test if all other person knows the candidate c and the candidate c doesn't know anybody. If any of these properties fail we say there is no such celebrity (or influencer). The overall complexity is O(n). Below is a simple implementation of the above algorithm –
Read full article from Find the Influencer or Celebrity - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment