Skip to main content

277. Find the Celebrity

mediumAsked at DoorDash

Given n people and a knows(a, b) API, find the celebrity — someone known by everyone but who knows nobody. DoorDash uses this to test whether you spot the O(n) elimination trick instead of the O(n^2) brute-force matrix check.

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

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Find the Celebrity as a recurring O(n) elimination problem.
  • Blind (2025-12)— DoorDash new-grad reports list this as a backend logic-and-API question.

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. The only thing you are allowed to do is ask questions like: 'Hi, A. Do you know B?' to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible. You are given a helper function bool knows(a, b) that 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, or -1 otherwise.

Constraints

  • n == graph.length
  • n == 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 knows nobody and is known by everyone else (besides themselves).

Example 2

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

Approaches

1. Two-pass elimination (optimal)

Pass 1: walk i = 0..n-1; if knows(candidate, i), candidate = i. Pass 2: verify candidate is known by everyone and knows nobody.

Time
O(n)
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: DoorDash's expected answer. The insight: if candidate knows i, candidate isn't the celebrity (celebrity knows nobody), so try i. The final i must be the only possible celebrity.

2. Brute-force matrix check

For each person, check if everyone else knows them and they know no one. Return the first match.

Time
O(n^2)
Space
O(1)
function findCelebrityBrute(n) {
  for (let i = 0; i < n; i++) {
    let ok = true;
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      if (knows(i, j) || !knows(j, i)) { ok = false; break; }
    }
    if (ok) return i;
  }
  return -1;
}

Tradeoff: Easy to derive but O(n^2). DoorDash interviewers want you to NAME this first, then derive the O(n) elimination.

DoorDash-specific tips

DoorDash interviewers grade specifically on the ELIMINATION INSIGHT. State: 'if A knows B, A can't be the celebrity (celebrity knows nobody) — so B is the candidate.' That sentence proves you spotted the O(n) trick.

Common mistakes

  • Forgetting the verification pass (the candidate could fail).
  • Skipping i === candidate in the verification — knows(candidate, candidate) is true per the problem but doesn't disqualify.
  • Calling knows() inside both directions in the verification when only the relevant direction is needed.

Follow-up questions

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

  • How would you minimize calls further (some solutions use < 3n calls).
  • What if multiple celebrities are possible?
  • What if you can only call knows() asynchronously?

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 does the first pass identify the only possible candidate?

If candidate i knows j, i can't be celebrity. If i doesn't know j, j can't be celebrity. So after the pass, only candidate could be celebrity; verify in pass 2.

Why is verification required?

The elimination only proves no one ELSE could be celebrity. The candidate itself still needs verification — someone might not know them, or they might know someone.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →