FastPrepParty Celebrity from a Knows Matrix
Problems/Party Celebrity from a Knows Matrix

Party Celebrity from a Knows Matrix

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A post published on October 27, 2022, by a student who received an Expedia summer SDE internship offer through campus hiring, places this task in the first of two same-day interviews that mixed technical and behavioral questions. A pair-sum question came before it. Besides the task's usual name, the post adds only the approach used: a stack, in linear time.

The post gives no input format, examples or limits. Here, who knows whom comes as an n by n matrix of 0s and 1s with 0s on the diagonal, for 2 to 200 people. You return the celebrity's number, or -1 when there is no celebrity.

Our version is about 85% the same as the reported question.

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[][]) → int

Examples

Example 1

knows = [[0,1,0],[0,0,0],[1,1,0]]return = 1

Row 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 = -1

Every 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 = -1

Persons 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].length
  • 2 <= n <= 200
  • Each knows[i][j] is 0 or 1.
  • knows[i][i] == 0 for every i.

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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int findCelebrity(int[][] knows) {
        // Write your code here.
    }
}
Checking account…