← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Microsoft SWE interview with a classic matrix problem that looks deceptively easy until you're staring at an O(N^2) brute force and the interviewer is waiting for something better.

Questions Asked (1)

Q1

Given an N×N boolean matrix where entry [i][j] is true if user i follows user j, find the 'Influencer': a user who follows nobody and is followed by everyone else. Return their index, or -1 if none exists. Solve it in O(N) time.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was to just scan every row and column which is obviously N squared and they were not impressed.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pass elimination strategy: first, find a candidate by scanning the matrix and eliminating non-influencers based on follow relationships; then verify the candidate in a second pass. This achieves O(N) time by leveraging the fact that an influencer must follow nobody and be followed by everyone.

Pro tip: Clarify that the matrix is given as a 2D array, so accessing any entry is O(1); the O(N) time refers to the number of matrix accesses, not the input size. Also, mention that the algorithm uses O(1) extra space.

1. Understand the problem and constraints

Restate the definition of an influencer: follows nobody (row all false) and is followed by everyone else (column all true except self). Note that there can be at most one influencer.

2. Find a candidate in one pass

Initialize candidate = 0. For each i from 1 to N-1, if matrix[candidate][i] is true (candidate follows i), then candidate cannot be the influencer, so set candidate = i. This eliminates one user per check.

3. Verify the candidate in a second pass

Check that the candidate follows nobody: for all j, matrix[candidate][j] is false. Check that everyone else follows the candidate: for all i != candidate, matrix[i][candidate] is true. If both hold, return candidate; else return -1.

4. Analyze time and space complexity

Explain that the algorithm performs at most 2N-2 matrix accesses, so O(N) time, and uses only a few variables, so O(1) space.

5. Discuss edge cases and trade-offs

Consider N=1 (the single user follows nobody and is followed by everyone? By definition, they follow nobody and are followed by everyone else—vacuously true, so return 0). Also, note that if the matrix is not given but can be queried, the same approach works with O(N) queries.

Key Points to Mention

  • At most one influencer can exist because if there were two, each would need to follow the other, contradicting 'follows nobody'.
  • The elimination step works because if candidate follows i, candidate is disqualified, and i remains a potential influencer.
  • Verification is necessary because the elimination only guarantees that the candidate is not disqualified by the follow relationships checked, but it might still fail the full conditions.
  • Time complexity is O(N) because we do at most N-1 checks in the first pass and 2(N-1) checks in the second pass.
  • Space complexity is O(1) as we only use a few variables.
  • The algorithm assumes the matrix is available for O(1) access; if not, the number of queries is still O(N).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.