Sliding Window: Target Containment and Most-Repeated Window

MLE onsite coding round: given a list of integers, a target value, and a fixed window size, (1) return every sliding window that contains the target, then (2) find the first window that maximizes the count of the target. Tests fluency with sliding-window + hashmap and crisp boundary handling. Problem Overview You are given an array of integers, a window size k, and a target value. The interview starts with finding every length-k sliding window that contains the target at least once, then asks for the length-k window where the target appears the most times. Part 1: Windows That Contain the Target Problem Statement Return the start indices of every length-k contiguous subarray of nums that contains target at least once. Start indices should be returned in increasing order. from typing import List def windows_containing_target( nums: List[int], k: int, target: int, ) -> List[int]: """ Return the start index of every length-k window that contains `target` at least once. """ pass Example nums = [1, 3, 2, 3, 4, 3, 5] k = 3 target = 3 windows_containing_target(nums, k, target) # [0, 1, 2, 3, 4] Every length-3 window happens to contain a 3, so all five start indices are returned. nums = [1, 2, 4, 5, 3, 6, 7, 8] k = 3 target = 3 windows_containing_target(nums, k, target) # [2, 3, 4] The 3 is at index 4, so the length-3 windows that include it start at indices 2, 3, and 4. Solution Maintain a running count of how many times target appears in the current window. Slide the window one step at a time: add the entering element to the count, drop the leaving element, and record the start index whenever the count is non-zero. from typing import List def windows_containing_target( nums: List[int], k: int, target: int, ) -> List[int]: n = len(nums) if k <= 0 or k > n: return [] count = sum(1 for x in nums[:k] if x == target) result: List[int] = [] if count > 0: result.append(0) for start in range(1, n - k + 1): if nums[start - 1] == target: count -= 1 if nums[start + k - 1] == target: count += 1 if count > 0: result.append(start) return result Complexity: Time: O(n) — one pass after the initial window seed. Space: O(1) extra, plus O(n) for the output in the worst case. Part 2: First Window With the Most Repeats Problem Statement Return the start index of the length-k window that contains target the most times. If two windows are tied, return the smaller start index. If the array is shorter than k, return -1. from typing import List def best_window_start( nums: List[int], k: int, target: int, ) -> int: """ Return the start index of the length-k window with the highest count of `target`. Break ties by returning the earliest such start. """ pass Example nums = [3, 1, 3, 2, 3, 3, 4, 3] k = 4 target = 3 best_window_start(nums, k, target) # 2 Counts of 3 per window: Start Window Count 0 [3, 1, 3, 2] 2 1 [1, 3, 2, 3] 2 2 [3, 2, 3, 3] 3 3 [2, 3, 3, 4] 2 4 [3, 3, 4, 3] 3 The maximum count is 3, first hit at start index 2. Solution Reuse the running-count slide from Part 1. Track the best start and best count separately, and only update the best when the current count is strictly greater — that keeps the earliest tie. from typing import List def best_window_start( nums: List[int], k: int, target: int, ) -> int: n = len(nums) if k <= 0 or k > n: return -1 count = sum(1 for x in nums[:k] if x == target) best_start = 0 best_count = count for start in range(1, n - k + 1): if nums[start - 1] == target: count -= 1 if nums[start + k - 1] == target: count += 1 if count > best_count: best_count = count best_start = start return best_start Complexity: Time: O(n) — one pass with O(1) work per slide. Space: O(1). Why Not Prefix Sum? A prefix-count array pref[i] = number of targets in nums[:i] would also give O(n) time, but it allocates an extra O(n) array and adds an off-by-one when reading pref[start + k] - pref[start]. The running-count slide is simpler, hits O(1) extra space, and matches what the interviewer is usually looking for after Part 1. Notes Part 1 alone ("return every length-k window that contains the target") has shown up as a deliberately easy phone-screen warm-up, separate from the harder most-repeated-window follow-up. Clarify whether the interviewer wants every qualifying window or only the single best one before coding. Edge Cases k > len(nums) — no valid window, return [] for Part 1 and -1 for Part 2. target never appears — Part 1 returns []; Part 2 returns 0 (the first window is tied at count 0). All elements equal target — Part 1 returns every start; Part 2 returns 0 since all counts are tied at k. k == 1 — Part 1 returns every index where nums[i] == target; Part 2 returns the first such index, or 0 if target is absent. k == len(nums) — exactly one window, so both parts collapse to a single check. Test Cases def test_windows_containing_target_basic(): assert windows_containing_target([1, 2, 4, 5, 3, 6, 7, 8], 3, 3) == [2, 3, 4] def test_windows_containing_target_all_windows(): assert windows_containing_target([1, 3, 2, 3, 4, 3, 5], 3, 3) == [0, 1, 2, 3, 4] def test_windows_containing_target_missing(): assert windows_containing_target([1, 2, 4, 5], 2, 3) == [] def test_windows_containing_target_window_too_large(): assert windows_containing_target([1, 3], 5, 3) == [] def test_best_window_start_basic(): assert best_window_start([3, 1, 3, 2, 3, 3, 4, 3], 4, 3) == 2 def test_best_window_start_ties_pick_earliest(): # Both windows have one 3; should return the earliest start. assert best_window_start([3, 1, 1, 3, 1, 1], 3, 3) == 0 def test_best_window_start_target_absent(): # All counts tie at 0; earliest start is 0. assert best_window_start([1, 2, 4, 5], 2, 3) == 0 def test_best_window_start_window_too_large(): assert best_window_start([1, 3], 5, 3) == -1 def test_best_window_start_k_equals_length(): assert best_window_start([3, 1, 3], 3, 3) == 0