[Solution]Problem 39: Find the Celebrity[Pintrest]

Math, Logic, Summations

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).

Thank you for all the support you’ve shown me. Much more high-quality content to come. If you have something to say to me, you can just reply to this email.

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.

Remember, always go for the brute force first. Take the low-hanging fruit.

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.

As a side note, you should develop a foundation in philosophy and economics to become a super coder. Taken from my article, Liberal Arts will make you Better at Machine Learning

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.

Join the cool kids with a sub. Remember if you’re not happy with the purchase, then I will refund you fully. No questions asked. There’s no risk to you.

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.

Step 3: Filtering

Let’s go back to the sentence-

At a party, there is a single person who everyone knows, but who does not know anyone in return (the "celebrity")

This gives us access to 2 possible crucial pieces of information. To understand them, let’s take 2 two people, i and j, and call knows(i,j) on them. Based on the return, we can make 2 deductions on them-

1. If it returns true, i knows j. Thus, i can’t be the celebrity, since the celebrity doesn’t know anybody.

2. If it returns false, then i doesn’t know j. Thus, j can’t be the celeb, since the celeb is known by all.

Through this, we can start removing the non-celebs really quickly. Every comparison we make, allows us to reduce the size of the potential celebs by 1.

So our solution will be simple. While we have more than 1 person in our potential list, we pop 2. Based on our logic, we will filter one of them. The one remaining will be readded to our potential list. We simply have to go through our list till we have only 1 left. The last one standing is the celeb.

Step 4: Coding it up

This is the final step we have to make. Fortunately, this is not super tricky to code up.

def find_celebrity(people):
    while len(people) > 1:
        i, j = people.pop(), people.pop()

        if knows(i, j):
            people.append(j) #celeb is known by all
        else:
            people.append(i) #celeb knows nobody

    return people[0]

The extra space complexity is trivial to calculate. However, I saw a couple of people struggle with the time complexity. The pops and readds were hard for them to work with. Fear not, I am here.

Notice that the pops and readds are basically a red-herring. This is because we have already established that we will always remove one person from our potential list. At the end of each iteration, the size of our list reduces by 1. This makes it clear that we will need N-1 calls to our knows function. Since all our operations are constant time our overall time complexity will be O(N).

Time Complexity- O(N)

Space Complexity- O(1)

Make sure you share your thoughts on this question/solution/any interesting questions/developments in the comments or through my links.

Happy Prep. I’ll see you at your dream job.

Go kill all you Topnotch Technician,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75