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.
assign_balls(n, d, seed)— throw balls into bins, each ball sampling bins uniformly with replacement and landing in the least loaded of them. Return the load array.max_load(n, d, seed)andmean_max_load(n, d, reps, seed).
Then compare against as grows from to and check the two predicted shapes: against .
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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Simulate distance contrast run | Classical ML | Coding | 30 min | ||
| Cache hit rates under Zipf popularity run | AI Systems | Coding | 1 hour | ||
| Measure anisotropy in an embedding space run | RAG | Coding | 1 hour | ||
| Measure fan-out amplification and the value of hedging run | AI Systems | Coding | 1 hour | ||
| Measure the covariance estimation rate run | High-Dim Statistics | Coding | 1 hour |