Weighted Random Sampling Data Structures

What's being tested

You must design a dynamic data structure that supports insert, delete, and getRandom where getRandom returns items proportional to their weight. Interviewers probe your knowledge of hybrid array+map layouts, prefix-sum indexing, update/search complexity tradeoffs, and numeric robustness under updates.

Patterns & templates

• hashmap+array hybrid — store items in an array for indexable operations and a hashmap for index lookup; swap-with-last for O(1) delete.
• prefix-sum array with binary search — maintain cumulative weights; sample by generating r in [0,total) and binary-search O(log n) per sample.
• Fenwick tree (Binary Indexed Tree) — supports point updates and prefix-sum queries in O(log n); use for frequent weight changes.
• Alias method — preprocess in O(n) to enable O(1) sampling; good when samples >> updates but costly for frequent inserts/deletes.
• For mostly-read, infrequent-write workloads: rebuild prefix/alias lazily (batch updates) to amortize costs.
• Track total weight explicitly; for sampling use uniform rand() scaled to total to avoid bias.
• Use int64 or double carefully; avoid cumulative rounding by using integer weights when possible, or renormalize periodically.
• Complexity shorthand: insert/delete amortized O(1) with array+map, sampling O(log n) with Fenwick/prefix, O(1) with alias after rebuild.

Common pitfalls

Pitfall: Treating floating cumulative sums as exact — leads to off-by-one or bias; prefer integer weights or careful eps handling.

Pitfall: Forgetting to update both array and tree/map on swap-delete — leaves stale indices and corrupts sampling.

Pitfall: Choosing alias method without asking update frequency — great for static weights but expensive for dynamic workloads.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.