CrackML by @ml.with.umang
Interview questions / ML Math
ML Math interview question

Efficient Multinomial Sampling

Given category probabilities, design an efficient sampler and analyze preprocessing and draw complexity.

mediumconceptEvidence 66/1001 source reportGoogle

The 60-second answer

For one/few draws, build cumulative probabilities and binary-search a uniform sample, giving O(n) preprocessing and O(log n) per draw. For very many draws from a fixed distribution, explain the alias method: O(n) preprocessing and O(1) expected draw time.

Build the answer in this order

1
Start with intuition

For one/few draws, build cumulative probabilities and binary-search a uniform sample, giving O(n) preprocessing and O(log n) per draw.

2
Write the mathematical object

For very many draws from a fixed distribution, explain the alias method: O(n) preprocessing and O(1) expected draw time.

3
State assumptions

Handle normalization, zero probabilities, floating-point boundaries, and deterministic seeding in tests.

4
Connect back to ML behavior

Choose the method from update frequency versus sample volume rather than automatically using the theoretically fastest draw.

A useful interview mental model

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

01Definition
02Mechanism
03Trade-offs
04Failure modes
05When to use

Senior-level signal

  • Senior answers discuss dynamic weights, where Fenwick/segment trees can support updates plus O(log n) sampling.
  • Mention statistical tests for empirical frequency and reproducibility, not just unit tests of index bounds.

What the interviewer is really testing

Whether you can connect the math to optimization, uncertainty, model behavior, and a practical engineering decision.

Likely follow-up questions

What assumption makes this approach work?
When would you choose the strongest alternative instead?
What production or data failure mode changes your answer?

Common weak-answer patterns

  • Reciting a definition without mechanism or assumptions.
  • Claiming one technique is always better without a data regime.
  • Stopping before failure modes, validation, or deployment implications.