Meta·Software Engineer·Onsite - System Design / Architecture·Senior

Senior

Jun 2026

Summary

Meta system design round focused on probabilistic data structures, specifically a weighted random picker. The depth of follow-ups surprised me, went way beyond just slapping a prefix sum together.

Questions Asked (2)

Design a WeightedPicker class that takes an array of positive integer weights and supports a pick() method returning an index proportional to its weight. Optimize for up to 10 million picks after preprocessing up to 100k weights. Walk through your preprocessing choices, random number generation, numerical stability concerns, and time/space complexity.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

I went straight for prefix sums and binary search, which is fine, but they pushed on why not the alias method.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a prefix-sum + binary search solution for O(log n) pick time, and discuss optimizations like the Alias method for O(1) pick time. Walk through preprocessing, random number generation, numerical stability, and complexity analysis, highlighting trade-offs.

Pro tip: Mention that for 10M picks, the Alias method's O(1) pick time is worth the O(n) preprocessing, but if weights change frequently, prefix-sum with binary search is more flexible. Also, discuss using a 64-bit random generator to avoid modulo bias.

1. Clarify Requirements and Constraints

Confirm the number of weights (up to 100k), number of picks (up to 10M), and whether weights can change. Discuss expected time/space complexity and any numerical precision requirements.

2. Choose Preprocessing Strategy

Compare prefix-sum with binary search (O(n) preprocessing, O(log n) pick) vs. Alias method (O(n) preprocessing, O(1) pick). Explain why Alias is better for many picks, but note its complexity and memory overhead.

3. Detail Random Number Generation

Explain how to generate a uniform random number in [0, totalWeight) using a 64-bit RNG, and how to map it to an index via binary search or alias table. Discuss avoiding modulo bias.

4. Address Numerical Stability

Discuss potential overflow when summing weights (use 64-bit integers), and precision issues if using floating-point probabilities. For Alias, ensure probabilities are computed accurately.

5. Analyze Time and Space Complexity

Provide Big-O for preprocessing and pick for both approaches. For Alias: O(n) preprocessing, O(1) pick, O(n) space. For prefix-sum: O(n) preprocessing, O(log n) pick, O(n) space. Justify choice based on pick count.

Key Points to Mention

Prefix-sum array with binary search for O(log n) pick time, simple and easy to implement.
Alias method for O(1) pick time after O(n) preprocessing, ideal for 10M picks.
Use 64-bit integers for cumulative sums to avoid overflow (max sum ~100k * max weight).
Generate random numbers using a high-quality 64-bit RNG (e.g., xorshift) and scale to total weight without modulo bias.
For Alias, handle probabilities carefully to avoid floating-point errors; use double precision and normalize.
Trade-offs: Alias is faster for many picks but more complex and uses extra memory; prefix-sum is simpler and more flexible if weights change.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Extend your WeightedPicker to support addWeight(i, delta) for updating a weight at a given index. Both updates and picks should run in sublinear time. What data structure and approach would you use?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where I blanked a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a Fenwick tree (Binary Indexed Tree) to store weights, enabling O(log n) updates and prefix sum queries. For picking, perform a binary search on the Fenwick tree to find the smallest index where the prefix sum exceeds a random target, achieving O(log n) time.

Pro tip: Mention that a segment tree with augmented sums is an alternative, but a Fenwick tree is simpler and more memory-efficient. Also, clarify that 'sublinear' means O(log n) here, and discuss handling edge cases like zero weights.

1. Clarify requirements and constraints

Confirm that addWeight updates a single weight by delta, and picks select an index with probability proportional to weights. Ensure both operations must be sublinear, typically O(log n).

2. Choose the data structure

Select a Fenwick tree (BIT) for its efficient point updates and prefix sum queries. Alternatively, a segment tree can be used, but justify your choice based on simplicity and performance.

3. Implement addWeight

Update the Fenwick tree at the given index by delta, propagating the change to all relevant nodes in O(log n) time.

4. Implement pick

Generate a random target between 0 and total weight. Use binary lifting on the Fenwick tree to find the smallest index where the prefix sum exceeds the target, in O(log n) time.

5. Analyze complexity and edge cases

State that both operations are O(log n). Discuss handling negative deltas (if allowed), zero weights, and ensuring the total weight remains positive.

Key Points to Mention

Fenwick tree (Binary Indexed Tree) supports point updates and prefix sums in O(log n).
Binary lifting on the Fenwick tree enables O(log n) search for the target index.
Segment tree with augmented sums is an alternative but may have higher constant factors.
Random target generation: uniform in [0, totalWeight) and find first prefix sum > target.
Handling edge cases: zero weights, negative deltas (if allowed), and maintaining total weight.
Time complexity: both addWeight and pick are O(log n), satisfying sublinear requirement.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.