Write a method named
Coolest that accepts a string parameter storing a name of a file of information about Twitter followers and returns the name of the person who is the most "popular" in the data set, according to the following rules.
Twitter is a social network where users can "follow" each other to see each other's messages.
Following a user is a one-directional relationship; if A follows B, it does not necessarily mean that B follows A.
You might imagine that the most "popular" user is the one who has the most followers.
But it is more impressive to be followed by people who have a lot of followers themselves.
So we will define the "popularity" of a user to be the sum of the number of their followers' followers.
For example, if user A has three followers named B, C, and D, then A's popularity is the sum of the number of followers that B, C, and D have.
If B has 3 followers, C has 2, and D has 4, then A's popularity is 9.
(It does not matter if there is any overlap between the groups of people who follow B, C, and D in our example.)
One funny side effect of this popularity system is that you don't get any points for being followed by someone who has 0 followers.
In this problem, each line of the data file is in the format
"name1 name2", to indicate that the user
name1 follows the user
Your job is to read this data and return the name of the user with the highest popularity as described above.
If two users tie for the highest popularity, return the one whose name comes earlier in alphabetical order.
For example, suppose a file named
twitter.txt contains the lines below.
Given this data set, the call of
Coolest("twitter.txt") would return "Mehran" because Mehran has the highest popularity score of 3 due to being followed by Stuart (who has 1 follower) and by Marty (who has 2 followers).
You may assume valid input.
Specifically, assume that the given file exists, is readable by your code, and that each line of it is in the format above with two whitespace-separated one-word names per line.
Assume that the file contains at least one line of data.
You may also assume that no user follows themselves and that there are no duplicate lines in the file.
You do not need to worry about case-sensitivity on this problem; assume that each name always appears in the same case.
Your solution should read the file only once, not make multiple passes over the file data.
You may create up to two additional data structures (stack, queue, set, map, etc.) as auxiliary storage.
A nested structure, such as a set of lists, counts as one additional data structure.
(You can have as many simple variables as you like, such as ints or strings.)
Your solution should run in O(N2) time or faster, where N is the number of names in the file.