A website streams movies to customers' TVs or other devices. Movies are in one of several genres such as action, drama, mystery, etc. Every movie is in exactly one genre (so that if a movie is an action movie as well as a comedy, it is in a genre called "action-comedy"). The site has around 10 million customers, and around 25,000 movies, but both are growing rapidly. The site wants to keep track of the most popular movies streamed. You have been hired as the lead engineer

to develop a tracking program.

i) Every time a movie is streamed to a customer, its name (e.g. "A Very Harold & Kumar 3D Christmas") and genre ("Comedy") is sent to your program, which then updates the data structures it maintains. (Assume your program can get the current year with a call to an appropriate Java class, in O(1) time.)

ii) Customers want to know what were the top k most streamed movies in genre g in year y. (If y is the current year, then accounting is done up to the current date.) For example, what were the top 10 most streamed comedy movies in 2012? Here k = 10, g="comedy" and y = 2012. This query is sent to your program which should output the top k movie names, in descending order of number of times streamed.

• a)Describe the data structures used to implement the above.

b)For (i), describe the algorithm, step by step, to update the data structures. Analyze its big O running time.

Show your work. Specify whether the running time is worst case or something else.

c) For (ii), analyze the big O running time to output the top k streamed movies. Describe additional data

structures, if any, used in this process. Show your work. Specify whether the running time is worst case