Your manager said that the users are now demanding an additional feature where the Upzilla Browser will also show websites that the users have visited the most.
Therefore, your job is to implement an additional function called:
public void listTopVisitedSites(Queue<SiteStats> sites, int n)
sites is a queue that represents all the websites that the user has visited, as well the number of times that the user has visited each website
Please see below for definition of the SiteStats class
n represents the top n most visited sites that we want to retrieve from the queue
0 < n <= m, where m is the number of websites tracked by Queue<SiteStats> sites or the size of the queue
The function will print the top 5 sites and the no. of times they are visited. If multiple websites have been visited the same no. of times, then they should be ordered by recency (the last visited).
If the user has no browsing history, the function will print an empty array of type String
In addition, your manager mentions this feature will be shipped in the mobile version of Upzilla Browser. Therefore, you should use the minimal amount of space/memory possible to implement this function since memory is limited in mobile devices.
Thus, please follow these instructions while implementing the listTopVisitedSites(Queue<SiteStats> sites, int n) function:
Please sort Queue<SiteStats> sites without using any additional queue(s) or data structure(s)
a. In other words, sort Queue<SiteStats> sites using itself and do not allocate other data structures. You can do this by finding the most visited site and reordering the queue so that the most visited sites take the top positions after sorting is completed.
Once the queue is sorted, please print the top N sites
The runtime and space complexity of your implementation should be O(
N
2
) and O(1) respectively.
You would also need to complete the following method -
public static void updateCount(String url)
This method finds the given website in the queue and increments the visited count by 1, if the website is found in the queue. If the website is not found, it adds a new node to the queue.
Note:
In order to not limit the number of distinct sites that the users could visit from the browser, SiteStats were not stored in a constant sized array. Instead, the number of websites visited is stored in a Queue.
This also had the benefit of allowing quick updates to the numVisits variable, as user behaviour showed that they were more likely to visit sites that they had not recently gone to. Thus following a somewhat FIFO approach.