A website streams movies to customers’ TVs or other devices. Movies are in one o

Question

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. “Harold and Kumar: Escape from Guan- tanamo Bay”) and genre (“Comedy”) is sent to your program so it can update 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) Also, every once in a while, 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 2010? Here k = 10, g=”comeday” and y = 2010. This query is sent to your program which should output the top k movie names.

Describe the data structures and algorithms used to implement both requirements. For (i), analyze the big O running time to update the data structures, and for (ii) the big O running time to output the top k streamed movies. Show your work. Also specify whether the running time is worst case or average case.

Explanation / Answer

Answer :

(i) For this case we can use growalble array or array as underlying data structure to update the data sent to the programmar.

Algorithm:

begin procedure search: arr,n,x

Take n and x i.e size of array and value to search in array values

   for condition i <n do
       if arr[i] is equlas x
           return i;
       end if
   end for
return -1
end procedure

Worst Case:
In the worst case we calculate upper bound on running time of an algorithm and we know the case that causes maximum number of operations to be executed. For Linear Search such as in our array with movie name and genre , the worst case happens when the combination of movie and genre found to be searched (given as x in the above code) is not present in the array. When x is not present, the search() functions compares it with all the elements of array one after the other one. Therefore, the worst case time complexity of updation of our data structure would be (n).

Best Case:
In the best case we calculate lower bound on running time of an algorithm and we know the case that causes minimum number of operations to be executed. In the our problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant.So time complexity in the best case would be (1)

(ii) For this case we can use growalble stack or stack using linked lists or array as data structure to know what were the top k most streamed movies in genre g in year y based on the input send to programmar.

Algorithm:

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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