Find the Celebrity from a Knows Matrix
Company: Omnissa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Find the Celebrity from a Knows Matrix
At a gathering of `n` people, a celebrity is a person who is known by every other person but who knows no other person.
You are given an `n x n` Boolean matrix `knows`, where `knows[a][b]` is `true` when person `a` knows person `b`. Values on the diagonal do not affect the definition.
Implement:
```text
findCelebrity(knows) -> integer
```
Return the celebrity's zero-based index, or `-1` if no celebrity exists. There can be at most one celebrity.
## Constraints
- `1 <= n <= 5,000`
- `knows.length == n` and every row has length `n`.
## Examples
### Example 1
```text
knows = [
[false, true, true],
[false, false, false],
[false, true, false]
]
output = 1
```
Everyone other than person 1 knows person 1, and person 1 knows nobody else.
### Example 2
```text
knows = [
[false, true],
[true, false]
]
output = -1
```
Neither person satisfies both conditions.
Overview: Find a celebrity from a Boolean knows matrix, returning the unique qualifying index or minus one. The prompt defines both celebrity conditions, diagonal behavior, zero-based indexing, and a large input bound that rewards linear candidate elimination and verification.
Read the full Omnissa Software Engineer interview experience this question came from
At a gathering of n people, a celebrity is known by every other person and knows no other person. knows[a][b] is true when person a knows person b; diagonal values do not affect the definition. Return the celebrity zero-based index, or -1 if none exists. There can be at most one celebrity.
Constraints
- 1 <= n <= 5,000
- knows has n rows and every row has n Boolean values.
- Diagonal values do not affect the celebrity definition.
- There is at most one celebrity.
Examples
Input: ([[False, True, True], [False, False, False], [False, True, False]],)
Expected Output: 1
Explanation: Everyone else knows person 1, who knows nobody else.
Input: ([[False, True], [True, False]],)
Expected Output: -1
Explanation: Both people know another person, so neither is a celebrity.
Hints
- Compare two people to eliminate at least one from consideration.
- Verify the final survivor in both matrix directions while skipping the diagonal.