cswork / libraryOpen practice workspace

Coding questions · HubSpot

Find a special person using knows(a,b)

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.

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.

Find the Special Person

Examples

Example 1

Input: ([[False, True, True], [False, False, True], [False, False, False]],)
Output: 2

Explanation: Person 2.

Example 2

Input: ([[False, True], [True, False]],)
Output: -1

Explanation: No special person.

Hints

  1. Eliminate candidates in one pass, then verify the survivor.