Question Bank
Sliding Window Essentials
Difficulty: Medium
Five mid-level prompts on fixed and variable sliding windows: max sum, longest substring without repeats, and a window-shrink invariant. Mixes implementation and trace.
Sliding Window Essentials
Five mid-level prompts on fixed and variable sliding windows: max sum, longest substring without repeats, and a window-shrink invariant. Mixes implementation and trace.
621 views
6
Implement maxSubarraySum(arr, k) returning the largest sum of any contiguous subarray of length k. Aim for O(n) time and O(1) extra space.
Examples
Example 1:
Input: arr = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: The first window [2, 1, 5] sums to 8. Slide one step: add 1, drop 2, sum = 7. Continue sliding: 7, 9, 6. Track the running max. The window [5, 1, 3] gives the maximum 9.Implement longestUniqueSubstring(s) returning the length of the longest substring with all distinct characters. Use a variable-size sliding window with a hash map of last-seen indices.
Examples
Example 1:
Input: s = 'abcabcbb'
Output: 3
Explanation: Variable window with a last-seen index map. When the current character was last seen inside the window, jump left to one past that earlier index. The longest distinct-character window has length 3 (e.g. 'abc').Example 2:
Input: s = 'bbbbb'
Output: 1
Explanation: Every character repeats immediately, so the window can never grow past 1.Trace this snippet step by step for arr = [1, 1, 1, 1] and k = 2. List every value of windowSum and best after each iteration of the second loop.
Examples
Example 1:
Input: arr = [1, 1, 1, 1], k = 2
Output: 2
Explanation: After priming, windowSum = 2 and best = 2. Iter i = 2: windowSum = 2 + 1 - 1 = 2, best = 2. Iter i = 3: windowSum = 2 + 1 - 1 = 2, best = 2. The function returns 2.Compare fixed-size and variable-size sliding windows. Give one canonical example of each and describe the loop invariant that decides when to shrink the window.
Spot the bug. This function should return the smallest contiguous subarray length whose sum is >= target, or 0 if none exists. The current version returns wrong values when no subarray qualifies.
Examples
Example 1:
Input: target = 7, arr = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: The window [4, 3] sums to 7 with length 2. The shrink loop is correct; the algorithm is O(n) amortized because each element enters and leaves the window at most once.Example 2:
Input: target = 100, arr = [1, 2, 3]
Output (buggy version): Infinity
Output (fixed version): 0
Explanation: When no subarray meets the target, best stays Infinity. The fix returns best === Infinity ? 0 : best so the documented 'no answer' sentinel is honored.