FastPrepDynamic Weighted Sampling
Problems/Dynamic Weighted Sampling

Dynamic Weighted Sampling

Citadel logoCitadel● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Citadel intern onsite interview. The report describes insertion, deletion, weighted random sampling, and a Fenwick tree that grows as needed, with binary lifting. We chose the identifiers, what replacement does, the order of slots, the ticket input, the limits, and the examples. Our version is about 80% the same as the reported question.

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 -1 if 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 <= 1000 for 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

Interview reports that mention this question

  • Citadel SWE Intern Later Rounds and Superday: 13 Experiences

Citadel interview experiences

  • Citadel Securities Quant Researcher Intern Loop: 1 Experience
  • Citadel Securities Research Engineer Interview: 1 Experience
  • Citadel Securities SWE Intern First Round: 2 Experiences
  • Citadel Securities Experienced SWE Interviews: 1 Experience
  • Citadel SWE Intern First-Round Questions: 20 Experiences
All Citadel interview questionsSee Citadel hiring insights
Saved
class Solution {
    public int[] weightedSamples(int[][] operations) {
        // Write your code here.
    }
}
Checking account…