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 Onsite rounds at Coinbase.

What role is this question designed for?

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

Generate Weighted Random NFTs with Updates

Quick Overview

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.

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.

Input: ([1, 0, 1], [["mint", 0], ["mint", 1]])

Expected Output: [0, 2]

Explanation: idx1 has weight 0, so it owns the empty interval and is never returned. Intervals: idx0=[0,1), idx1=[1,1) empty, idx2=[1,2). Target 0 -> idx0, target 1 -> idx2.

Input: ([2, 3, 5], [["mint", 7], ["update", 0, 10], ["mint", 5], ["mint", 13]])

Expected Output: [2, 0, 1]

Explanation: Initially intervals idx0=[0,2), idx1=[2,5), idx2=[5,10); target 7 -> idx2. After update(0,+10) weights are [12,3,5], intervals idx0=[0,12), idx1=[12,15), idx2=[15,20); target 5 -> idx0, target 13 -> idx1.

Input: ([4, 4, 4, 4], [["mint", 0], ["mint", 4], ["mint", 8], ["mint", 12], ["mint", 15]])

Expected Output: [0, 1, 2, 3, 3]

Explanation: All-equal weights: intervals are [0,4),[4,8),[8,12),[12,16). Targets at each boundary 0,4,8,12 map cleanly to indices 0..3; target 15 is the last position in idx3.

Input: ([10, 1], [["update", 0, -9], ["mint", 0], ["mint", 1]])

Expected Output: [0, 1]

Explanation: After update(0,-9) weights are [1,1], intervals idx0=[0,1), idx1=[1,2). Target 0 -> idx0, target 1 -> idx1. Shows updates can shrink a weight and rebalance the intervals.

Input: ([3, 3], [["mint", 2], ["mint", 3], ["mint", 5]])

Expected Output: [0, 1, 1]

Explanation: Intervals idx0=[0,3), idx1=[3,6). Target 2 -> idx0; target 3 (the boundary) -> idx1 because index i owns [cum(i-1), cum(i)) and we pick the first cumulative sum strictly greater than r; target 5 -> idx1.

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.

Quick Overview