The Celebrity Problem

The Celebrity Problem is a classic interview question often associated with LinkedIn, Google, and other tech companies, involving array representations, two-pointer techniques, and graph modeling (where people are nodes and "knows" relations are directed edges).[1][3][5]

Problem Statement

In a party of n people (labeled 0 to n-1), a celebrity is defined as someone who knows no one (out-degree 0) but is known by everyone else (in-degree n-1). You are given a function knows(a, b) (or an n x n adjacency matrix M where M[i][j] = 1 if person i knows j, else 0) that returns true if a knows b. Find and return the celebrity's index (0-based); return -1 if none exists. The function knows(a, a) returns 1 (self-knowledge), but this doesn't affect celebrity status since celebrities know no others.[3][4][5][1]

Example Inputs/Outputs

Example 1
Input: n = 4, M = [,,, ][1]

• Person 1 (index 1) knows only themselves; everyone knows them.
  Output: 1[5][1]

Example 2
Input: n = 2, M = [, ][1]

• No one fits: Person 0 knows no one but person 1 doesn't know them; person 1 knows themselves.
  Output: -1[4]

Example 3
Input: n = 3 (via knows function calls implying relations where 1 is known by 0 and 2 but knows none).
Output: 1[5]

Constraints

• 1 ≤ n ≤ 100 (or up to 10^4 in some variants).[3][1]
• knows(a, b) is called at most 3*n times in optimal solutions (to ensure O(n) efficiency).[5]
• Matrix is binary (0/1); input via matrix or oracle function.[3][1]