Dynamic Weighted Sampling
Updated
Problem statement
Maintain items with positive integer weights. Process operations on an initially empty collection:
[0, id, weight]: insert an item, or replace its weight if the identifier already exists.[1, id, 0]: remove that item. Removing an absent identifier does nothing.[2, ticket, 0]: return the item selected by the ticket, or-1if the collection is empty.
An identifier keeps the slot assigned at its first insertion, including after removal and reinsertion. Read active items in this slot order. An item with weight w owns w consecutive ticket values. Ticket values start at zero; select the item whose cumulative weight first exceeds ticket.
For a nonempty collection with total weight W, the input guarantees 0 <= ticket < W. For an empty collection, the ticket is zero. Choosing a ticket uniformly from this range samples each item with probability equal to its weight divided by W. The explicit ticket makes this exercise deterministic.
Return only sample results, in operation order. Explain how a Fenwick tree supports weight changes and ticket selection without scanning every active item.
Function
weightedSamples(operations: int[][]) → int[]Examples
Example 1
operations = [[0,10,2],[0,20,3],[2,0,0],[2,2,0],[1,10,0],[2,0,0]]return = [10,20,20]The weights 2 and 3 give item 10 tickets 0 and 1, and item 20 tickets 2, 3, and 4. Thus tickets 0 and 2 select 10 and 20. After removing 10, every valid ticket selects 20.
Example 2
operations = [[2,0,0],[0,8,1],[0,3,2],[1,8,0],[0,8,4],[2,3,0],[2,4,0]]return = [-1,8,3]The empty sample returns -1. Item 8 keeps its first slot after reinsertion, so it owns tickets 0 through 3. Item 3 owns tickets 4 and 5.
Constraints
0 <= operations.length <= 5000.- Each operation contains exactly three integers.
- The operation code is 0, 1, or 2.
0 <= id <= 10^6.1 <= weight <= 1000for insertion or replacement.- Every integer in the input lies between 0 and 5000000.
- Delete and sample operations have a final value of zero.
- Every sample ticket satisfies the current total-weight rule above.
More Citadel Onsite Interview questions
- Maximize Workday EarningsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Changes for Palindromic BlocksOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Removal PoolONSITE INTERVIEW · Seen Sep 2026
- Centered K-by-K Submatrix SumsONSITE INTERVIEW · Seen Aug 2026
- Search Suggestions with a Prefix TreeONSITE INTERVIEW · Seen Aug 2026
- Traverse Interior Matrix Cells in Row-Major OrderONSITE INTERVIEW · Seen Aug 2026
- Time-Based Key-Value StorePHONE SCREEN · ONSITE INTERVIEW · Seen Feb 2026
- 2048 Simulation and Board CodecONSITE INTERVIEW · Seen Jan 2026
- Cancellable Priority Task QueueONSITE INTERVIEW · Seen Jan 2026
- Exchange Connection AlertsONSITE INTERVIEW · Seen Jan 2026
Similar questions at other companies
- Out-of-Order Logger Rate LimiterGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Maintain a Consistent-Hashing RingCohesity · ONSITE INTERVIEW
- Maintain a Consistent-Hashing RingApple · PHONE SCREENApple interview questions
- Time Map with Sum and AverageConfluent · PHONE SCREENConfluent interview questions
- Versioned Social NetworkOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Range Sum Query in a Mutable GridBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Totals from a Tiered Rate TableMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Roll a Weighted DieLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Time-Based Key-Value StoreOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions
- Time-Based Key-Value StoreCockroach Labs · PHONE SCREEN · ONSITE INTERVIEW