Find the Celebrity
Medium · Graphs · about 20 minutes
Asked at LinkedIn, Meta, Amazon, Apple, NVIDIA, SpaceX, Rivian, Arm.
At a party of n people (0..n-1), a celebrity is known by everyone else and knows nobody. You're given graph, where graph[a][b] == 1 means a knows b (treat each lookup as a call to knows(a, b)). Return the celebrity's label, or -1 if there is none. Aim for O(n) lookups.