Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Amazon coding screen for a software engineer role. The main problem was a weighted random sampler with generics, which sounds straightforward until you get to the follow-up about expiring entries.

Questions Asked (2)

Design a generic weighted random generator class that supports adding values with associated weights and sampling from them with probability proportional to their weight. Implement an add method and a sampling method.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The probability math is simple enough: track cumulative weights, pick a random number in range, binary search or linear scan to find the bucket.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a solution using prefix sums and binary search for O(log n) sampling and O(1) add (or O(n) if using a list). Discuss trade-offs between different data structures and handle edge cases like zero weights and empty generator.

Pro tip: Mention that for dynamic weights, a Fenwick tree (Binary Indexed Tree) can achieve O(log n) for both add and sample, showing awareness of advanced data structures. Also, discuss how to handle floating-point precision issues in sampling.

1. Clarify Requirements

Ask about expected frequency of add vs. sample operations, whether weights can be updated or removed, and constraints on weight values (e.g., positive, zero, negative).

2. Choose Data Structure

Based on requirements, select an appropriate data structure: array with prefix sums for static weights, or Fenwick tree for dynamic weights to balance add and sample costs.

3. Implement Add Method

For array approach, append value and update total weight; for Fenwick tree, update tree and total weight. Ensure O(1) or O(log n) time.

4. Implement Sample Method

Generate a random number between 0 and total weight, then use binary search on prefix sums (or Fenwick tree query) to find the corresponding value. Ensure O(log n) time.

5. Discuss Trade-offs and Edge Cases

Compare time complexities of different approaches, handle zero weights, empty generator, and floating-point precision. Mention potential optimizations like alias method for static weights.

Key Points to Mention

Time complexity trade-offs: O(1) add + O(n) sample vs. O(n) add + O(log n) sample vs. O(log n) for both using Fenwick tree
Use of prefix sums and binary search for efficient sampling
Handling of zero weights (should never be selected) and negative weights (invalid)
Random number generation and scaling to total weight
Edge cases: empty generator, single element, all weights zero
Alternative: Alias method for O(1) sampling when weights are static

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

Extend the weighted random generator to support entries that expire after a given duration in milliseconds, via an addWithExpiry method.

System DesignTechnical Trade-offsAPI & Integrations

Author's notes

This is where things got interesting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the requirements first: expiry semantics, time source, and whether expired entries are removed lazily or eagerly. Then propose a design that integrates expiry with the existing weighted selection, discussing data structures and trade-offs. Finally, outline the API, edge cases, and testing strategy.

Pro tip: Mention that you would use a monotonic clock (e.g., System.nanoTime()) to avoid issues with system clock adjustments, and that lazy deletion with periodic cleanup is often a good balance for performance.

1. Clarify Requirements

Ask about expiry semantics: is it time-to-live from insertion, or an absolute expiration timestamp? Should expired entries be removed immediately or lazily? What happens if all entries expire?

2. Design Data Structures

Propose storing entries with expiration times in a structure that supports efficient weighted selection and expiry checks. Consider a min-heap for expirations and a list for weighted selection, or a balanced tree.

3. Integrate with Weighted Selection

Explain how to modify the weighted random selection to skip expired entries. Discuss whether to filter expired entries before selection or during selection, and the performance implications.

4. Handle Expiry Cleanup

Decide on a cleanup strategy: lazy removal during selection, periodic background cleanup, or eager removal using a timer. Discuss trade-offs in terms of complexity, memory, and CPU.

5. Define API and Edge Cases

Specify the addWithExpiry method signature, including parameters for weight and duration. Cover edge cases: zero/negative duration, weight zero, all entries expired, and thread safety.

Key Points to Mention

Use of a monotonic clock for expiry to avoid system time changes.
Data structure choices: min-heap for expirations, array for weighted selection, or a balanced BST.
Lazy vs. eager expiration and the trade-offs between memory usage and CPU overhead.
Thread safety and concurrency considerations if the generator is shared.
API design: method signature, return values, and error handling for invalid inputs.
Testing strategy: unit tests for expiry, weighted distribution, and edge cases.

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