Compute sliding window sums by tag

Q: Compute sliding window sums by tag

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Datadog.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Datadog during technical interviews.

Question

##### 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.

PracHub · Accepted Answer

def sliding_window_sums_by_tag(datapoints, tag, k):
    # Filter datapoints containing the tag, keep original index for stable tie-breaking
    filtered = []
    for idx, dp in enumerate(datapoints):
        tags = dp.get("tags", [])
        if isinstance(tags, (list, tuple)) and tag in tags:
            ts = dp.get("ts")
            val = dp.get("value")
            filtered.append((ts, val, idx))

# Edge cases
    if k <= 0:
        return []

# Sort by timestamp ascending; break ties by original index to preserve input order
    filtered.sort(key=lambda x: (x[0], x[2]))

values = [v for _, v, _ in filtered]
    m = len(values)
    if k > m:
        return []

# Sliding window sums
    res = []
    window_sum = sum(values[:k])
    res.append(window_sum)
    for i in range(k, m):
        window_sum += values[i] - values[i - k]
        res.append(window_sum)

return res

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.

Quick Overview

Hints

Quick Overview

Compute sliding window sums by tag

Constraints

Solution

Explanation

Hints