Find the Celebrity

Medium

Uber

0 views

Let's play a game at a party! Imagine there are n people at the party, labeled from 0 to n - 1. Among these n people, at most one is a celebrity. A celebrity is defined as someone who is known by everyone else at the party, but they don't know anyone else. So, everyone knows the celebrity, but the celebrity doesn't know anyone.

Your task is to find out who the celebrity is, if they exist. You are only allowed to ask one type of question: "Does person A know person B?" Luckily, there's a function called knows(a, b) which tells you whether person A knows person B. This function is already implemented. Your code should call this helper function as few times as possible.

Write a function int findCelebrity(n) that takes the number of people n as input and returns the label of the celebrity if there is one, or -1 if there is no celebrity. Assume 1 <= n <= 100 and there will be at most one celebrity.

For example, consider the following scenario:

n = 3
knows = [
  [1,1,0],
  [0,1,0],
  [1,1,1]
]

Here, knows[i][j] means whether person i knows person j. Based on the definition of a celebrity:

Person 0 is not a celebrity because they know person 1.
Person 1 is not a celebrity because person 0 knows them, but they also know person 2.
Person 2 is not a celebrity because person 0 and person 1 know them, but they also know persons 0 and 1.

Therefore, findCelebrity(3) should return -1.

Another example:

n = 2
knows = [
  [1,0],
  [1,1]
]

Person 0 is not a celebrity because person 1 knows them, but they know person 1.
Person 1 is not a celebrity because person 0 knows them, and they also know person 0.

Therefore, findCelebrity(2) should return -1.

Can you implement the findCelebrity function efficiently?

Find the Celebrity

Medium

Uber

0 views

Let's play a game at a party! Imagine there are n people at the party, labeled from 0 to n - 1. Among these n people, at most one is a celebrity. A celebrity is defined as someone who is known by everyone else at the party, but they don't know anyone else. So, everyone knows the celebrity, but the celebrity doesn't know anyone.

Your task is to find out who the celebrity is, if they exist. You are only allowed to ask one type of question: "Does person A know person B?" Luckily, there's a function called knows(a, b) which tells you whether person A knows person B. This function is already implemented. Your code should call this helper function as few times as possible.

Write a function int findCelebrity(n) that takes the number of people n as input and returns the label of the celebrity if there is one, or -1 if there is no celebrity. Assume 1 <= n <= 100 and there will be at most one celebrity.

For example, consider the following scenario:

n = 3
knows = [
  [1,1,0],
  [0,1,0],
  [1,1,1]
]

Here, knows[i][j] means whether person i knows person j. Based on the definition of a celebrity:

Person 0 is not a celebrity because they know person 1.
Person 1 is not a celebrity because person 0 knows them, but they also know person 2.
Person 2 is not a celebrity because person 0 and person 1 know them, but they also know persons 0 and 1.

Therefore, findCelebrity(3) should return -1.

Another example:

n = 2
knows = [
  [1,0],
  [1,1]
]

Person 0 is not a celebrity because person 1 knows them, but they know person 1.
Person 1 is not a celebrity because person 0 knows them, and they also know person 0.

Therefore, findCelebrity(2) should return -1.

Can you implement the findCelebrity function efficiently?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the integer n (number of people)?
If there is no celebrity, should I return -1, or is there another specific value I should return?
Is it possible for there to be multiple people who are known by everyone else and know no one, or is the celebrity guaranteed to be unique if they exist?
Is it possible for someone to know themselves (i.e., knows(a, a) could return true)?
Can I assume the 'knows' function is implemented correctly and has a time complexity of O(1)?

Brute Force Solution

Approach

The brute force method for finding a celebrity means checking every single person to see if they fit the celebrity requirements. We treat each person as a potential celebrity and systematically verify if they meet the conditions.

Here's how the algorithm would work step-by-step:

Pick the first person on the list.
Check if everyone else knows this person.
Also, check if this person knows no one else.
If both of these are true, then this person is the celebrity, and we are done.
If not, repeat this process, but pick the next person on the list.
Continue until you find a celebrity or have checked everyone.

Code Implementation

