DSA · Engineering Foundry challenge level: Foundation

Bounded Streaming Frequency Index

Design an in-memory index that answers frequency queries over a moving event window while controlling memory growth.

All challengesSuggested practice time: 40 minutes

Original prompt

What you are building

Design the algorithm and interfaces for a service component that receives timestamped string keys and answers how many times a key appeared during the most recent W seconds. Events arrive in timestamp order. Explain the data structures, update and query operations, cleanup strategy, and tests you would use before implementation.

Engineering Foundry originalNo company association

Deliverables

A precise interface for recording events and querying a key.
The core algorithm and supporting data structures.
Time and space complexity for updates, queries, and cleanup.
Edge cases involving window boundaries, idle keys, and bursts.
A focused test plan with representative sequences.

Constraints

Use process memory only; persistence is outside this exercise.
Do not assume a fixed key vocabulary.
A query at time T counts events with timestamps in the interval (T - W, T].
Favor correctness and bounded cleanup work over clever compression.

Success criteria

Window-boundary semantics are unambiguous.
Expired data can be reclaimed without scanning every known key per event.
Complexity claims match the proposed operations.
Tests demonstrate empty, boundary, burst, and long-idle behavior.

Suggested workflow

Write the time-window invariant in one sentence.
Sketch the update and query interfaces.
Choose a representation and trace a small event sequence.
Analyze cleanup cost and memory growth.
Write boundary-focused tests before refining the explanation.

Attempt before reveal

Build your deliverable independently.

Use the prompt, constraints, and workflow first. Guidance offers considerations and questions - not a canonical solution.

Reveal guidanceDirections and questions to test

One direction to explore

Consider whether exact per-event timestamps are necessary or whether fixed-duration buckets preserve the required semantics.
Separate the global expiry order from per-key counts so cleanup does not scan inactive keys.
Test the exact instant an event leaves the open-left window boundary.

Reveal common mistakesFailure patterns worth checking

Keeping every event forever and calling cleanup an implementation detail.
Using a full-key scan on every record operation.
Leaving the inclusive and exclusive window boundaries undefined.
Claiming constant memory without relating it to event rate and window length.

Reveal stretch goalsOptional ways to extend the deliverable

Discuss out-of-order events with bounded lateness.
Explore approximate counting when exact memory cost is too high.

Optional solution worksheet

Prepare your approach for discussion.

Capture your reasoning, then copy a plain-text summary you control.

Session only - not saved.Refreshing or leaving this page clears every worksheet field and self-review choice. Nothing is uploaded or officially submitted.

Approach summary

Key decision

Important tradeoff

Failure mode or edge case

Validation or testing plan

Reflection

Optional solution URLThis link remains in the current browser session and is included only if you copy the summary.

Nothing is sent when you copy.

Optional community discussion

Compare reasoning, not rankings.

Discuss this challenge in the Engineering Foundry community if you choose. Share your own work, explain assumptions, critique ideas rather than people, and remove confidential or proprietary material.

Discuss this challenge

Loading Engineering Foundry…

DSA · Engineering Foundry challenge level: Foundation

Bounded Streaming Frequency Index

Design an in-memory index that answers frequency queries over a moving event window while controlling memory growth.

All challengesSuggested practice time: 40 minutes

Original prompt

What you are building

Engineering Foundry originalNo company association

Deliverables

A precise interface for recording events and querying a key.
The core algorithm and supporting data structures.
Time and space complexity for updates, queries, and cleanup.
Edge cases involving window boundaries, idle keys, and bursts.
A focused test plan with representative sequences.

Constraints

Use process memory only; persistence is outside this exercise.
Do not assume a fixed key vocabulary.
A query at time T counts events with timestamps in the interval (T - W, T].
Favor correctness and bounded cleanup work over clever compression.

Success criteria

Window-boundary semantics are unambiguous.
Expired data can be reclaimed without scanning every known key per event.
Complexity claims match the proposed operations.
Tests demonstrate empty, boundary, burst, and long-idle behavior.

Suggested workflow

Write the time-window invariant in one sentence.
Sketch the update and query interfaces.
Choose a representation and trace a small event sequence.
Analyze cleanup cost and memory growth.
Write boundary-focused tests before refining the explanation.

Attempt before reveal

Build your deliverable independently.

Use the prompt, constraints, and workflow first. Guidance offers considerations and questions - not a canonical solution.

Reveal guidanceDirections and questions to test

One direction to explore

Consider whether exact per-event timestamps are necessary or whether fixed-duration buckets preserve the required semantics.
Separate the global expiry order from per-key counts so cleanup does not scan inactive keys.
Test the exact instant an event leaves the open-left window boundary.

Reveal common mistakesFailure patterns worth checking

Keeping every event forever and calling cleanup an implementation detail.
Using a full-key scan on every record operation.
Leaving the inclusive and exclusive window boundaries undefined.
Claiming constant memory without relating it to event rate and window length.

Reveal stretch goalsOptional ways to extend the deliverable

Discuss out-of-order events with bounded lateness.
Explore approximate counting when exact memory cost is too high.

Optional solution worksheet

Prepare your approach for discussion.

Capture your reasoning, then copy a plain-text summary you control.

Session only - not saved.Refreshing or leaving this page clears every worksheet field and self-review choice. Nothing is uploaded or officially submitted.

Approach summary

Key decision

Important tradeoff

Failure mode or edge case

Validation or testing plan

Reflection

Optional solution URLThis link remains in the current browser session and is included only if you copy the summary.

Nothing is sent when you copy.

Optional community discussion

Compare reasoning, not rankings.

Discuss this challenge

Bounded Streaming Frequency Index

What you are building

Deliverables

Constraints

Success criteria

Suggested workflow

Build your deliverable independently.

One direction to explore

DSA deliverable self-review

Prepare your approach for discussion.

Compare reasoning, not rankings.

Bounded Streaming Frequency Index

What you are building

Deliverables

Constraints

Success criteria

Suggested workflow

Build your deliverable independently.

One direction to explore

DSA deliverable self-review

Prepare your approach for discussion.

Compare reasoning, not rankings.