MiddleCodeOccasionalNot answered yet
Pick a server at random in proportion to configured load weights
Given server load weights that sum to 1, e.g. {0.3, 0.1, 0.6}, implement chooseServer so each server is picked with probability equal to its weight.
Requirements:
- Use one uniform random draw in
[0, 1). - Over many calls the empirical distribution must match the weights.
int chooseServer(const std::vector<double>& weights, double r) {
// r is a uniform random value in [0, 1); your code here
}Write the implementation.
Build the cumulative distribution: walk the weights accumulating a running sum and return the first index where the sum exceeds r. This maps the uniform draw onto buckets sized by weight, so each server's chance equals its weight. O(k), or O(log k) with a prefix-sum array and binary search.
- ✗Comparing
ragainst each raw weight instead of the cumulative sum - ✗Off-by-one at the boundary, e.g. using
<=so the last bucket is unreachable - ✗Assuming uniform selection already respects the weights
- →How would you speed repeated draws with a prefix-sum array and binary search?
- →What changes if the weights do not sum to exactly 1?
Contents
Task
Implement server selection in proportion to load weights using one uniform draw.
Solution
#include <vector>
int chooseServer(const std::vector<double>& weights, double r) {
double acc = 0.0;
for (int i = 0; i < (int)weights.size(); ++i) {
acc += weights[i]; // cumulative sum
if (r < acc) return i; // first bucket covering r
}
return (int)weights.size() - 1; // guard against rounding error
}Key points
- Compare
ragainst the cumulative sum, not the raw weights. - A bucket as wide as a weight gives probability equal to the weight.
- The
r < accboundary (not<=) keeps the distribution correct.
Contents
