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.