Find the Celebrity from Pairwise Acquaintances
Updated
Problem statement
A group contains n people numbered from 0 to n - 1. The matrix entry knows[a][b] is 1 exactly when person a knows person b.
A celebrity is known by every other person but knows no other person. At most one celebrity exists. Return the celebrity's index, or -1 if the group has no celebrity. Diagonal entries are irrelevant.
Function
findCelebrity(knows: int[][]) → intExamples
Example 1
knows = [[0,1,0],[0,0,0],[0,1,0]]return = 1People 0 and 2 know person 1, while person 1 knows neither of them.
Example 2
knows = [[0,1],[1,0]]return = -1Each person knows the other, so neither can be a celebrity.
Example 3
knows = [[1]]return = 0With one person, all off-diagonal celebrity conditions hold vacuously.
Constraints
1 <= n <= 2000.knowsis ann x nmatrix.- Every entry is
0or1. - Only off-diagonal entries determine the result.
More Amazon Onsite Interview questions
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dungeon GameONSITE INTERVIEW · Seen Nov 2026
- Integer BreakONSITE INTERVIEW · Seen Nov 2026
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
- First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Find the Celebrity from Pairwise AcquaintancesSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Minimum Operations to Sort with Rotations Then SwapsBank of New York Mellon · OA
- Optimal TransferSnowflake · OASnowflake interview questions
- Maximum XOR Elimination ScoreRippling · OARippling interview questions
- 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
- Capacity to Ship Packages Within DaysMicrosoft · OA · ONSITE INTERVIEWMicrosoft interview questions
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences