Probability/Randomization based coding problems
Fixed-range sampling
Fixed-range sampling is a technique used in data analysis and statistics to select a subset of data points from a larger dataset. It involves dividing the data into fixed-sized intervals or ranges and then selecting a specific number of data points from each range.
Following is sample code
const fixedRangeSampling = (data, numSamples, rangeSize)=> {
const numRanges = Math.ceil(data.length / rangeSize);
const samples = [];
for (let i = 0; i < numRanges; i++) {
const start = i * rangeSize;
const end = Math.min(start + rangeSize, data.length);
const rangeData = data.slice(start, end);
// Randomly select samples from the range
while (samples.length < (i + 1) * (numSamples / numRanges)) {
const randomIndex = Math.floor(Math.random() * rangeData.length);
samples.push(rangeData[randomIndex]);
}
}
return samples;
}
// Example usage
const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const numSamples = 5;
const rangeSize = 3;
const sampledData = fixedRangeSampling(data, numSamples, rangeSize);
console.log(sampledData);Reservoir Sampling: A Technique for Sampling from Streams
Reservoir sampling is a technique used to select a random sample of fixed size from a stream of data, where the number of elements in the stream is unknown or potentially infinite. This technique is particularly useful when dealing with large datasets that cannot be stored in memory at once.
const reservoirSampling = (stream, k) => {
const reservoir = [];
for (let i = 0; i < stream.length; i++) {
const element = stream[i];
if (i < k) {
reservoir.push(element);
} else {
const randomIndex = Math.floor(Math.random() * (i + 1));
if (randomIndex < k) {
reservoir[randomIndex] = element;
}
}
}
return reservoir;
}
// Example usage
const stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const sampleSize = 3;
const sampledData = reservoirSampling(stream, sampleSize);
console.log(sampledData);528. Random Pick with Weight
https://leetcode.com/problems/random-pick-with-weight/description/
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
Intuition
Goal is to sample data with weight.
Generally when we pick number from set for example [1,9] , choosing either 1 or 9 is 50% probability. But in this question we need to choose 1 with 10% and 9 with 90% as goal is to choose as per weight i.e. num/total .
We can relate this problem on throwing ball on the line where each number is projected as per their weight as below.
If we throw ball multiple times then we can say that 9 out of 10 times ball will fall into 9 range.
We can construct the line in the experiment by chaining up all values together.
Here we can see that the offsets of the ranges are actually the prefix sums from a sequence of numbers.
Since weights given are positive therefore prefix sum will be monotonically increasing.
To throw a ball on the line is to find an offset to place the ball. Let us call this offset target.
Algorithm
- Set up the playground, by generating a list of prefix sums from a given list of numbers.
- Generate a random number between
0andtotalSum. This will be thetargetto search in the prefix sum to find out the block. - Scan through the prefix sums to find the first prefix sum that is larger than our
targetoffset. - And the index of this prefix sum would be exactly the right place that the target should fall into.
Following is the code to implement it.
/**
* @param {number[]} w
*/
var Solution = function (w) {
const n = w.length;
this.prefix = new Array(n).fill(0);
this.prefix[0] = w[0];
for (let i = 1; i < n; i++) {
this.prefix[i] = this.prefix[i - 1] + w[i];
}
this.total = this.prefix[n - 1];
};
/**
* @return {number}
*/
Solution.prototype.pickIndex = function () {
const target = Math.random() * this.total;
// Run a linear search (or use binary search) to find the target zone
for (let i = 0; i < this.prefix.length; i++) {
if (target < this.prefix[i]) {
return i;
}
}
return -1;
};398. Random Pick Index
https://leetcode.com/problems/random-pick-index/description
Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Implement the Solution class:
Solution(int[] nums)Initializes the object with the arraynums.int pick(int target)Picks a random indexifromnumswherenums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.
Example 1:
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.Approach
Apply random on the list of target’s indeces.
/**
* @param {number[]} nums
*/
var Solution = function (nums) {
const map = new Map();
const n = nums.length;
for (let i = 0; i < n; i++) {
const num = nums[i];
if (!map.has(num)) {
map.set(num, []);
}
map.get(num).push(i);
}
this.map = map;
};
/**
* @param {number} target
* @return {number}
*/
Solution.prototype.pick = function (target) {
const ids = this.map.get(target);
const total = ids.length;
const random = Math.floor(Math.random() * total);
return ids[random];
};
