DSA interview question

The Celebrity Problem

Hard · Data structures · Topics: stack, graph

The problem

At a party of n people, a celebrity is someone everyone else knows but who knows no one else. You're given an n × n matrix where M[i][j] = 1 means person i knows person j, and each lookup is an expensive question ("does i know j?"). Find the celebrity's index, or −1. Checking every candidate fully is O(n²) questions. One question always eliminates somebody: if i knows j, i isn't the celebrity; if not, j isn't. A two-pointer sweep leaves one candidate after n − 1 questions, and a final O(n) check confirms or rejects it.

Example: [[0,1,0],[0,0,0],[0,1,0]] → 1.

Function signature

int findCelebrity(const vector<vector<int>>& M);  // -1 if there is no celebrity

Test cases

Input `M`	Output	Explanation
`[[0,1,0],[0,0,0],[0,1,0]]`	`1`	Everyone knows 1; 1 knows nobody
`[[0,1],[1,0]]`	`-1`	They know each other
`[[1,1,0],[0,1,0],[0,1,1]]`	`1`	The diagonal (knowing yourself) is ignored
`[[0,0,1,0],[0,0,1,0],[0,0,0,0],[0,0,1,0]]`	`2`
`[[0,0,0],[0,0,0],[0,0,0]]`	`-1`	Nobody is known by the others
`[[0]]`	`0`	A lone person qualifies

(Confirm: at most one celebrity can exist; the diagonal M[i][i] carries no information and is ignored.)

How interviewers phrase it

"Find the celebrity in a party of N people, given a knows-matrix" (GeeksforGeeks "The Celebrity Problem"; LeetCode 277 with a knows(a, b) API).

Clarifying questions to ask

Is the diagonal meaningful? (No, ignore it.)
Can there be more than one celebrity? (No: two celebrities would each have to know the other.)
Is each knows() lookup expensive? (That's why O(n) questions matters.)

Follow-ups to expect

"Why does one question eliminate someone?"
"Why is the final check needed?"
"What's the stack version?"
"How many questions in total?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview