c) For (ii), describe the algrorithm, step by step, to output the top k streamed

Question

c) For (ii), describe the algrorithm, step by step, to output the top k streamed movies in genre g in year y. Describe additional data structures, if any, used in this process. Analyze its big O running time. Show your work. Specify whether the running time is worst case or something else

Note: a) is asking for java data structures and b) is asking for the java algorithms (No Code). There is no coding whatssoever in this question.

For a), I think a hashmap using a genre and a linked list for the title can be used in O(1) time. I just need help with the algorithm.

It would help me a great deal if you can please answer all the parts.

Also, this question wants the most efficient algorithm as possible in Big O running time.

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 the top k most streamed movies in genre g in year y. (f y is the current year, then accounting is done up to the current date of the year.) For example, what were the top 10 most streamed comedy movies in 2013? Here k 10, g "comedy" and y 2013. 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, toupdate the data structures. Analyze its big O running time. Show your work. Specify whether the running time is worst case or something else.

Explanation / Answer

Solution:

a).Data Structure using:
   ArrayList,HashMap.

b) Algorithm to implement:

1.create a class for movie with instant variables.
movie name,genre,year streamed
   create accossors for the above.

2. create an arraylist having the list of movies streamed.
3. Build a map of counters whose keys are the movies which are streamed and value is no of times its gets streamed.

4. Create an array of the map's entries - the entries are of the form (key,value) where key is genre and value is the above created map.

5.create an array of the map enteries -the entries are of the form(key,value) where key is the year and value is the genre list created above.

6. Use the median of median algorithm to find the k most movies of type genre streamed in the specified year .

7. Iterate over the array and provide the logic to find the k most movies of type genre streamed in the specified year.

8.The idea is we have the movie with number of times streamed.so we have to get list of movies for the selected genre and then the list of genre for the selected year

c) Time For Execution.

Complexity: O(n)
run-time complexity: O(n)
Space complexity : O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.