We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Celebrity

Number: 277

Difficulty: Medium

Paid? Yes

Companies: LinkedIn, Microsoft, Meta, Amazon, Uber, Toast, Goldman Sachs, TikTok, DoorDash

Problem Description

There is a party with n people labeled from 0 to n-1. One of them might be a celebrity. A celebrity is known by everyone else, but the celebrity knows no one at the party. You can ask questions using an API call knows(a, b) which returns true if person a knows person b. Your task is to find the celebrity (if one exists) while minimizing the number of API calls.

Key Insights

  • Use pairwise comparisons to eliminate non-celebrities.
  • If a candidate knows another person, the candidate cannot be the celebrity.
  • Verify the candidate by checking that they do not know anyone and that everyone knows them.
  • Achieve the solution in two passes: one for candidate selection and the other for validation.

Space and Time Complexity

Time Complexity: O(n) – One pass for candidate selection and one for validation. Space Complexity: O(1) – Only constant extra space is used.

Solution

The approach consists of two main steps:

  1. Candidate Selection: Iterate through the people and maintain a candidate. For every person i, if the current candidate knows i, then set candidate = i. This works because if candidate knows i, candidate cannot be the celebrity.
  2. Verification: Check that the candidate does not know any other person and that every other person knows the candidate. If both conditions hold, candidate is the celebrity; otherwise, return -1.

The main data structures used are simple integer variables. The algorithm leverages a two-pass technique to reduce the number of knows API calls while ensuring correctness.

Code Solutions

# Function definition for findCelebrity using the helper knows(a, b) API.
def findCelebrity(n):
    # Step 1: Candidate Selection.
    candidate = 0
    for i in range(1, n):
        # If candidate knows i, then candidate cannot be the celebrity.
        if knows(candidate, i):
            candidate = i  # Select new candidate.
    
    # Step 2: Verification.
    # Check if candidate does not know any other person.
    for i in range(n):
        if i != candidate:
            # Either candidate knows someone or someone doesn't know candidate.
            if knows(candidate, i) or not knows(i, candidate):
                return -1
    return candidate

# Example helper function (for testing, this is normally provided in the problem context).
def knows(a, b):
    # This function should return True if person a knows person b, otherwise False.
    pass
← Back to All Questions