Celebrity Problem
Flexport
MicrosoftThe problem
A celebrity is a person who is known by everyone else at the party but does not know anyone in return. Given a square matrix M of size N x N where M[i][j] is 1 if person i knows person j, and 0 otherwise, determine if there is a celebrity at the party. Return the index of the celebrity or -1 if no such person exists.
Note that M[i][i] is always 0.
Input: M = [ [0, 1, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [0, 1, 1, 0] ] Output: 1 Explanation: Person 1 does not know anyone and is known by persons 0, 2, and 3. Therefore, person 1 is the celebrity.
Input: M = [ [0, 1], [1, 0] ] Output: -1 Explanation: Both persons know each other, so there is no celebrity.
Input: M = [ [0, 1, 0], [0, 0, 0], [0, 1, 0] ]
- 1 <= N <= 3000
- 0 <= M[][] <= 1
cpp
class Solution
{
public:
int celebrity(vector<vector<int>> &M){
}
};java
class Solution {
public int celebrity(int[][] M) {
}
}python
class Solution:
def celebrity(self, M):javascript
class Solution {
celebrity(M) {
}
}csharp
public class Solution
{
public int celebrity(List<List<int>> M){
}
}go
func celebrity(M [][]int) int {
}Stuck? Show a way to structure it+
- 01Eliminate one of two people at each comparison to obtain a single candidate.
- 02If candidate knows i, candidate is replaced by i; otherwise i is eliminated.
- 03Verify that the candidate knows nobody and everyone else knows the candidate.
- 04Return no result when the final verification fails.
Reference answer
Then expect these follow-ups
Why does each comparison safely eliminate one person?
Tests: proof
Can there be two celebrities under this definition?
Tests: logical reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question