Quick Overview

This question evaluates a candidate's ability to design and analyze dynamic data structures that support weighted random sampling with inserts and deletes, testing skills in algorithm design, complexity analysis, and randomized sampling under large numeric constraints.

Design dynamic weighted random sampling with updates

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem: Support weighted random sampling with insert/delete Design a data structure that maintains a dynamic set of items, each with a **positive integer weight**, and supports: 1. `insert(id, weight)` - Adds a new item `id` with the given `weight`. - If `id` already exists, you may either reject or treat it as an update (state your choice). 2. `delete(id)` - Removes the item if it exists. 3. `sample() -> id` - Returns an `id` chosen randomly such that: \[ P(id) = \frac{weight(id)}{\sum_j weight(j)} \] ### Requirements - Target time complexity: **O(log n)** per operation. - Must handle up to ~10^5 operations. - Weights can be large (e.g., up to 10^9); total weight may exceed 32-bit. - `sample()` should be unbiased given an ideal RNG. ### Notes - You may assume access to a function `randInt(1, totalWeight)` that returns a uniform integer in that range. - Clearly define how you map item IDs to internal indices as the set changes over time.

Quick Answer: This question evaluates a candidate's ability to design and analyze dynamic data structures that support weighted random sampling with inserts and deletes, testing skills in algorithm design, complexity analysis, and randomized sampling under large numeric constraints.

You are given a sequence of operations on a dynamic set of integer item IDs. Each active item has a positive integer weight. Implement a function that processes all operations and returns the result of every sample query. Operations: - ("insert", id, weight): Insert a new item or update the existing item's weight to the new positive value. - ("delete", id): Remove the item if it exists. If it does not exist, do nothing. - ("sample", r): Simulate weighted random sampling using a pre-generated random integer r. To make sampling deterministic for testing, active items are considered in increasing ID order. If their current weights are w1, w2, ..., then they occupy cumulative intervals [1, w1], [w1+1, w1+w2], and so on. A sample query returns the ID whose interval contains r. If the set is empty, or r is outside the range [1, totalWeight], return -1 for that sample. Your goal is to support up to about 10^5 operations efficiently.

Constraints

  • 1 <= len(operations) <= 100000
  • 1 <= weight <= 10^9 for insert operations
  • IDs are integers and may be sparse or large in magnitude
  • The total active weight can exceed 32-bit integer range
  • Insert on an existing ID must be treated as a weight update
  • Delete on a missing ID is a no-op

Examples

Input: [("insert", 10, 4), ("insert", 20, 6), ("sample", 1), ("sample", 4), ("sample", 5), ("sample", 10)]

Expected Output: [10, 10, 20, 20]

Explanation: In increasing ID order, 10 owns [1,4] and 20 owns [5,10].

Input: [("insert", 5, 3), ("insert", 2, 2), ("sample", 4), ("insert", 5, 1), ("sample", 2), ("delete", 2), ("sample", 1), ("delete", 5), ("sample", 1)]

Expected Output: [5, 2, 5, -1]

Explanation: Insert on existing ID updates its weight. After all deletions, sampling from an empty set returns -1.

Hints

  1. Compress item IDs into fixed indices, then store current weights in a Fenwick tree or segment tree.
  2. A sample query is equivalent to finding the first index whose prefix-sum weight is at least r.

Loading coding console...