Find a special person using knows(a,b)
Company: HubSpot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Problem
You are given `n` people labeled `0` to `n-1` at a party. You can call an API:
- `knows(a, b) -> bool`: returns `true` if person `a` knows person `b`, otherwise `false`.
A **special person** is defined as someone who:
1. Is **known by everyone else** (for all `i != x`, `knows(i, x) == true`), and
2. **Knows nobody else** (for all `i != x`, `knows(x, i) == false`).
Return the label of the special person if one exists, otherwise return `-1`.
## Constraints
- `1 <= n <= 10^4`
- You should minimize the number of API calls; aim for **O(n)** calls.
## Notes
- `knows(a, a)` is undefined and should not be relied upon.
Quick Answer: This question evaluates algorithmic reasoning about pairwise relation inference using an oracle-style knows(a, b) API and the ability to minimize API calls, testing skills in graph modeling and asymptotic analysis.
Given a knows matrix, return the person known by everyone else who knows nobody else, or -1.
Examples
Input: ([[False, True, True], [False, False, True], [False, False, False]],)
Expected Output: 2
Explanation: Person 2.
Input: ([[False, True], [True, False]],)
Expected Output: -1
Explanation: No special person.
Input: ([[False]],)
Expected Output: 0
Explanation: Single person.
Hints
- Eliminate candidates in one pass, then verify the survivor.