Sunday, December 28, 2014

Influence Finder

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)

Click here for the original problem. 
Probably the most interesting problem I have met today.

If I understand correctly, if there exists an influencer in a matrix, it should be like this: 


The desired method should return 1 as the influencer. Moreover, since the influencer is followed by everyone yet is not following anyone (arrogant guy), there exists only one influencer in a given matrix. 

So, here comes my code. Technically, it's O(n^2). I first check if a person is following herself, which immediately excludes her from the candidate list. Then I check rows and columns simultaneously, if the candidate is so into another person and follows him or her, she is out, or if this guy is not popular enough that everyone wants to follow him, he is out. So, after trimmed lots of unnecessary loops, the solution should be better than O(n^2). 

However, I am still looking for better solution... 


public class InfluenceFinder {
 public int getInfluencer (boolean[][] followingMatrix) {
  if (followingMatrix == null) 
   throw new NullPointerException ("Null matrix? Are you kidding me?"); //This is a joke...
  if (followingMatrix.length == 0) 
   return -1;
  boolean isInfluencer = true;
  for (int cand = 0; cand < followingMatrix.length; cand++) {
   if (followingMatrix[cand][cand] == true) {
    continue;
   }
   for (int i = 0; i < followingMatrix.length; i++) {
    if (i == cand)
     continue;
    if (followingMatrix[i][cand] == false || followingMatrix[cand][i] == true) {
     isInfluencer = false;
     break;
    }
   }
   if (isInfluencer)
    return cand;
   isInfluencer = true; 
  }
  return -1;   
 }

}

1 comment:

  1. hey ,
    you can the fine O(n) solution in the comments section so career cup site.
    http://www.careercup.com/question?id=6482755168763904

    ReplyDelete