Quick Overview

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.

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.

Hints

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

Loading coding console...