public interface InfluencerFinder {
/ Given a matrix of following between N LinkedIn users (with ids from 0 to N-1): followingMatrix[i][j] == true iff user i is following user j thus followingMatrix[i][j] doesn't imply followingMatrix[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 This method should find an Influencer by a given matrix of following, or return -1 if there is no Influencer in this group. / int getInfluencer(boolean[][] followingMatrix)
Analysis
The most naive method is using two loops to check if the user is an influencer. Time complexity of this method is O(n^2)
However, it is easy to prove that there is only one influencer. So we can start from the first user, all the user followed by him is impossible to be an influencer. In the mean time, if any one follows him, he is impossible to be an influencer. So think like we are traverse on the matrix. Time complexity of this method is O(n)
Another interesting way to think of this question is that, since all column are independent to each other. We can parallelly sum the column up. All the columns that sum up to N - 1 can be one possible influncer. Why we should check by column instead of row? Because few users will be followed by everyone else. However, lots of people may not follow anyone. Then we only need to check if they actually do not follow anyone. There are a coulple of ways to parallel it.
- Divide the columes and spawn threads to compute them.
- Use some thing list ISPC tasks to parallel them, we can make use of SIMD as well.
- Use MapReduce to parallel.
Read full article from Find Influencer
No comments:
Post a Comment