Generate Weighted Random NFTs with Updates
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You manage k NFT types, each with a positive integer rarity weight w[i]. Implement a minter: constructor(w) builds any needed structures in O(k); mint() returns index i with probability w[i]/sum(w) using a prefix-sum structure and binary search over a random target, targeting O(log k) per mint. Follow-ups:
(
1) Support update(i, delta) to change a weight and keep mint() at O(log k); propose and justify a data structure (e.g., Fenwick or segment tree).
(
2) Support mintWithoutReplacement(t) that draws t distinct NFTs according to current weights, efficiently updating state after each draw.
(
3) Make randomness reproducible via seeding and write property-based tests to validate the distribution within tolerance and cover edge cases (zero/huge weights, all equal, k=
1).
Quick Answer: This question evaluates understanding of weighted random sampling, efficient data structures for maintaining and updating prefix sums, probabilistic reasoning about sampling distributions, and reproducible testing of randomized algorithms within the Coding & Algorithms domain.
You manage `k` NFT types, each with a non-negative integer rarity weight `w[i]`. A real minter would draw a uniform random target `r` in `[0, sum(w))` and return the index `i` whose cumulative weight interval `[prefix[i-1], prefix[i])` contains `r`, so that index `i` is chosen with probability `w[i] / sum(w)`. It must also support changing weights on the fly while keeping each draw fast.
To make this deterministic and testable, **the random draw is supplied explicitly**. Implement:
```
solution(w, ops) -> list[int]
```
- `w` is the initial list of `k` non-negative integer weights.
- `ops` is a list of operations applied in order. Each operation is a list:
- `["mint", r]` — `r` is an integer target in `[0, total)` where `total` is the current sum of weights. Return (append to output) the index `i` that **owns** target `r`: the smallest `i` such that `prefix[0] + ... + prefix[i] > r`. Equivalently, index `i` owns the half-open interval `[cum(i-1), cum(i))`. Zero-weight items own an empty interval and are never returned.
- `["update", i, delta]` — add `delta` to `w[i]` (delta may be negative; the resulting weight stays `>= 0`). This must not break the speed of later mints.
Return the list of minted indices, in the order the `mint` operations appear.
The efficient approach uses a **Fenwick (Binary Indexed) tree** (or segment tree): point-update a weight in `O(log k)`, and find the index owning a cumulative target in `O(log k)` by walking the tree bits, subtracting subtree sums as you descend. This is the mutable-weight analogue of a static prefix-sum array with binary search.
Constraints
- 1 <= k <= 10^5 (number of NFT types).
- 0 <= w[i]; at least one weight is positive at construction time.
- For each ["mint", r] op, 0 <= r < total (the current sum of weights), and total > 0.
- For each ["update", i, delta] op, 0 <= i < k and w[i] + delta >= 0.
- 0 <= len(ops) <= 2 * 10^5.
Examples
Input: ([1, 2, 3], [["mint", 0], ["mint", 1], ["mint", 2], ["mint", 3], ["mint", 5]])
Expected Output: [0, 1, 1, 2, 2]
Explanation: Intervals: idx0=[0,1), idx1=[1,3), idx2=[3,6). Targets 0,1,2,3,5 land in idx0, idx1, idx1, idx2, idx2 respectively.
Input: ([5], [["mint", 0], ["mint", 4]])
Expected Output: [0, 0]
Explanation: k=1 edge case: the single index owns [0,5), so every target returns 0.
Hints
- Index i should own the half-open cumulative interval [cum(i-1), cum(i)) of length w[i]; target r lands in it with probability w[i]/total. Use a strict '>' (first index whose cumulative sum exceeds r) so zero-weight items (empty intervals) are never returned.
- A static prefix-sum array gives O(log k) mint via binary search, but update is O(k) because changing w[i] shifts every later prefix. Replace it with a Fenwick / segment tree to get O(log k) updates.
- On a Fenwick tree you can find the owning index without materializing the prefix array: walk bits from the highest down; greedily take the largest jump whose subtree sum still fits under the remaining target, subtracting as you go. The index you stop at is the interval owner.