Repository: TheAlgorithms/Java
Pull request #6204 (2025-03-30 02:10:57)

Add ReservoirSampling algorithm to randomized module
###  Algorithm Overview:
- Efficient for selecting k random elements from a stream of unknown size
- Commonly used in streaming systems, big data pipelines, and memory-limited environments
- Time Complexity: O(n)
- Space Complexity: O(k)

---

###  Implementation Details:
- Class: `ReservoirSampling`
- Package: `com.thealgorithms.randomized`
- JavaDoc included for class and method
- Demonstration included in `main()` method
- File name and class name follow PascalCase
- Fully formatted using `clang-format`

---

###  Reference:
- [Reservoir Sampling - Wikipedia](https://en.wikipedia.org/wiki/Reservoir_sampling)

Author: Michael Alexander Montoya (@cureprotocols)

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`



DenizAltunkapan: What if sampleSize > stream.length? Perhaps there should be error handling for invalid input, the rest lgtm
cureprotocols: Added input validation for `sampleSize > stream.length` as requested — thanks for the suggestion, @DenizAltunkapan!

Let me know if anything else is needed — happy to improve further


cureprotocols: ✅ Applied clang-format and added JUnit test to `src/test/java/com/thealgorithms/randomized/`.

All requested changes completed. Ready for final review 💪

cureprotocols: ✅ Final test file now formatted with `clang-format --style=file`
✅ Verified formatting with `--dry-run --Werror`
✅ Test class is correctly placed under:
  `src/test/java/com/thealgorithms/randomized/ReservoirSamplingTest.java`

CI will re-run shortly. Appreciate all the support — ready for merge when you are 💪

siriak: Error:  /home/runner/work/Java/Java/src/main/java/com/thealgorithms/randomized/ReservoirSampling.java:19:1: Utility classes should not have a public or default constructor. [HideUtilityClassConstructor]
Error:  /home/runner/work/Java/Java/src/test/java/com/thealgorithms/randomized/ReservoirSamplingTest.java:3:47: Using the '.*' form of import should be avoided - org.junit.jupiter.api.Assertions.*. [AvoidStarImport]
cureprotocols: ✅ All requested changes are now complete:

- ✅ Converted `ReservoirSampling` to `final` class with private constructor
- ✅ No wildcard imports (`org.junit.jupiter.api.Assertions.*` removed)
- ✅ JUnit test placed in correct directory: `src/test/java/com/thealgorithms/randomized`
- ✅ Verified both files pass clang-format `--style=file`
- ✅ Confirmed formatting via `--dry-run --Werror`

Thanks again for your review and feedback. Ready for merge when you are.


Patch:
diff --git a/src/main/java/com/thealgorithms/randomized/ReservoirSampling.java b/src/main/java/com/thealgorithms/randomized/ReservoirSampling.java
new file mode 100644
index 00000000..05e70f63
--- /dev/null
+++ b/src/main/java/com/thealgorithms/randomized/ReservoirSampling.java
@@ -0,0 +1,55 @@
+package com.thealgorithms.randomized;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.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>
+ */
+public final class ReservoirSampling {
+
+    // Prevent instantiation of utility class
+    private ReservoirSampling() {
+        throw new UnsupportedOperationException("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.
+     */
+    public static List<Integer> sample(int[] stream, int sampleSize) {
+        if (sampleSize > stream.length) {
+            throw new IllegalArgumentException("Sample size cannot exceed stream size.");
+        }
+
+        List<Integer> reservoir = new ArrayList<>(sampleSize);
+        Random rand = new Random();
+
+        for (int i = 0; i < stream.length; i++) {
+            if (i < sampleSize) {
+                reservoir.add(stream[i]);
+            } else {
+                int j = rand.nextInt(i + 1);
+                if (j < sampleSize) {
+                    reservoir.set(j, stream[i]);
+                }
+            }
+        }
+
+        return reservoir;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/randomized/ReservoirSamplingTest.java b/src/test/java/com/thealgorithms/randomized/ReservoirSamplingTest.java
new file mode 100644
index 00000000..0c6061fc
--- /dev/null
+++ b/src/test/java/com/thealgorithms/randomized/ReservoirSamplingTest.java
@@ -0,0 +1,45 @@
+package com.thealgorithms.randomized;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.Arrays;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+public class ReservoirSamplingTest {
+
+    @Test
+    public void testSampleSizeEqualsStreamLength() {
+        int[] stream = {1, 2, 3, 4, 5};
+        int sampleSize = 5;
+
+        List<Integer> result = ReservoirSampling.sample(stream, sampleSize);
+
+        assertEquals(sampleSize, result.size());
+        assertTrue(Arrays.stream(stream).allMatch(result::contains));
+    }
+
+    @Test
+    public void testSampleSizeLessThanStreamLength() {
+        int[] stream = {10, 20, 30, 40, 50, 60};
+        int sampleSize = 3;
+
+        List<Integer> result = ReservoirSampling.sample(stream, sampleSize);
+
+        assertEquals(sampleSize, result.size());
+        for (int value : result) {
+            assertTrue(Arrays.stream(stream).anyMatch(x -> x == value));
+        }
+    }
+
+    @Test
+    public void testSampleSizeGreaterThanStreamLengthThrowsException() {
+        int[] stream = {1, 2, 3};
+
+        Exception exception = assertThrows(IllegalArgumentException.class, () -> ReservoirSampling.sample(stream, 5));
+
+        assertEquals("Sample size cannot exceed stream size.", exception.getMessage());
+    }
+}