Hello my super dedicated reader,
Hope you’re having a groovy almost-weekend. I could hear you waiting anxiously for my solution. Through our super deep spiritual connection, I know that my posts are your favorite thing about the day (don’t burst my bubble).
Problem
This problem was asked by Pinterest.
At a party, there is a single person who everyone knows, but who does not know anyone in return (the "celebrity"). To help figure out who this is, you have access to an O(1)
method called knows(a, b)
, which returns True
if person a
knows person b
, else False
.
Given a list of N
people and the above operation, find a way to identify the celebrity in O(N)
time.
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Only 15 days left in this offer -
Step 1: Brute Force
This is one of those problems where the setup is super simple. No hidden rules, no weird transitions. So we can jump into our brute force solution immediately.
Our brute force works by comparing every pair of people at the party. For this, we create a dictionary that stores the Boolean values corresponding to whether a person is known by others. We do this for each person. We use a dictionary because we will be doing many insertions, lookups, and searches. So the O(1) time complexity of dictionaries will come in handy. To learn more about hashing, the underlying idea behind dictionaries and sets, check out this Math Monday.
For each pair (i, j)
, we append the value of knows(i, j)
to the jth
key. Thus if our dictionary[Person 0]= [True,True, False, True] then we know that Person 1 is known by people 1 and 3 and not known by person 2.
Keep in mind knows(i,j) will always be true. Although how well does a person truly know themselves? For that matter, how well does someone “know” somebody else? And how can we comfortably separate the concept of self from the other, when we all influence each other? Some interesting questions for you to think about. And discuss with the interviewer.
Getting back to the solution, the key whose values are all True
must be the celebrity, since they are all known by everyone.
from collections import defaultdict
def find_celebrity(people):
who_knows = defaultdict(list)
for i in people:
for j in people:
who_knows[j].append(knows(i, j)) #does i know j?
for person in who_knows.keys():
if all(val == True for val in who_knows[person]):
return person
This is unfortunately very slow. As with all solutions that do pairwise comparisons over a list, the complexity will be O(N^2). Add to that our space complexity of O(N^2) since for every person, we have to store if they are known by all other people. We know that this is costly. How can we improve it?
Step 2: Why this solution is slow
Let’s take a second to think about why our solution is bad. This can give us lots of insight into coming up with the efficient solution.
We discuss this a lot in this newsletter, but let me remind you of an important trick to quickly figure out an optimal solution from the brute force code. You can apply this to any questions where we have been given a few conditions.
By definition, brute force solutions don’t take advantage of the constraints given to us. Indeed if we look at our brute-force, we will see that our solution doesn’t use the following-
... but who does not know anyone in return (the "celebrity")
We only use the first part (everyone knows the celebrity). Is the above condition really that powerful though? Yes it is. Using it, we will be cut our time complexity to O(N). Furthermore, our space complexity will be O(1). We will slash both our time and space costs by an order of n. Doing this IRL would guarantee your promotion.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.