ReservoirSampling.java

packagecom.thealgorithms.randomized;

importjava.util.ArrayList;
importjava.util.List;
importjava.util.Random;

/**
 * Reservoir Sampling Algorithm
 *
 * Use Case:
 * - Efficient for selecting k random items from a stream of unknown size
 * - Used in streaming systems, big data, and memory-limited environments
 *
 * Time Complexity: O(n)
 * Space Complexity: O(k)
 *
 * @author Michael Alexander Montoya (@cureprotocols)
 * @see <a href="https://en.wikipedia.org/wiki/Reservoir_sampling">Reservoir Sampling - Wikipedia</a>
 */
publicfinalclassReservoirSampling {

// Prevent instantiation of utility class
privateReservoirSampling() {
thrownewUnsupportedOperationException("Utility class");
 }

/**
 * Selects k random elements from a stream using reservoir sampling.
 *
 * @param stream The input stream as an array of integers.
 * @param sampleSize The number of elements to sample.
 * @return A list containing k randomly selected elements.
 */
publicstaticList<Integer> sample(int[] stream, intsampleSize) {
if (sampleSize > stream.length) {
thrownewIllegalArgumentException("Sample size cannot exceed stream size.");
 }

List<Integer> reservoir = newArrayList<>(sampleSize);
Randomrand = newRandom();

for (inti = 0; i < stream.length; i++) {
if (i < sampleSize) {
reservoir.add(stream[i]);
 } else {
intj = rand.nextInt(i + 1);
if (j < sampleSize) {
reservoir.set(j, stream[i]);
 }
 }
 }

returnreservoir;
 }
}