Katkat
Back

Generate Weighted Random NFTs with Updates

CoinbaseSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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 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).