Katkat
Back

Find target-heavy sliding windows

RobloxMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to implement an efficient sliding window algorithm to analyze frequency-based patterns within a data stream or array.

Problem Statement

You are monitoring game telemetry data represented as an array of integers events, where each integer represents an event ID. Given an integer target_id and an integer k, you need to identify all subarrays of size k where the frequency of target_id is at least threshold.

Write a function find_heavy_windows(events, target_id, k, threshold) that returns a list of starting indices of all such valid windows.

Constraints

  • 1 <= len(events) <= 10^6
  • 1 <= k <= len(events)
  • `0 <= target_id, events[i] Valid (index 0)
  • Window 2: [2, 1, 1] (count of 1s is 2) -> Valid (index 1)
  • Window 3: [1, 1, 3] (count of 1s is 2) -> Valid (index 2) Output: [0, 1, 2]

Example 2: Input: events = [4, 4, 4, 5], target_id = 4, k = 2, threshold = 2

  • Window 1: [4, 4] (count is 2) -> Valid (index 0)
  • Window 2: [4, 4] (count is 2) -> Valid (index 1)
  • Window 3: [4, 5] (count is 1) -> Invalid Output: [0, 1]

Implementation

def find_heavy_windows(events, target_id, k, threshold):
    # Your code here

Hints

Hint 1

Instead of counting from scratch for every window of size k, use a sliding window to update the count in O(1) time as you move from one index to the next.

Hint 2

Maintain a variable to keep track of the current count of `target_id` inside the window, incrementing it when the new element entering the window matches `target_id` and decrementing it when the element leaving matches.

Hint 3

Be careful with the bounds of your loop to ensure you process exactly `len(events) - k + 1` windows.

Follow-up questions

  • How would you modify your solution if the target criteria changed from a single `target_id` to a set of multiple target IDs that must all be present?
  • If the memory footprint of the `events` array was massive, how could you handle this if it didn't fit entirely in RAM (e.g., processing via a stream)?
  • What is the time and space complexity of your solution, and can you optimize the space complexity further?