The Celebrity Problem
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## The Celebrity Problem
At a party there are `n` people, labeled `0` to `n - 1`. Among them there may be exactly one **celebrity** — a person who satisfies **both** of these conditions:
- Every other person at the party knows the celebrity, and
- The celebrity does not know any other person at the party.
You cannot observe the acquaintance graph directly. You may only query it through a single boolean API:
```
knows(a, b) -> true if person a knows person b, false otherwise
```
A person is never asked whether they know themselves (`knows(a, a)` is not meaningful and should not be called).
Implement a function `findCelebrity(n)` that returns the label of the celebrity if one exists, or `-1` if there is no celebrity. Your goal is to use **as few calls to `knows` as possible** — a strong solution makes $O(n)$ calls rather than the brute-force $O(n^2)$.
### Input / Output
- You are given the integer `n` (the number of people) and access to the `knows(a, b)` API.
- For testing, the acquaintance relation is provided as an `n x n` matrix `M`, where `M[i][j] == 1` means person `i` knows person `j`, and `0` means they do not. A call to `knows(i, j)` returns `M[i][j] == 1`. (Your solution must use the API, not read the matrix directly.)
- Return a single integer: the celebrity's label, or `-1`.
### Examples
**Example 1**
```
n = 3
M = [
[0, 1, 0], # person 0 knows person 1
[0, 0, 0], # person 1 knows no one
[0, 1, 0] # person 2 knows person 1
]
Output: 1
```
Person `1` is known by everyone else (`knows(0,1)` and `knows(2,1)` are both true) and knows no one, so `1` is the celebrity.
**Example 2**
```
n = 2
M = [
[0, 1],
[1, 0]
]
Output: -1
```
Person `0` knows person `1` and person `1` knows person `0`, so neither can be a celebrity.
### Constraints
- $2 \le n \le 5000$
- `M[i][i] == 0` for all `i`.
- At most one celebrity exists.
Quick Answer: This question evaluates a candidate's ability to design a graph-search algorithm under a restricted query interface, using pairwise "knows" relationships to identify a unique sink node while minimizing calls. It tests optimization instincts, since a naive check is quadratic while an elimination-based approach reduces this to linear time. Such problems are common in coding interviews to assess algorithmic efficiency and edge-case reasoning about existence conditions.
At a party there are `n` people, labeled `0` to `n - 1`. There may be exactly one **celebrity** — someone whom **every** other person knows, and who **knows no one** else.
You cannot read the acquaintance graph directly; you may only query the boolean API `knows(a, b)` (true if person `a` knows person `b`). You must never call `knows(a, a)`.
Return the celebrity's label, or `-1` if there is no celebrity, using as few `knows` calls as possible — aim for `O(n)` rather than the brute-force `O(n^2)`.
**Executable form:** For testing, the acquaintance relation is supplied as an `n x n` matrix `M`, where `M[i][j] == 1` means person `i` knows person `j`. Your function receives `M` and should treat `knows(a, b)` as `M[a][b] == 1` (defined internally) rather than inspecting `M` in your elimination logic.
Example 1: `M = [[0,1,0],[0,0,0],[0,1,0]]` -> `1` (everyone knows person 1, and person 1 knows no one).
Example 2: `M = [[0,1],[1,0]]` -> `-1` (each knows the other).
Constraints
- 2 <= n <= 5000
- M[i][i] == 0 for all i (no one is asked about themselves)
- At most one celebrity exists
- Solve using the knows(a, b) API only; do not scan M directly in your elimination logic
- Aim for O(n) calls to knows rather than O(n^2)
Examples
Input: ([[0,1,0],[0,0,0],[0,1,0]],)
Expected Output: 1
Explanation: Persons 0 and 2 both know person 1 (M[0][1]=M[2][1]=1), and person 1 knows no one (row 1 all zeros), so 1 is the celebrity.
Input: ([[0,1],[1,0]],)
Expected Output: -1
Explanation: Person 0 knows person 1 and vice versa, so neither knows-no-one condition holds; no celebrity.
Input: ([[0,1],[0,0]],)
Expected Output: 1
Explanation: Person 0 knows person 1 (M[0][1]=1) and person 1 knows no one, so 1 is the celebrity.
Input: ([[0,0,1],[1,0,1],[0,0,0]],)
Expected Output: 2
Explanation: Persons 0 and 1 both know person 2, and person 2 knows no one (row 2 all zeros), so 2 is the celebrity.
Input: ([[0,1,0,1],[0,0,1,1],[1,0,0,1],[0,0,0,0]],)
Expected Output: 3
Explanation: Everyone knows person 3 (M[0][3]=M[1][3]=M[2][3]=1) and person 3 knows no one, so 3 is the celebrity even though it sits last.
Input: ([[0,1,0],[0,0,1],[1,0,0]],)
Expected Output: -1
Explanation: A cycle 0->1->2->0: elimination leaves candidate 2, but knows(2,0)=1, so verification fails and there is no celebrity.
Input: ([[0,0],[0,0]],)
Expected Output: -1
Explanation: No one knows anyone, so no person is universally known; verification fails and the answer is -1.
Hints
- Brute force is O(n^2): check every ordered pair. To reach O(n), first eliminate n-1 people, then verify the one survivor.
- Elimination trick: keep a running candidate starting at 0. For each next person i, if the candidate knows i, the candidate is disqualified (a celebrity knows no one), so set candidate = i. After one pass, only one person can possibly be the celebrity.
- Verification is mandatory: the survivor is only a POSSIBLE celebrity. Confirm the candidate knows no one AND everyone else knows the candidate; if either check fails, return -1.