Quick Overview

This question evaluates understanding of sequence processing, sliding-window aggregation, filtering by tag, and efficient state management in tagged time-series or event data, testing algorithmic efficiency and correctness.

Compute sliding window sums by tag

Company: Datadog

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question Given a list of datapoints where each datapoint has tags, a timestamp, and a value, write a function that, for a specified tag t and window size k, returns the sums of every consecutive window of size k over the datapoints that contain tag t.

Overview: This question evaluates understanding of sequence processing, sliding-window aggregation, filtering by tag, and efficient state management in tagged time-series or event data, testing algorithmic efficiency and correctness.

You are given a list of datapoints, each with fields: tags (list of strings), ts (integer timestamp), and value (integer). Implement sliding_window_sums_by_tag(datapoints, tag, k) that: (1) selects only datapoints whose tags contain the exact string tag, (2) orders the selected datapoints by ascending ts and preserves original input order when ts is equal, and (3) returns a list of sums of every consecutive window of size k over the ordered values. If fewer than k datapoints match, return an empty list. The input list may be in any order.

Constraints

  • 1 <= n <= 200000, where n is the number of datapoints
  • Each datapoint is a dict with keys: 'tags' (list[str]), 'ts' (int), 'value' (int)
  • Tag strings are non-empty; tags list size 0..50
  • Timestamps ts are integers and may repeat
  • Values are integers in range [-1e9, 1e9]
  • 1 <= k <= n; if the number of matching datapoints m < k, return []
  • Order matching datapoints by ascending ts; if ts ties, preserve original input order
  • Input datapoints are not guaranteed to be pre-sorted

Hints

  1. First filter datapoints whose tags contain the target tag.
  2. Sort the filtered list by timestamp ascending; preserve input order for equal timestamps.
  3. Maintain a running sum for the sliding window and update it in O(1) per step.

Loading coding console...

Show the approach

Approach

Filter datapoints to those containing the target tag, then sort by timestamp ascending while preserving input order for equal timestamps. Extract the values and compute the sums of every consecutive window of size k using a sliding window: initialize with the first k values, then for each step add the entering value and subtract the leaving value. If fewer than k datapoints match, return an empty list.

Time complexity:
O(m log m), where m is the number of matching datapoints
Space complexity:
O(m)