CrackML by @ml.with.umang
Interview questions / ML Coding & PyTorch
ML Coding & PyTorch interview question

Large-Scale Weighted Random Sampling

Design weighted random sampling when there are millions of items and weights may update.

hardml codingEvidence 41/1001 source reportMeta

The 60-second answer

For static weights, prefix sums plus binary search give O(n) build/O(log n) sample; alias tables give O(n) build/O(1) sample. For frequent point updates, a Fenwick or segment tree stores subtree weight mass and supports both update and sample in O(log n).

Build the answer in this order

1
State tensor contract

For static weights, prefix sums plus binary search give O(n) build/O(log n) sample; alias tables give O(n) build/O(1) sample.

2
Implement the mechanism

For frequent point updates, a Fenwick or segment tree stores subtree weight mass and supports both update and sample in O(log n).

3
Check numerics + gradients

Define behavior for zero/negative weights, total-mass overflow, concurrent updates, and snapshot consistency.

4
Test shapes and edge cases

Benchmark based on the real read:update ratio and memory budget, not sampling complexity alone.

A useful interview mental model

This is the shape of a strong answer—not a script to memorize.

01Shapes
02Forward pass
03Loss / grads
04Numerics
05Tests

Senior-level signal

  • Senior answers discuss sharding the mass across machines and selecting shard then item hierarchically.
  • Include deterministic replay/versioned weight snapshots when sampling decisions affect experiments or user experience.

What the interviewer is really testing

Tensor fluency, shape reasoning, numerics, gradients, batching, device awareness, and the ability to debug—not API memorization.

Likely follow-up questions

What are the tensor shapes at each step?
Where could numerical instability or silent broadcasting appear?
How would you verify gradients and batched behavior?

Common weak-answer patterns

  • Ignoring shape, dtype, device, masking, or broadcasting assumptions.
  • Using a framework call without explaining the underlying operation.
  • Skipping gradient, numerical-stability, and batching checks.