Time Needed to Stream Movies - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Standard (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is an integer array movies, where each element represents the number of movies a user wants to stream, and an integer k representing the index of the user we are interested in.
• Q: What is the output?
  • A: The output is the total time (in seconds) it takes for the user at position k to finish streaming all their movies.
• Q: What happens when a user has streamed all their movies?
  • A: The user leaves the queue and does not re-enter.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a queue to simulate the streaming process, keeping track of each user's remaining movies and the total time until the user at position k finishes streaming.

1. Initialize an empty deque (queue).
2. Populate the queue with tuples `(i, movies[i])`, where `i` is the index of the user and `movies[i]` is the number of movies they want to stream.
3. Initialize a `time` variable to keep track of the time taken.
4. While there are users in the queue:
   1. Dequeue the first user and increment the `time` by 1 as they stream one movie.
   2. If this user is at index `k` and has just streamed their last movie, return the `time`.
   3. If the user still has movies left to stream, decrease their movie count by 1 and enqueue them back to the end of the queue.
5. Return the `time` when the loop exits (though logically, the return should happen inside the loop).

⚠️ Common Mistakes

• Forgetting to check if the user is the one at index k before they leave the queue.
• Not properly simulating the queue behavior where users re-enter the queue after streaming a movie.
• Incorrectly calculating the time taken by not properly managing the queue.

I-mplement

from collections import deque

def time_required_to_stream(movies, k):
    # Initialize an empty queue
    queue = deque()
    
    # Populate the queue with (index, movie_count) tuples
    for i in range(len(movies)):
        queue.append((i, movies[i]))
    
    time = 0
    
    while queue:
        i, movie_count = queue.popleft()  # Get the current user and their movie count
        time += 1  # Increment time as the user streams one movie
        
        if i == k and movie_count == 1:
            # If this is user k and they've just streamed their last movie, return the time
            return time
        
        if movie_count > 1:
            # If the user has more movies to stream, reduce their count and put them back in the queue
            queue.append((i, movie_count - 1))

    return time  # In case something goes wrong, although we should always return within the loop