def find_celebrity_brute_force(number_of_people, knows):
    for potential_celebrity in range(number_of_people):
        is_actually_celebrity = True

        # Check if everyone else knows the potential celebrity
        for other_person in range(number_of_people):
            if potential_celebrity == other_person:
                continue
            if not knows(other_person, potential_celebrity):
                is_actually_celebrity = False
                break

        # Check if the potential celebrity knows anyone else
        if is_actually_celebrity:

            # Must verify potential celebrity knows no one
            for other_person in range(number_of_people):
                if potential_celebrity == other_person:
                    continue

                # Found someone the potential celebrity knows
                if knows(potential_celebrity, other_person):
                    is_actually_celebrity = False
                    break

        # Found a celebrity
        if is_actually_celebrity:
            return potential_celebrity

    return -1

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n people to check if they are a celebrity. For each person, it checks if everyone else knows them (requiring n-1 calls to the knows function) and if the person knows no one else (again requiring n-1 calls to the knows function). This nested checking for each potential celebrity results in (n * (n-1) + n * (n-1)) operations which approximate to n * n. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The brute force algorithm iterates through the list of people and checks conditions for each person. It does not create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or track visited people. It uses only a few variables to keep track of the current person being evaluated as a potential celebrity and potentially a boolean variable to hold intermediate checks. Thus, the space used remains constant regardless of the input size N (number of people), giving us a space complexity of O(1).

Optimal Solution

Approach

The problem is to find a 'celebrity' in a group, where a celebrity is someone everyone knows, but who doesn't know anyone else. The efficient strategy is to eliminate candidates who cannot be the celebrity, quickly narrowing down to a single potential celebrity, and then verifying if this person truly fits the celebrity criteria.

Here's how the algorithm would work step-by-step:

Start by picking two people from the group.
If the first person knows the second person, then the first person cannot be the celebrity. We know this because a celebrity doesn't know anyone else.
If the first person doesn't know the second person, then the second person cannot be the celebrity. We know this because everyone must know the celebrity.
Repeat this comparison, always eliminating one person at a time, until you're left with only one potential celebrity.
Now that you have a potential celebrity, you need to double-check that they really are a celebrity.
Verify that everyone else knows the potential celebrity.
Verify that the potential celebrity doesn't know anyone else.
If both checks pass, then you've found the celebrity. If either check fails, there is no celebrity in the group.

Code Implementation

def find_celebrity(number_of_people):
    potential_celebrity = 0
    for i in range(1, number_of_people):
        if knows(potential_celebrity, i):
            #If potential knows i, potential is not celebrity
            potential_celebrity = i

    # Verify if potential_celebrity is actually a celebrity.
    for i in range(number_of_people):
        if i != potential_celebrity:
            if not knows(i, potential_celebrity) or knows(potential_celebrity, i):
                #Must be known by everyone, and know nobody
                return -1

    #Last step to verify
    if knows(potential_celebrity, potential_celebrity):
        return -1

    return potential_celebrity

Big(O) Analysis

Time Complexity

O(n) – The algorithm first reduces the potential celebrity candidates to a single person through pair comparisons in a single pass, requiring at most n-1 comparisons. Then, it verifies if the potential celebrity is indeed a celebrity. The verification step involves checking if everyone knows the potential celebrity (n-1 checks) and if the potential celebrity knows no one (n-1 checks). Therefore, the total number of operations is approximately (n-1) + (n-1) + (n-1) = 3n - 3, which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only requires a few variables to keep track of the potential celebrity candidate and loop counters for verification. The space required does not depend on the number of people (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
n is zero or negative	Return -1 immediately as a celebrity cannot exist in an empty or nonsensical room size.
n is one	Person 0 is a celebrity if they know nobody (knows(0,x) is always false for all x).
No celebrity exists	The algorithm should correctly identify and return -1 if no one satisfies the celebrity criteria.
Multiple potential candidates after the first loop	The second verification loop must filter down to ensure only a true celebrity is returned.
The 'knows' function is implemented incorrectly or inconsistently.	Assume the 'knows' function is correctly implemented according to the problem description.
Integer overflow when calculating indices or using large n	The index should not overflow as long as it does not exceed the integer limit, assuming the 'knows' function accepts integer types, but large n can affect the algorithm's runtime complexity.
Input 'n' exceeding available memory	The solution must be space-efficient to avoid out-of-memory errors for large 'n', and should scale linearly.
Candidate celebrity knowing themselves (knows(candidate, candidate) is true)	This should be handled during the verification phase, returning -1 if this impossible condition occurs.