Party Celebrity from a Knows Matrix
Updated
Problem statement
There are n people at a party, numbered from 0 to n - 1. You are given an n x n matrix knows: knows[i][j] == 1 means person i knows person j, and 0 means they do not. Knowing is one-way: knows[i][j] and knows[j][i] can differ.
A celebrity is a person whom every other person knows, and who knows none of the other people.
Return the number of the celebrity, or -1 if there is no celebrity. There can never be two celebrities, so the answer is unique.
Function
findCelebrity(knows: int[][]) → intExamples
Example 1
knows = [[0,1,0],[0,0,0],[1,1,0]]return = 1Row 1 is all 0, so person 1 knows nobody. Column 1 has a 1 in rows 0 and 2, so both other people know person 1. Person 1 is the celebrity.
Example 2
knows = [[0,1,1],[1,0,1],[0,1,0]]return = -1Every row has at least one 1: person 0 knows persons 1 and 2, person 1 knows persons 0 and 2, and person 2 knows person 1. Everyone knows someone, so nobody is a celebrity, and the answer is -1.
Example 3
knows = [[0,0,1],[0,0,0],[0,0,0]]return = -1Persons 1 and 2 know nobody. But person 0 does not know person 1, and person 1 does not know person 2, so neither is known by everyone else. Person 0 knows person 2, so person 0 is not a celebrity either. The answer is -1.
Constraints
n == knows.length == knows[i].length2 <= n <= 200- Each
knows[i][j]is0or1. knows[i][i] == 0for everyi.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Search a Row- and Column-Sorted MatrixByteDance · ONSITE INTERVIEWByteDance interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Max Area of IslandGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Max Area of IslandRoku · ONSITE INTERVIEWRoku interview questions
- Max Area of IslandBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Area of IslandSambaNova Systems · ONSITE INTERVIEWSambaNova Systems interview questions
- Number of Islands IIAmazon · ONSITE INTERVIEW
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)