Morgan Stanley OA 2022 - Votes

Problem Description

An online streaming application wishes to analyze the popularity of web series streaming on their platform. Each web series is given a unique ID, and users vote for their favorite series. To analyze popularity, the marketing team has selected N users (with IDs from 0 to N-1) and recorded the IDs of the web series voted on by these users.

The marketing team analyzes the web series in batches of size K. The first batch consists of votes from users with IDs 0 to K-1. For the next batch, the vote of the user with ID 0 is removed from the left side, and the vote of the next user is added from the right side. This process continues until the last batch includes the vote of the user with ID N-1.

For each batch, the maximum number of votes for any web series needs to be recorded. The marketing team manager wants to automate this feature in their system to save time.

Write an algorithm to find the maximum number of votes for a web series in every batch.

Input Format

• The first line contains an integer N — the number of users.
• The second line contains N space-separated integers representing the IDs of the web series voted on by the users.
• The last line contains an integer K — the size of each batch.

Output Format

• Print space-separated integers representing the maximum number of votes for any web series in each batch.

Constraints

• 1 <= K <= N <= 1000
• -10^6 <= wsID[i] <= 10^6 where ( i = 0 to N-1 )

Sample Input

6
20 10 20 16 40 40
3

Sample Output

2 1 1 2

Explanation

• In the first batch [20, 10, 20], the web series with ID 20 is voted on by a maximum of 2 users.
• In the second batch ([10, 20, 16]), each web series is voted on by only 1 user.
• In the third batch ([20, 16, 40]), each web series is voted on by only 1 user.
• In the fourth batch ([16, 40, 40]), the web series with ID 40 is voted on by a maximum of 2 users.

Thus, the output is [2, 1, 1, 2].