Skip to main content

277. Find the Celebrity

mediumAsked at Microsoft

Find the Celebrity is Microsoft's elegant elimination puzzle. With n people and a knows(a,b) oracle, brute force is O(n^2). The two-pointer elimination trick gets it to O(n) calls — and the verification pass is what makes the candidate proof bulletproof.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Bing/Azure org onsite reports list this as a recurring elimination-style medium.
  • Blind (2025-12)— Microsoft new-grad and L60 reports include Find the Celebrity with the O(n) call follow-up.

Problem

Suppose you are at a party with n people labeled from 0 to n - 1 and among them there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. You are given a helper function bool knows(a, b) which tells you whether a knows b. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party. Return the celebrity's label if there is a celebrity at the party. If there is no celebrity, return -1.

Constraints

  • n == graph.length == graph[i].length
  • 2 <= n <= 100
  • graph[i][j] is 0 or 1.
  • graph[i][i] == 1

Examples

Example 1

Input
graph = [[1,1,0],[0,1,0],[1,1,1]]
Output
1

Explanation: Person 1 is the celebrity: everyone knows 1, and 1 knows no one.

Example 2

Input
graph = [[1,0,1],[1,1,0],[0,1,1]]
Output
-1

Explanation: There is no celebrity.

Approaches

1. Brute-force (verify every candidate)

For each person p, check that everyone else knows p and p knows nobody else. Return p if both hold.

Time
O(n^2) calls to knows()
Space
O(1)
function findCelebrity(n) {
  for (let p = 0; p < n; p++) {
    let isCeleb = true;
    for (let i = 0; i < n; i++) {
      if (i === p) continue;
      if (knows(p, i) || !knows(i, p)) { isCeleb = false; break; }
    }
    if (isCeleb) return p;
  }
  return -1;
}

Tradeoff: Quadratic. The right starting point for the conversation — name it, then ask 'can we eliminate without checking everything?' to set up the optimal.

2. Two-pointer elimination + verify (optimal)

Walk a single candidate from 0 to n-1. If knows(candidate, i), candidate can't be the celebrity (celebrities know nobody) — replace candidate with i. After one pass, verify the candidate against everyone else.

Time
O(n) calls to knows()
Space
O(1)
function findCelebrity(n) {
  let candidate = 0;
  for (let i = 1; i < n; i++) {
    if (knows(candidate, i)) candidate = i;
  }
  for (let i = 0; i < n; i++) {
    if (i === candidate) continue;
    if (knows(candidate, i) || !knows(i, candidate)) return -1;
  }
  return candidate;
}

Tradeoff: Three passes max (two walks plus a verify), each O(n). The elimination invariant is the key: after the first pass, anyone the candidate KNEW has been eliminated; anyone the candidate didn't know cannot be the celebrity if they preceded the candidate. So only the surviving candidate needs verification.

Microsoft-specific tips

Microsoft grades this on whether you can verbalize the elimination invariant. Say: 'if A knows B, then A is not the celebrity (celebrities know nobody). If A does not know B, then B is not the celebrity (everyone knows the celebrity). Either way, one call eliminates one person — so n-1 calls leave exactly one candidate, who I then verify in another n-1 calls.' That sentence is the entire interview.

Common mistakes

  • Forgetting the verification pass — the first pass only narrows to one candidate, it doesn't prove the candidate is actually the celebrity.
  • Verifying the candidate against itself — the loop must skip i === candidate.
  • Caching knows() results in a 2D array without realizing the call count is the metric, not the runtime.

Follow-up questions

An interviewer at Microsoft may pivot to one of these next:

  • What if there could be MORE than one celebrity (or zero)? Run the same algorithm; if verify fails return -1.
  • What if knows() were expensive (network call)? Memoize results — but check the problem's call-cost model.
  • Related: Topological elimination in tournament graphs.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the verify pass needed?

The elimination pass guarantees that IF a celebrity exists, it must be the final candidate. It does NOT guarantee a celebrity exists. The verify pass closes that gap.

Can we do better than 3(n-1) calls?

The lower bound is 3(n-1) calls without caching — proven via adversary argument. With caching the second/third pass can hit memoized results.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Find the Celebrity and other Microsoft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →