Linkedin Interview Question Software Engineer / Developers
Country: United States
1. There could be at most 1 influencer, this can easily proved by contradiction.
2. Thus can be solved in O(N)
int getInfluencer(vector<vector<bool> > M) {
int cand=0;
for(int i=1; i<M.size(); i++)
{
if(M[cand][i] == 1 || M[i][cand]==0)
{
cand = i;
}
}
// now verify cand is indeed an influencer
for(int j=0; j<M.size(); j++)
{
if(j==cand) continue;
if(M[cand][j]==1 || M[j][cand]==0) return -1;
}
return cand;
}
If i understand this question correctly, influncer can be find out easily using following strategy :
1. store "true" as value 1 and "false" as value 0;
2. find all the columns with total = N-1; each such column is one influencer .
step 2 can run in parallel for all columns and save result in shared space.
In Python:
# Example of m
m = [[0, 1, 1, 0],
[1, 0, 1, 1],
[0, 0, 0, 0],
[1, 1, 1, 0]]
def get_influencer(m):
# find a row i that has all 0s
# and a column that has all 1s, except in diagonal
x = [sum(m[i]) for i in range(len(m))] #sum of all elements in row i
y = [sum(j) for j in zip(*m)] #sum of all elements in col j
results = map(lambda pair: (1 if pair[0] == 0 and pair[1] == len(m) -1 else 0), zip(x, y))
influencers = [i for i in range(len(m)) if results[i]] #index of influencers
return influencers[0] if influencers else -1
public static int getInfluncer(boolean [][] followingMatrix){
// if i is follows by j, following[i][j] = ttrue;
int n = following.length;
int influencer = 0;
for(int i=1; i<n;i++){
if(followingMatrix[i][influencer]){
// influencer is following someone. So it cant be.
influencer = i;
}
}
// All other nodes except influencer follow at least 1 other person. Hence, we just need
// to check that the surviving influencer is not following anyone else.
// All nodes after influencer have already been checked.
for(int i=0; i<influencer;i++){
if(followingMatrix[i][influencer])
return -1;
}
return influencer;
}
I am not able to understand this question fully. Can someone please explain, what happens if i have the setup like below :
{
{0,1,0},
{1,0,0},
{0,0,0}
}
Why is influncer = 2 here, i understand {2,0} {2,1} are 0's. BUT shouldnt {0,2} and {1,2} be equal to 1, meaning 0,1 are following2, but 2 is not following anyone ... ?
For each user, look at index [i][i]. then check the row and column which intersect there. If the row has any 1s and the column has any 0s, you can stop searching that user immediately as you know they aren't the influencer.
Furthermore, any time you find a 1 while checking the column, you know that the user who corresponds to the row it's in is also not the influencer.
int getInfluencer(boolean[][] followingMatrix) {
Set<Integer> candidates = new HashSet<Integer>();
for (int i = 0; i < followingMatrix.length; i++)
candidates.add(i);
while (candidates.size() != 0) {
Integer cur;
for (Integer i : candidates) {
cur = i;
candidates.remove(cur);
break;
}
// Check row
boolean breakFlag = false;
for (int i = 0; i < followingMatrix.length; i++) {
if (breakFlag)
break;
if (i != cur) {
if (followingMatrix[cur][i]) {
breakFlag = true;
break;
}
}
}
if (breakFlag)
continue;
// Check column
for (int i = 0; i < followingMatrix.length; i++) {
if (breakFlag)
break;
if (i != cur) {
if (!followingMatrix[i][cur]) {
breakFlag = true;
break;
}
}
candidates.remove(i);
}
if (!breakFlag)
return cur;
}
return -1;
}
Imagine a matrix as follows:
a11 a12 a13 a14 ...... a1N
a21 a22 a23 a24 ...... a2N
..
..
aN1 aN2 aN3 aN4...aNN
So we have an NxN matrix of booleans. We are interested in that particular individual, for whom:
1. This individual does not follow anybody. That means, if the index of such an individual is j in
the above matrix, then ajk = false for all k = 1, 2, ...., N
2. This individual is followed by everybody. This means, the column akj = true for all k = 1, 2, ..., N (since followingMatrix[i][j] denotes "i follows k", for all k = 1, 2, ..., N, we get the sentence "all k follow j" which is what we want)
So basically, we are searching for a row, with all false values, and for a column with all but one true values (the value ajj will always be false, based on the definition in the problem statement).
This can be done using the following function:
public static int getInfluencer(boolean[][] followingMatrix) {
for(int i=0; i<followingMatrix.length; i++) {
boolean isInfluencer = true;
for(int j=0; j<followingMatrix[i].length; j++) {
if(followingMatrix[i][j]) {
isInfluencer = false;
break;
}
}
if(isZeroFollower) {
// check for all (j, i) for j = 0 to i-1
for(int j=0; j<i; j++) {
if(followingMatrix[j][i]) {
isInfluencer = false;
break;
}
}
// (i, i) will always be false, so skip
// check for all (j, i) for j = i+1 to N
for(int j=i+1; j<followingMatrix[i].length; j++) {
if(followingMatrix[j][i]) {
isInfluencer = false;
break;
}
}
}
if(isInfluencer) return i;
}
return -1;
}
Check out the github code for
in github.com
/sabithksme/skillTest/blob/719a26e2f8bbe98494dea3d10ce68f8c20324347/src/main/java/com/sks/skill/influencer/Influencer.java
This can be done in linear time and linear memory. Starting from the bottom left, with each move, you can eliminate one person as a candidate for an influencer.
public static int getInfluencer(int[][] followingMatrix) {
int n = followingMatrix.length;
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < n; i++) {
set.add(i);
}
int i = n - 1, j = 0;
while(i >= 0 && j < n && !set.isEmpty()) {
if (i == j) {
j++;
continue;
}
if (followingMatrix[i][j] == 1) {
if (set.contains(i)) {
set.remove(i);
}
i--;
} else {
if (set.contains(j)) {
set.remove(j);
}
j++;
}
}
if (set.isEmpty()) {
// no influencer
return -1;
}
Integer[] influencers = set.toArray(new Integer[1]);
int influencer = influencers[0];
System.out.println("Possible influencer: " + influencer);
for (int k = 0; k < n; k++) {
if (k == influencer) continue;
if (followingMatrix[k][influencer] == 0) return -1;
}
for (int k = 0; k < n; k++) {
if (k == influencer) continue;
if (followingMatrix[influencer][k] == 1) return -1;
}
return influencer;
}
O(n) solution
int getInfluencer(bool** followingMatrix, int num)
{
assert(num>1);
int ID1=0, ID2=1; //ID1 alway on the left of ID2, anyone after ID2 is not processed
while(ID2<num)
{
// (false, false) or (true, true): none of them should be influencer
if(followingMatrix[ID1][ID2] == followingMatrix[ID2][ID1])
{
ID1 = ID2+1;
ID2 = ID2+2;
}
else if(followingMatrix[ID1][ID2])
{
// ID1 cannot be influencer
ID1 = ID2;
ID2++;
}
else
{ // ID2 cannot be influencer
ID2++;
}
}
// No one can be influencer
if(ID1>=num) return -1;
for(int i=0; i<num; i++)
{
if(i==ID1) continue;
if(!followingMatrix[i][ID1] || followingMatrix[ID1][i])
return -1;
}
return ID1;
}
void testGetInfluencer()
{
int n = 10, ID=0;
bool** matrix;
matrix = new bool*[n];
for(int i=0; i<n; i++)
matrix[i] = new bool[n];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
matrix[i][j] = (rand()%2 == 1);
for(int i=0; i<n; i++)
{
matrix[ID][i] = false;
matrix[i][ID] = true;
}
//for(int i=0; i<n; i++)
// matrix[i][i] = false;
int res = getInfluencer(matrix, n);
for(int i=0; i<n; i++)
delete [] matrix[i];
delete [] matrix;
}
Give it a try here:
int getInfluencer(boolean followingMatrix, int num) {
int num=0;
for(int j=0;i<followingMatrix[i].length;i++){
for(int i=0;j<followingMatrix.length;j++{
if(followingMatrix[i][j]==true&&followingMatrix[j][i]==false) num++;
}
if(num==followingMatrix.length) return true;
break;
}
return false;
}
public InfluenceerFindeImple implements InfluncerFinder {
public int getInfluencer(boolean[][] followingMatrix) {
Set<Integer> notInfluencer = new HashSet<Integer>();
boolean flag = false;
for(int j=0; j<followMatrix.length(); j++) {
if(notInfluncer.contains(j)) continue;
for(i=0; i>followMatrix.length(); i++) {
if(i == j) continue;
if(followMatrix[i][j] == true) {
notInfluencer.add(i);
flag = true;
} else {
notInfluencer.add(j);
flag = false;
break;
}
if(flag == true) return j;
}
}
return -1;
}
}
Here is a C# solution. As per the above comments, there can be only one influencer and the algorithm is O(n). Imagine the matrix as a "cylinder"; then we must find a row where `false` values wrap all the way around. At the same time, as we test for false values, we eliminate other users from being an influencer candidate. Therefore, we should have to test each column for false at most twice: once to see if the current user can be the influencer, and once to see if it is false in the (possible) influencer's row. If we find a row of all false, afterward just check the column values for that user to be true.
using System;
namespace Influence
{
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(bool[][] followingMatrix);
}
public Finder : InfluencerFinder
{
public int getInfluencer(bool[][] followingMatrix)
{
int numUsers = followingMatrix[0].length;
int numNotFollowing = 0;
int j = 0;
int user;
bool colOverflow = false;
while(numNotFollowing < numUsers)
{
if(user == numUsers - 1 || colOverflow)
return -1;
user = j;
numNotFollowing = 0;
while(!followingMatrix[user][j] && numNotFollowing < numUsers)
{
j++;
numNotFollowing++
if(j >= numUsers)
{
j = j % numUsers;
colOverflow = true;
}
}
}
// if here, then row user has all false... check col
int numFollowedBy = 0;
for(int i = 0; i < numUsers; i++)
{
if(i == user)
continue;
if(!followingMatrix[i][user])
return -1;
}
return user;
}
}
}
"""
Problem Breakdown
if i != j and matrix[i][j] == 1
i can't be influencer, otherwise j can't be
so everyone comparison, there is one exclude
There can only be one influencer
Use queue (FIFO) to arrange comparisons like sports match
for example, for 8 teams, there are 4+2+1=7 to get winner
pop two people, compare, get winner back in queue, until there is 1 winner
"""
class Solution:
def getInfluencer(self, matrix):
# Initialize data structure
N = len(matrix)
queue = range(N)
# Use N-1 compare to find potential influencer
while len(queue) > 1:
x = queue.pop(0)
y = queue.pop(0)
if matrix[x][y] == 1:
queue.append(y)
else:
queue.append(x)
# Check if winner is real influencer
z = queue[0]
for i in xrange(N):
if i != z and matrix[z][i] == 1:
return []
for i in xrange(N):
if i != z and matrix[i][z] == 0:
return []
return queue[0]
def find_influencer(matrix):
for row in range(len(matrix)):
following_none = not any(matrix[row])
if not following_none:
continue
all_following = True
for r_no in range(len(matrix)):
if not row == r_no:
continue
if not matrix[r_no][row]:
all_following = False
break
if all_following:
return row
return -1
def find_influencer(matrix):
for row in range(len(matrix)):
following_none = not any(matrix[row])
if not following_none:
continue
all_following = True
for r_no in range(len(matrix)):
if not row == r_no:
continue
if not matrix[r_no][row]:
all_following = False
break
if all_following:
return row
return -1
O(N^2) solution.
Logic: a person "i" is not an influencer if "i" is following any "j" or any "j" is not following "i"
- mombasa February 19, 2014int getInfluencer(vector<vector<bool> > M) { for(int i=0; i<M.size(); i++) { bool is_influencer = true; for(int j=0; j<M.size(); j++) { if( i==j ) continue; if( M[i][j] || !M[j][i] ) { is_influencer = false; break; } } if( is_influencer ) return i; } return -1; }