Daily Coding Problem | Day 1134 | Stream median

devstromo · devstromo · commit e3b909ef305e · 2025-05-25T21:50:26.000-03:00
diff --git a/daily-coding-problem/src/main/java/com/devstromo/day1134/DESCRIPTION.md b/daily-coding-problem/src/main/java/com/devstromo/day1134/DESCRIPTION.md
@@ -0,0 +1,19 @@
+Good morning! Here's your coding interview problem for today.
+
+This problem was asked by Microsoft.
+
+Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.
+
+Recall that the median of an even-numbered list is the average of the two middle numbers.
+
+For example, given the sequence [2, 1, 5, 7, 2, 0, 5], your algorithm should print out:
+
+```
+2
+1.5
+2
+3.5
+2
+2
+2
+```
diff --git a/daily-coding-problem/src/main/java/com/devstromo/day1134/Problem.java b/daily-coding-problem/src/main/java/com/devstromo/day1134/Problem.java
@@ -0,0 +1,36 @@
+package com.devstromo.day1134;
+
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+public class Problem {
+    // Max-heap for the lower half
+    private final PriorityQueue<Integer> lower =
+            new PriorityQueue<>(Comparator.reverseOrder());
+    // Min-heap for the upper half
+    private final PriorityQueue<Integer> higher = new PriorityQueue<>();
+
+    /** Inserts the next value and returns the median after the insertion. */
+    public double add(int value) {
+        // 1. Insert
+        if (lower.isEmpty() || value <= lower.peek()) {
+            lower.offer(value);
+        } else {
+            higher.offer(value);
+        }
+
+        // 2. Re-balance (at most one element difference)
+        if (lower.size() > higher.size() + 1) {
+            higher.offer(lower.poll());
+        } else if (higher.size() > lower.size() + 1) {
+            lower.offer(higher.poll());
+        }
+
+        // 3. Median
+        if (lower.size() == higher.size()) {
+            // Both heaps non-empty because we maintain balance
+            return (lower.peek() + higher.peek()) / 2.0;
+        }
+        return (lower.size() > higher.size()) ? lower.peek() : higher.peek();
+    }
+}
diff --git a/daily-coding-problem/src/test/java/com/devstromo/day1134/ProblemUnitTest.java b/daily-coding-problem/src/test/java/com/devstromo/day1134/ProblemUnitTest.java
@@ -0,0 +1,24 @@
+package com.devstromo.day1134;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class ProblemUnitTest {
+    private final Problem problem = new Problem();
+
+    @Test
+    @DisplayName("Test stream median")
+    void testStreamMedian() {
+        int[] stream      = {2, 1, 5, 7, 2, 0, 5};
+        double[] expected = {2, 1.5, 2, 3.5, 2, 2, 2};
+        for (int i = 0; i < stream.length; i++) {
+            double actual = problem.add(stream[i]);
+            assertEquals(expected[i], actual, 1e-9,
+                    "Mismatch at index " + i);
+        }
+    }
+
+
+}
