Katkat
Back

Convert Samples into Event Intervals

AnthropicMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to process sequential data, apply run-length encoding concepts, and implement filtering logic based on temporal constraints.

Problem Statement

You are given a list of samples representing the state of a system at sequential time points. Each sample is a tuple (timestamp, state). A state is considered 'active' if it is represented by the value 1, and 'inactive' if it is 0.

Your task is to identify all continuous intervals of 1s that last for at least k time units.

An interval is defined as starting at the first occurrence of 1 and ending at the last occurrence of 1 before the state changes to 0 or the trace ends. The duration of an interval starting at t_start and ending at t_end is calculated as t_end - t_start. If an interval has only one sample (where t_start == t_end), its duration is 0.

Function Signature

def get_active_intervals(samples: list[tuple[int, int]], k: int) -> list[tuple[int, int]]:
    # samples is sorted by timestamp
    # returns a list of (start_timestamp, end_timestamp)

Constraints

  • samples length is up to 10^5.
  • timestamps are strictly increasing integers.
  • state is either 0 or 1.

Examples

Example 1: Input: samples = [(1, 1), (2, 1), (3, 0), (4, 1), (5, 1), (6, 1)], k = 2 Output: [(1, 2), (4, 6)] Explanation: The first sequence of 1s lasts from 1 to 2 (duration 1, which is = k). Actually, the duration (2-1) is 1. If k=2, only the second interval (6-4=2) is included.

Example 2: Input: samples = [(1, 0), (5, 1)], k = 0 Output: [(5, 5)]

Edge Cases

  • Empty input list.
  • All zeros or all ones.
  • Single sample inputs.

Hints

Hint 1

Iterate through the samples and keep track of the start timestamp whenever a transition from 0 to 1 occurs.

Hint 2

When a transition from 1 to 0 occurs (or the end of the list is reached), compare the current timestamp with the stored start timestamp to check the duration.

Hint 3

Ensure your logic handles the transition case correctly, specifically the very last interval if it terminates at the end of the input list.

Follow-up questions

  • How would you modify the function if the samples are not perfectly sorted by timestamp?
  • What is the time and space complexity of your solution, and can you optimize the memory usage to O(1) extra space beyond the output?
  • If the input was a stream of millions of samples, how would you process this in a distributed environment?