Amazon SDE-1/2/SDE-Intern OA Questions | Amazon OA Questions | Kumar K | August 2026 |Set 242

Question

Comments

import java.util.*;

public class InventoryOptimizerPureO5 {
    static class Interval {
        int start, end, value;

        Interval(int start, int end, int value) {
            this.start = start;
            this.end = end;
            this.value = value;
        }
    }

    public static int minCostO1(int[] quality) {
        if (quality == null || quality.length == 0) return 0;

        List<Interval> intervals = new ArrayList<>();
        // Maps a quality value to its specific Interval object in the list
        Map<Integer, Interval> valueToIntervalMap = new HashMap<>();
        Map<Integer, Integer> freq = new HashMap<>();

        // Single pass: O(n) time complexity
        for (int i = 0; i < quality.length; i++) {
            int val = quality[i];
            freq.put(val, freq.getOrDefault(val, 0) + 1);

            if (!valueToIntervalMap.containsKey(val)) {
                // First time seeing this value.
                // Since 'i' is strictly increasing, intervals are automatically sorted by 'start'!
                Interval newInterval = new Interval(i, i, val);
                intervals.add(newInterval);
                valueToIntervalMap.put(val, newInterval);
            } else {
                // Seen before: Update the end index directly in the existing interval object
                valueToIntervalMap.get(val).end = i;
            }
        }

        // Line sweep to merge overlapping neighborhoods: O(U) time where U <= n
        int totalCost = 0;
        int currentEnd = intervals.get(0).end;
        
        List<Integer> currentGroupVals = new ArrayList<>();
        currentGroupVals.add(intervals.get(0).value);

        for (int i = 1; i < intervals.size(); i++) {
            Interval next = intervals.get(i);

            // Since intervals are naturally sorted by 'start', this check remains 100% correct
            if (next.start <= currentEnd) {
                currentEnd = Math.max(currentEnd, next.end);
                currentGroupVals.add(next.value);
            } else {
                totalCost += calculateGroupCost(currentGroupVals, freq);

                currentEnd = next.end;
                currentGroupVals.clear();
                currentGroupVals.add(next.value);
            }
        }

        totalCost += calculateGroupCost(currentGroupVals, freq);

        return totalCost;
    }

    private static int calculateGroupCost(List<Integer> groupVals, Map<Integer, Integer> freq) {
        int groupTotal = 0;
        int groupMax = 0;
        for (int v : groupVals) {
            int f = freq.get(v);
            groupTotal += f;
            groupMax = Math.max(groupMax, f);
        }
        return groupTotal - groupMax;
    }
}

Answer 1

import java.util.*;

public class InventoryOptimizerPureO5 {
    static class Interval {
        int start, end, value;

        Interval(int start, int end, int value) {
            this.start = start;
            this.end = end;
            this.value = value;
        }
    }

    public static int minCostO1(int[] quality) {
        if (quality == null || quality.length == 0) return 0;

        List<Interval> intervals = new ArrayList<>();
        // Maps a quality value to its specific Interval object in the list
        Map<Integer, Interval> valueToIntervalMap = new HashMap<>();
        Map<Integer, Integer> freq = new HashMap<>();

        // Single pass: O(n) time complexity
        for (int i = 0; i < quality.length; i++) {
            int val = quality[i];
            freq.put(val, freq.getOrDefault(val, 0) + 1);

            if (!valueToIntervalMap.containsKey(val)) {
                // First time seeing this value.
                // Since 'i' is strictly increasing, intervals are automatically sorted by 'start'!
                Interval newInterval = new Interval(i, i, val);
                intervals.add(newInterval);
                valueToIntervalMap.put(val, newInterval);
            } else {
                // Seen before: Update the end index directly in the existing interval object
                valueToIntervalMap.get(val).end = i;
            }
        }

        // Line sweep to merge overlapping neighborhoods: O(U) time where U <= n
        int totalCost = 0;
        int currentEnd = intervals.get(0).end;
        
        List<Integer> currentGroupVals = new ArrayList<>();
        currentGroupVals.add(intervals.get(0).value);

        for (int i = 1; i < intervals.size(); i++) {
            Interval next = intervals.get(i);

            // Since intervals are naturally sorted by 'start', this check remains 100% correct
            if (next.start <= currentEnd) {
                currentEnd = Math.max(currentEnd, next.end);
                currentGroupVals.add(next.value);
            } else {
                totalCost += calculateGroupCost(currentGroupVals, freq);

                currentEnd = next.end;
                currentGroupVals.clear();
                currentGroupVals.add(next.value);
            }
        }

        totalCost += calculateGroupCost(currentGroupVals, freq);

        return totalCost;
    }

    private static int calculateGroupCost(List<Integer> groupVals, Map<Integer, Integer> freq) {
        int groupTotal = 0;
        int groupMax = 0;
        for (int v : groupVals) {
            int f = freq.get(v);
            groupTotal += f;
            groupMax = Math.max(groupMax, f);
        }
        return groupTotal - groupMax;
    }
}