Skip to content
nonconvexcard

Balls into bins, with one choice and with two

CodingIntermediate⏱ 1 hourAI Systemsload balancingballs into binsrandomised algorithmssimulation

Problem

Measure the gap between random assignment and the power of two choices.

  1. assign_balls(n, d, seed) — throw nn balls into nn bins, each ball sampling dd bins uniformly with replacement and landing in the least loaded of them. Return the load array.
  2. max_load(n, d, seed) and mean_max_load(n, d, reps, seed).

Then compare d=1d = 1 against d=2,3,4d = 2, 3, 4 as nn grows from 500500 to 20,00020{,}000 and check the two predicted shapes: log⁡n/log⁡log⁡n\log n/\log\log n against log⁡log⁡n/log⁡d\log\log n/\log d.

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here7 tests · Python runs in your browser
⌘/Ctrl + ↵ to run · limit 90s · draft saved in this browser
7 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Simulate distance contrast runClassical MLCodingBeginner30 min
Cache hit rates under Zipf popularity runAI SystemsCodingIntermediate1 hour
Measure anisotropy in an embedding space runRAGCodingIntermediate1 hour
Measure fan-out amplification and the value of hedging runAI SystemsCodingIntermediate1 hour
Measure the covariance estimation rate runHigh-Dim StatisticsCodingIntermediate1 hour