{"id":672,"date":"2017-01-18T14:15:01","date_gmt":"2017-01-18T14:15:01","guid":{"rendered":"https:\/\/www.audero.it\/blog\/?p=672"},"modified":"2017-01-18T14:39:42","modified_gmt":"2017-01-18T14:39:42","slug":"from-javascript-developer-to-javascript-engineer-find-all-celebrities-in-a-set-of-people","status":"publish","type":"post","link":"https:\/\/www.audero.it\/blog\/2017\/01\/18\/from-javascript-developer-to-javascript-engineer-find-all-celebrities-in-a-set-of-people\/","title":{"rendered":"From JavaScript developer to JavaScript engineer: find all celebrities in a set of people"},"content":{"rendered":"

In the first article of my series From JavaScript developer to JavaScript engineer<\/a><\/cite> titled From JavaScript developer to JavaScript engineer: Re-implementing ECMAScript 2015’s String.prototype.repeat() method<\/a><\/cite> I’ve discussed how computer science concepts can help in writing better and more elegant software<\/strong>. Specifically, I’ve demonstrated how to use appropriate algorithms and data structures<\/strong>, together with techniques like memoization, to re-implement the String.prototype.repeat()<\/code> method so that it’s blazing fast.<\/p>\n

In this second article of the series, I’ll discuss how important is reasoning about the problem we’re facing. To do that, I’ll analyze the problem of finding all celebrities in a set of people.<\/p>\n

If you want to take a look at the final solution, you can either go to the section An efficient solution<\/cite> or browse my Interview questions<\/cite> repository on GitHub<\/a>.
\n<\/p>\n

Introducing the problem<\/h2>\n

\"\"<\/p>\n

The problem I’ll analyze in this article is about finding all the celebrities in a set of people. On its own, this isn’t very informative, so here it is the text of the problem:<\/p>\n

A person is considered a celebrity if he\/she likes nobody and everybody likes him\/her. Given a set of people and a function likes(i, j)<\/code>, which takes the names of two people as parameters and returns true<\/code> if i<\/var> likes j<\/var> and false<\/code> otherwise, write a findCelebrities()<\/code> function to return all the celebrities in the given set.<\/p><\/blockquote>\n

The description of the problem might have still left you a bit confused, so let’s consider a couple of examples.<\/p>\n

Given an empty set of people (for example, const people = [];<\/code>), regardless of the values returned by the likes()<\/code> function, findCelebrities()<\/code> should return an empty set (that is []<\/code>).<\/p>\n

Let’s now consider a more complex example. Given a set of many people:<\/p>\n

\r\nconst people = [\r\n   'Mark',\r\n   'David',\r\n   'John',\r\n   'Aurelio',\r\n   'Anna',\r\n   'Peter'\r\n];\r\n<\/pre>\n
and the following likes()<\/code> function:<\/p>\n
\r\nfunction likes(i, j) {\r\n   return i !== 'Peter';\r\n}\r\n<\/pre>\n
findCelebrities()<\/code> should return:<\/p>\n
\r\nfindCelebrities(people, likes); \/\/ ['Peter']\r\n<\/pre>\n
These two examples have hopefully clarified the behavior of the findCelebrities()<\/code> function. So, it’s now time to implement it.<\/p>\n
A simple solution<\/h2>\n
The text of the problem asks to find all celebrities in a set of people. A celebrity is defined as someone that likes nobody and is liked by everyone. This condition can be expressed with the following set-builder notation:<\/p>\n
\"The<\/p>\n
This notation gives us the simplest solution to the problem. We start with a fixed person, let’s call this person candidate<\/var>, and loop through the whole set P<\/var> (where P<\/var> stands for people) to verify the condition that everyone else likes candidate<\/var> and candidate<\/var> dislikes everyone else. We can stop the loop as soon as one of these two conditions is not verified. In such case, we know that candidate<\/var> is not a celebrity. We then repeat this process for every person in the set P<\/var>. Once done, we’ll obtain the set C<\/var> of all the celebrities.<\/p>\n
Turning this description into code, results in the following code:<\/p>\n
\r\nfunction findCelebrities(people, likes) {\r\n   return people.filter(function(candidate) {\r\n      return !people.find(function(person) {\r\n         return person !== candidate &&\r\n            (likes(candidate, person) || !likes(person, candidate));\r\n      });\r\n   });\r\n}\r\n<\/pre>\n
The code above is concise but not very efficient. If we analyze its time complexity, we can demonstrate that it’s an O(n<\/var>2<\/sup>)<\/em> where n<\/var> is the number of the people in the set. The reason is that we loop over every person in the set and for each of them we scan again the whole set to verify that the conditions to be a celebrity are met.<\/p>\n
If you have never heard of the Big O notation<\/a>, I suggest you to learn more about it. It\u2019s a fundamental concept to analyze the performance of your algorithms.<\/small><\/p>\n
The time complexity of this function can be heavily improved. In the next section I’ll show you how.<\/p>\n
Analysis of the problem<\/h2>\n
To understand how we can optimize findCelebrities()<\/code>, we have to think what its weak points are.<\/p>\n
Every set has at most one celebrity<\/h3>\n
The most important point to understand is the amount of celebrities that may be present in the given set. The text asks to find all of them, but in a given set there may be at most one. The demonstration can be made by using reductio ad absurdum<\/em><\/a>.<\/p>\n
Let’s say that more than one celebrity can be present in the set, for example two. We may assume, without loss of generality, that they are the first and the second person that we’ll process. Because the first person is a celebrity, it occurs that everyone else likes the person and the latter doesn’t like everyone else. But if this is true, then it means that the second celebrity is at least not liked by the first celebrity (it’s also true that the second celebrity likes someone, the first celebrity). Therefore, the second celebrity can’t be a celebrity at all, which confirms the previous statement.<\/p>\n
Choosing the best candidate to be a celebrity<\/h3>\n
Thanks to the consideration of the previous section, we can optimize the algorithm to search for the best candidate to be a celebrity. Once we find it, we test that this person meets the two conditions required. If the conditions are met, we have a celebrity; otherwise the set doesn’t include any celebrity.<\/p>\n
We can start with the assumption that the first person in the set is the best candidate and test the relation against the other people in the set, one at a time. If one of the two conditions is not met, that is if the candidate likes the person currently under analysis or the candidate isn’t liked by the person, we know that the current best candidate isn’t a celebrity. In particular, we deal with two possible scenarios:<\/p>\n