Generate Weighted Random NFTs with Updates

Q: Generate Weighted Random NFTs with Updates

This is a Coding & Algorithms interview question from Coinbase for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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: (

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). (
Support mintWithoutReplacement(t) that draws t distinct NFTs according to current weights, efficiently updating state after each draw. (
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).

Generate Weighted Random NFTs with Updates

Comments (0)