Question

1. Suppose that you have a program that can read through all posts within a given time period (e.g. the last 7 days) on a social network web site (e.g., Facebook), and generate a list of pairs (ui, pi) representing texts in all posts found, where i=1, 2, ..., and ui and pi represent the author username and the text content of the i-th post found, respectively. Describe an algorithm that outputs the list of usernames in the decreasing order of their total numbers of words posted among the posts described above. Analyze the running time of your algorithm. You may assume that the input of your algorithm is two arrays U and P that store the pairs (ui, pi) as defined above.

Please answer differently than solution already on chegg, I would like explanations to steps. Thank you.

Answer 1

Algorithm for above will be :-

1) Funtion which takes two input , one is the author array , and other is the posts array.

2)This functions returns the authors array , in the decreasing order of their words in the post.

3)The function will contain :-

• Call another function , passing the posts array.
  • In this function , start a loop over the posts array.
  • In each iteration calculate the number of words in each post[i] ( i being the iterator).
  • You can easily calculate the nmber of words using the stringstream (this is present in C++).
  • Create another array postlength , which will contain the number of words in each post[i].
  • Return the postlength array from this function.
• Accept the postlength array returned from above funtion.
• Now, you will have two arrays , author array(containing the authors name) and secondly postlength array(contianing the number of words in each posts).
• Now, initialise a map , which will contain author's name as key and number of words as value.
• Now start a loop over the author's array. In each itereation you will do :-
  • If the author[i] ( i being the iterator) is present in the map's key , just fetch the value from the map , corresponding to the author[i] and add the postlenght[i] value to the value retrieved. Now insert new value with the author[i] in the map.
  • If the author[i] is not present in the map's key, insert the pair(author[i],postlength[i]) in the map.
• Now sort the map according to the values, and return the map's key by storing them in an array.
• For sorting the map you can use the insertion sort , where just create a new array and insert the map's key according to its value in the map.
• The time complexity willl be O(n^2) because of the time complexity of insertion sort which will be maximum and for other loops it will be O(n) as we are iterating over the array once only in each loops . So time complexity is max of all time complexity which will be O(n^2).

This solution is according to me , and if you need any help , just comment , I will be happy to help.