Generate Weighted Random NFTs with Updates

Q: Generate Weighted Random NFTs with Updates

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.

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

Overview

Comments (0)