find the celebrity

🏠

Suppose you are at a party with n people (labeled from 0 to n - 1), and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her, but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

Let's begin with our who knows who adjacency Matrix.

 1M = [
 2[1,1,0,0,0,0,0,0],
 3[0,1,0,0,0,0,1,0],
 4[1,1,1,1,0,0,0,0],
 5[0,1,1,1,0,0,1,0],
 6[0,1,0,0,1,0,0,1],
 7[0,1,0,1,0,1,0,0],
 8[0,1,0,1,0,0,1,0],
 9[0,1,0,0,1,0,0,1],
10]

If you were to ask "does person 2 know person 3" you'd perform a look at M[2][3]. We can therefore observe that everyone knows person 1, but person 1 doesn't know anyone (besides themselves).

The naive way of doing this, is to ask if each person knows every other person, which obviously has a time complexity of , and it thus inefficient.

 1M = [
 2[1,1,0,0,0,0,0,0],
 3[0,1,0,0,0,0,0,0],
 4[1,1,1,1,0,0,0,0],
 5[0,1,1,1,0,0,1,0],
 6[0,1,0,0,1,0,0,1],
 7[0,1,0,1,0,1,0,0],
 8[0,1,0,1,0,0,1,0],
 9[0,1,0,0,1,0,0,1],
10]
11
12def knows(a, b):
13    return M[a][b]
14
15def find_celebrity(n):
16    for i in range(n):
17        if all(not knows(i, j) and knows(j, i) for j in range(n) if i != j):
18            return i
19    return -1
20
21print(find_celebrity(len(M)))

Optimisation: Candidate Celebrity Hopping

This problem can be hugely optimised by treating the knowing relationship as a directed graph. Since everyone knows the celebrity, but the celebrity knows no-one, we can do the following:

1def find_celebrity(n):
2    c = reduce(lambda a, b: (a, b)[knows(a, b)], range(1, n), 0)
3  return c

reduce with a ternary handles this logic beautifully. Our celebrity candidate is 0 which is the initialiser to reduce. We then iterate from 1 through to the last guest, while holding on to the most well-known person in the room as our candidate.

Celebrity Confirmation

1return (-1, c)[all(c == j or (g(j, c) and not g(c, j)) for j in range(n))]

Our final step is making sure our candidate is indeed a celebrity. This is easily done with all handling the simple logic of being known to all, but knowing no-one.

Putting it all together

The leetcode question specifies the knows API so one must assume it's slow; this potential latency can easily be mitigated with caching.

 1M = [
 2[1,1,0,0,0,0,0,0],
 3[0,1,0,0,0,0,0,0],
 4[1,1,1,1,0,0,0,0],
 5[0,1,1,1,0,0,1,0],
 6[0,1,0,0,1,0,0,1],
 7[0,1,0,1,0,1,0,0],
 8[0,1,0,1,0,0,1,0],
 9[0,1,0,0,1,0,0,1],
10]
11
12def knows(a, b):
13    return M[a][b]
14
15def find_celebrity(n):
16    g = lru_cache(None)(knows)
17    c = reduce(lambda a, b: (a, b)[g(a, b)], range(1, n), 0)
18    return (-1, c)[all(c == j or (g(j, c) and not g(c, j)) for j in range(n))]
19
20print(find_celebrity(len(M)))

This may seem cryptic, and this style is not recommended in the workplace. But who is to say this is essentially wrong in any way? Being able to pack this amount of work in one-liners is a Python superpower, albeit one that ought to be used responsibly.

Time and Space Complexity