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:
- nominate a celebrity candidate (guest 0)
- iterate over each guest
- if the candidate knows the guest, the guest becomes the candidate
- if the candidate does not know the guest, the candidate remains the candidate
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