logo CodeStepByStep logo

coolest

Language/Type: C++ basics streams file input
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function 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 name2. 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).

Stuart Marty
Helene Elmer
Donald Marty
Bruce Elmer
Donald Elmer
Donald Stuart
Stuart Mehran
Mehran Donald
Reid Elmer
Marty Mehran

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.

Constraints: 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 vectors, 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.

Type your C++ solution code here:


This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.