Microsoft

## Question 1: Parity-Balanced Subarray Concepts:** Prefix Sum, Hash Map Problem Statement:** You are given an array of integers `nums`. A contiguous subarray is considered "parity-balanced" if the sum of the elements located at even indices within the subarray is exactly equal to the sum of the elements located at odd indices within the subarray (using 0-based indexing relative to the start of the subarray). Return the length of the longest parity-balanced contiguous subarray. If no such subarray exists, return `0`. Test Case:** *Input:** `nums = [2, 4, 3, 1, 2, 5]` *Output:** `4` *(The subarray `[4, 3, 1, 2]` is parity-balanced: even indices sum = 4 + 1 = 5, odd indices sum = 3 + 2 = 5)* - ## Question 2: Alternating Sequence with Overrides Concepts:** Sliding Window, State Tracking Problem Statement:** You are given an array of positive integers `nums` and an integer `k`. An array is perfectly alternating if the parity (even/odd) of its elements strictly alternates. You have the ability to override the parity of at most `k` elements in the array (conceptually changing an even number to an odd number, or vice versa). Return the maximum length of a contiguous subarray that can be made perfectly alternating using at most `k` overrides. Test Case:** *Input:** `nums = [2, 4, 1, 3, 4, 6]`, `k = 1` *Output:** `4` *(By overriding the parity of the element `3` to be even, the subarray `[4, 1, 3, 4]` becomes [even, odd, even, even] -> [even, odd, even, odd] which strictly alternates)* - ## Question 3: Maximum Dependency Cost Concepts:** Sliding Window, Monotonic Deque Problem Statement:** You are given two arrays of integers of length `n`: `compile_time` and `dependency_factor`, along with an integer `k`. You must select a contiguous subarray of exactly length `k`. The "execution cost" of a subarray is defined as the sum of the `compile_time` values in that subarray multiplied by the minimum `dependency_factor` value in that same subarray. Return the maximum possible execution cost among all contiguous subarrays of length `k`. Test Case:** *Input:** `compile_time = [2, 3, 1, 5, 4]`, `dependency_factor = [3, 2, 5, 4, 1]`, `k = 2` *Output:** `24` *(Choosing the subarray starting at index 2 gives `compile_time` [1, 5] and `dependency_factor` [5, 4]. Sum of compile time = 6, minimum dependency = 4. Cost = 6 * 4 = 24)*