Akuna Capital·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Akuna Capital data scientist interview with a meaty system design question about streaming statistics. The sliding window twist at the end is what actually tripped me up, not the basic version.

Questions Asked (1)

Design a data structure that tracks max, mean, and mode over an unbounded integer stream. Estimate its memory footprint assuming values fall between 1 and 1001. Then extend it to support a sliding window of the last k elements only.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

Started fine with the basic version.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: unbounded stream, integer values between 1 and 1001, and need for max, mean, and mode. For the unbounded case, propose a fixed-size array of counts (size 1001) to track frequencies, along with running sum and count for mean, and current max. For the sliding window, discuss using a queue to maintain order and a frequency array with a max-heap or balanced BST to efficiently update mode and max as elements expire.

Pro tip: Explicitly state the memory footprint: 1001 integers for counts (about 4KB) plus a few scalars, which is negligible. For the sliding window, emphasize the trade-off between using a heap (O(log n) updates) versus a balanced BST (O(log n) updates but easier to remove arbitrary elements).

1. Clarify requirements and constraints

Confirm that the stream is unbounded, values are integers in [1, 1001], and we need max, mean, and mode. Ask if updates need to be in real-time and if the sliding window size k is fixed.

2. Design for unbounded stream

Use a frequency array of size 1001 to count occurrences. Maintain running sum and count for mean, and track current max by comparing with new elements. For mode, track the current mode and its frequency, updating when a count exceeds the max frequency.

3. Estimate memory footprint

The frequency array takes 1001 * 4 bytes ≈ 4KB. Additional scalars (sum, count, max, mode, mode_freq) take constant space. Total memory is O(1001) ≈ 4KB, which is very small.

4. Extend to sliding window of last k elements

Use a queue to maintain the window. When adding a new element, increment its count and enqueue; when the window exceeds k, dequeue the oldest element and decrement its count. For max, use a monotonic deque or a max-heap with lazy deletion. For mode, maintain a max-heap of (frequency, value) or a balanced BST keyed by frequency, updating as counts change.

5. Analyze time and space complexity

For unbounded: O(1) per update, O(1) query. For sliding window: O(log n) per update with heap/BST, O(1) for max with deque, O(1) for mean. Space: O(k) for queue plus O(1001) for counts.

Key Points to Mention

Fixed range of values allows using a frequency array instead of a hash map, saving memory and time.
For mode, tie-breaking rules (e.g., smallest value) should be defined.
Sliding window requires efficient removal of old elements; a heap with lazy deletion or a balanced BST can handle this.
Max in sliding window can be maintained in O(1) amortized time using a monotonic deque.
Mean can be updated in O(1) by maintaining running sum and count, even with sliding window.
Memory footprint is dominated by the frequency array (4KB) and the window queue (O(k)), which is very efficient.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.