Asked at Virtu Financial, D.E. Shaw
Theory: Quant Python That Survives ReviewRead the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.
Implement chunk_order(total, weights), which slices a parent order across
time buckets in proportion to the expected volume in each.
The slices are lots, so they must be whole numbers, and they must add up to the parent exactly. Rounding each slice on its own fails: rounding down under-fills the order, and rounding to nearest can overshoot it. The standard answer to this apportionment problem is the largest remainder method.
total is a non-negative integer, the parent quantity.weights is a list of non-negative integers, the expected volume per bucket.Bucket \( i \) is entitled to \( total \times w_i / W \) lots, where \( W \) is the sum of the weights. Allocate by largest remainder:
Return the list of integer slices, in bucket order.
The returned list must sum to total exactly. That is the property being
tested, and it is what makes the naive per-bucket rounding wrong.
chunk_order(100, [1, 1, 1])
# [34, 33, 33]
chunk_order(10, [1, 1, 1, 1])
# [3, 3, 2, 2]
In the first, each bucket is entitled to \( 33\tfrac{1}{3} \) lots. All three floor to 33, leaving one lot over, and all three tie on the remainder, so the earliest takes it.
0 <= total <= 10^9 and 0 <= len(weights) <= 2 * 10^5.