Find the Celebrity
Updated
Problem statement
A group contains n people numbered from 0 through n - 1. You are given an n × n matrix knows: knows[a][b] = 1 means person a knows person b, and 0 means they do not.
A celebrity is known by every other person and knows no other person. Return the celebrity's index, or -1 when no celebrity exists. Diagonal entries are ignored. With one person, return 0.
Optimize the number of matrix lookups after the input is available. Matrix indexing provides the relation queries used in the interview.
Function
findCelebrity(knows: int[][]) → intExamples
Example 1
knows = [[0,0,1],[1,0,1],[0,0,0]]return = 2People 0 and 1 know person 2, while person 2 knows neither of them.
Example 2
knows = [[1,1],[1,0]]return = -1Each person knows the other, so neither is a celebrity. The diagonal values have no effect.
Constraints
1 <= n <= 50knows.length = n, and every row has lengthn.- Every entry is
0or1.
More Omnissa Onsite Interview questions
- Build and Check a Palindrome Linked ListONSITE INTERVIEW · Seen Sep 2026
- Maximum All-Ones Square Side LengthONSITE INTERVIEW · Seen Sep 2026
- Maximum Subarray SumONSITE INTERVIEW · Seen Sep 2026
- Coin ChangeONSITE INTERVIEW · Seen Jul 2026
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Jul 2026
- Rotate Array RightONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Minimum Station Tracks for a Train ScheduleBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Minimize Total Weight After HalvingAmazon · ONSITE INTERVIEW
- Capacity to Ship Packages Within DaysMicrosoft · OA · ONSITE INTERVIEWMicrosoft interview questions
- Gas StationeBay · ONSITE INTERVIEWeBay interview questions
- Make an Array Non-Decreasing With One ModificationGoogle · ONSITE INTERVIEWGoogle interview questions
- Wizard Scroll Allocation StrategyJane Street · ONSITE INTERVIEWJane Street interview questions
- Maximize Compatible Car RidersUber Freight · PHONE SCREEN · ONSITE INTERVIEWUber Freight interview questions
- Maximize Monsters DefeatedSalesforce · ONSITE INTERVIEWSalesforce interview questions