Amazon·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

Amazon SWE interview with a pretty gnarly design question around a weighted random sampler with time-based expiry. One question, but it had enough moving parts to keep me busy for the whole session.

Questions Asked (1)

You have a weighted random generator with add(value, weight) and next(). Extend it to support addWithExpiry(value, weight, expireAfterMs) so that each entry automatically stops contributing to the distribution after a given number of milliseconds. Walk through your data structure choices and how next() handles expired entries.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I went straight for a min-heap keyed on expiry timestamps, which felt right, but then stumbled when they pushed on what next() actually does when it pops an expired entry mid-sample.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a data structure that supports efficient weighted sampling and expiration. Walk through the design, focusing on how next() handles expired entries, and discuss trade-offs between different approaches.

Pro tip: Mention that you would use a min-heap for expiration and a Fenwick tree for weighted sampling, and discuss how to handle lazy deletion to avoid O(n) removals. This shows you understand both algorithmic efficiency and practical implementation details.

1. Clarify requirements and constraints

Ask about expected frequency of addWithExpiry vs next, whether weights can change, and if expired entries need immediate removal or can be lazily cleaned.

2. Choose core data structures

Propose a Fenwick tree (or segment tree) for cumulative weights to enable O(log n) sampling, and a min-heap keyed by expiration time for efficient expiry tracking.

3. Design addWithExpiry

Insert the value into the Fenwick tree with its weight, and push (expiryTime, value) onto the min-heap. Store a mapping from value to its current weight and expiry for updates.

4. Design next() with lazy expiration

Before sampling, pop all expired entries from the heap, and for each, remove its weight from the Fenwick tree (set to 0). Then sample a random number in [0, totalWeight) and use the Fenwick tree to find the corresponding value.

5. Analyze complexity and trade-offs

Discuss time complexity: O(log n) for addWithExpiry and next (amortized for expiration cleanup). Mention alternative approaches like using a balanced BST or a segment tree, and trade-offs in memory and implementation complexity.

Key Points to Mention

Use a Fenwick tree (Binary Indexed Tree) for O(log n) weighted sampling and updates.
Use a min-heap to track expiration times and lazily remove expired entries.
Maintain a hash map from value to its weight and expiry for efficient updates/removals.
In next(), first clean up expired entries by popping from the heap and updating the Fenwick tree.
Sampling: generate a random number in [0, totalWeight) and find the smallest index with cumulative weight > random number.
Discuss trade-offs: lazy deletion vs eager deletion, memory overhead, and handling duplicate values.

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