Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Microsoft SWE interview, one coding round focused on a classic graph/logic problem. Nothing too wild but the follow-up verification step is where people usually slip up.

Questions Asked (1)

Given n people at a party labeled 0 to n-1, find the 'celebrity' who is known by everyone but knows nobody. You can call knows(a, b) to check if a knows b. Solve it in O(n) calls, or return -1 if no celebrity exists.

Algorithms & Data Structures

Author's notes

The linear pass to narrow down a candidate clicked pretty fast for me.

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 iterating through all people and eliminating anyone who is known by the current candidate. Then, verify the candidate by checking that they know no one and everyone else knows them. This uses at most 2n-2 calls, achieving O(n).

Pro tip: Mention that the elimination pass is essentially a tournament where each comparison eliminates one person, and the verification pass is necessary to handle false positives. This shows you understand the invariant and edge cases.

1. Initialize candidate

Start with person 0 as the initial candidate.

2. Elimination pass

For each person i from 1 to n-1, if knows(candidate, i) is true, then candidate knows i, so candidate cannot be the celebrity; set candidate = i. Otherwise, i knows candidate, so i cannot be the celebrity; keep candidate unchanged.

3. Verification pass

After the loop, verify that the candidate is indeed a celebrity: check that for every other person j, knows(candidate, j) is false and knows(j, candidate) is true. If any check fails, return -1.

4. Return result

If verification passes, return the candidate; otherwise, return -1.

Key Points to Mention

The elimination pass reduces the candidate set by one with each knows call, ensuring O(n) calls.
The verification pass is crucial because the elimination pass only guarantees that the candidate is not known by anyone who was eliminated, but it doesn't guarantee the celebrity property.
Edge cases: n=0 or n=1. For n=1, the single person is trivially a celebrity (if we assume they know nobody and are known by everyone, vacuously true).
The algorithm uses at most 2n-2 calls to knows, which is O(n).
The problem is equivalent to finding a sink in a directed graph where edges represent 'knows' relationships.
If no celebrity exists, the verification will fail and we return -1.

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