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.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

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

Design a weighted random value generator

Quick Overview

This question evaluates understanding of weighted random sampling, probability-proportional selection, data structures for aggregating weights, and API design with time-based expiration semantics.

Design a weighted random value generator

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Weighted random value generator Design a generic component that stores values with integer weights and can return a random value with probability proportional to its weight. ### Requirements - Support adding a value with a weight: - `add(value: T, weight: Int)` - Support returning a random value: - `pick(): T` (name can vary) - If the stored pairs are `[(1,1), (2,1), (5,3)]`, then probabilities are: - `1`: 20%, `2`: 20%, `5`: 60% - If you then add `(3,5)`, probabilities become: - `1`: 10%, `2`: 10%, `5`: 30%, `3`: 50% ### Focus Prioritize **clarity, maintainability, and extensibility** over micro-optimizing performance. ### Follow-up Add an API that supports expiration: - `addWithExpiry(value: T, weight: Int, expireAfterMs: Int)` - After the expiration time elapses, that added weight contribution should no longer affect `pick()`. ### Clarifications to address (state assumptions) - Whether `weight` is always positive. - Whether adding an existing `value` merges weight or stores multiple entries. - Expected behavior when there are no active (non-expired) entries.

Quick Answer: This question evaluates understanding of weighted random sampling, probability-proportional selection, data structures for aggregating weights, and API design with time-based expiration semantics.

Simulate a weighted random generator using explicit 1-indexed tickets instead of randomness; also support expiring entries with logical time.

Constraints

pick operations provide a ticket instead of calling randomness.
ticket is normalized into the active total weight.
add_expiry uses the current logical time plus ttl as its expiration.

Examples

Input: ([["add",1,1],["add",2,1],["add",5,3],["pick",1],["pick",3],["pick",5]],)

Expected Output: [1, 5, 5]

Explanation: Tickets map deterministically across cumulative weights.

Input: ([["pick",1],["add","a",2],["add_expiry","b",3,10],["pick",4],["tick",10],["pick",3]],)

Expected Output: ['EMPTY', 'b', 'a']

Explanation: Expired entries stop contributing after their expiry time.

Input: ([["add","x",0],["pick",1]],)

Expected Output: ['EMPTY']

Explanation: No active positive weight returns EMPTY.

Hints

Maintain entries in insertion order.
For a pick, scan cumulative active weights until the ticket falls into a range.

Last updated: Jun 27, 2026

Loading coding console...