Amazon OA | SDE-II

Round 1

Questions: Data analysts at Amazon are studying the trends in movies and shows popular on Prime Video in order to enhance the user experience. They have identified the best critic-rated and the best audience-rated web series presented by Integer ID Series 1 and Series 2. They also had defined the watch score of a continuous period of some days as a number of distinct series watched by a viewer during that period. Given an array watch history of size n that represents the web series watched by a viewer over a period of n days and two integers, Series 1 and Series 2 report the minimum watch score of a contiguous period of days in which both Series 1 and Series 2 have been viewed at least once. If Series 1 and Series 2 are of the same value, one occurrence during the period is sufficient.

Example: n is equal to 5, Series 1 is equal to 1, Series 2 is equal to 2. Watch history array is 1, 3, 2, 1, 4. For this, the output is 2. Return the minimum watch score which will be 2.

Test Case 1: watch_history size n = 5
watch_history = [1,2,3,5,1]
series1 = 5
series2 = 5
Output : 2

Test Case 2: watch_history size n = 6
watch_history = [1,2,2,2,5,2]
series1 = 1
series2 = 5
Output : 3

import java.util.*;

public class Solution {
    public static int getMinScore(List<Integer> watch_history, int series1, int series2) {
        // Variables to store the last positions of series1 and series2
        int lastSeries1 = -1, lastSeries2 = -1;
        int minScore = Integer.MAX_VALUE;
        
        // A map to track the count of distinct series in the current window
        Map<Integer, Integer> countMap = new HashMap<>();
        
        int left = 0; // Start of the sliding window
        
        for (int right = 0; right < watch_history.size(); right++) {
            int currentSeries = watch_history.get(right);
            
            // Update the count of the current series
            countMap.put(currentSeries, countMap.getOrDefault(currentSeries, 0) + 1);
            
            // Track the latest positions of series1 and series2
            if (currentSeries == series1) lastSeries1 = right;
            if (currentSeries == series2) lastSeries2 = right;
            
            // If both series1 and series2 have been encountered
            if (lastSeries1 != -1 && lastSeries2 != -1) {
                // Shrink the window from the left to maintain the valid subarray containing both series1 and series2
                while (lastSeries1 >= left && lastSeries2 >= left) {
                    int leftSeries = watch_history.get(left);
                    // Try to minimize the window by removing the leftmost element
                    if (countMap.get(leftSeries) == 1) {
                        countMap.remove(leftSeries);
                    } else {
                        countMap.put(leftSeries, countMap.get(leftSeries) - 1);
                    }
                    left++;
                }
                
                // Calculate the number of distinct series in the current window
                minScore = Math.min(minScore, countMap.size());
            }
        }
        
        // Return the minimum score found, or -1 if no valid subarray was found
        return (minScore == Integer.MAX_VALUE) ? -1 : minScore + 1;
    }
}