## Linkedin Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
4
of 8 vote

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"

``````int 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;
}``````

Comment hidden because of low score. Click to expand.
9

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;
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

And remove the ones with Row sum is > 0

Comment hidden because of low score. Click to expand.
0

@Inquisitive Really nice solution!

Comment hidden because of low score. Click to expand.
0

Isn't that is still o(n2)?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

This would fail at the first if... if no one is following 0, then your code keeps the influencer at 0 after the first for loop. Did you mean the following instead?

``````if(followingMatrix[influencer][i]) {
influencer = i;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ... ?

Comment hidden because of low score. Click to expand.
0

There is no influencer here.
return -1.

Comment hidden because of low score. Click to expand.
0

there is no influencer here.
return -1 in this case

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++)

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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

Sorry for the minor mistake in the code. Please replace

``if(isZeroFollower) {``

by

``if(isInfluencer) {``

Time complexity: O(N) (Assuming a square matrix with side sqrt(N))
Space complexity: O(1)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check out the github code for
in github.com
/sabithksme/skillTest/blob/719a26e2f8bbe98494dea3d10ce68f8c20324347/src/main/java/com/sks/skill/influencer/Influencer.java

Comment hidden because of low score. Click to expand.
0

sabithksme/skillTest/blob/master/src/main/java/com/sks/skill/influencer/Influencer.java

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
}
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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) {
flag = true;
} else {
flag = false;
break;
}

if(flag == true) return j;
}

}

return -1;

}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

"""
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]

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

the simple strategy :-

verify each row, if all the cells is true in that row where i != j then we found an influencer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry each column

the simple strategy :-

verify each column, if all the cells is true in that column where i != j then we found an influencer i.e (i+1) th person.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.