Find target-heavy sliding windows
Company: Roblox
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `nums`, an integer `target`, and a fixed window size `k`, solve the following two tasks:
1. Return all contiguous subarrays of length `k` that contain at least one occurrence of `target`.
2. Among all contiguous subarrays of length `k`, return the first window that contains the maximum number of occurrences of `target`.
If no length-`k` window contains `target`, return an empty list for part (1) and indicate that no valid window exists for part (2).
Aim for an efficient sliding-window solution.
Quick Answer: This question evaluates array manipulation, counting and efficient algorithm design—focusing on the sliding-window technique for detecting and quantifying target occurrences in fixed-size subarrays, and it measures algorithmic efficiency and complexity reasoning.
Given nums, target, and window size k, return [all_windows_with_target, first_window_with_max_target_count]. If no length-k window contains target, return [[], None].
Constraints
- Windows are contiguous and have length k
- The best window is the earliest one among ties
Examples
Input: ([1, 2, 3, 2, 2], 2, 3)
Expected Output: [[[1, 2, 3], [2, 3, 2], [3, 2, 2]], [2, 3, 2]]
Input: ([1, 1, 1], 2, 2)
Expected Output: [[], None]
Input: ([5], 5, 1)
Expected Output: [[[5]], [5]]
Input: ([1, 2], 1, 3)
Expected Output: [[], None]
Hints
- Maintain the count of target in the current window as it slides by one position.