Coding interviews
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
var medians = new Median();
foreach(int x in new[] { int.MaxValue, int.MaxValue, int.MinValue, 0 }) { medians.Add(x); Console.WriteLine(medians.Value().ToString("0.0",CultureInfo.InvariantCulture)); }
sealed class Median {
private readonly PriorityQueue<int,int> low = new(Comparer<int>.Create((a,b)=>b.CompareTo(a)));
private readonly PriorityQueue<int,int> high = new();
public void Add(int x) { if(low.Count==0 || x<=low.Peek()) low.Enqueue(x,x); else high.Enqueue(x,x);
if(low.Count>high.Count+1) { int v=low.Dequeue(); high.Enqueue(v,v); }
if(high.Count>low.Count) { int v=high.Dequeue(); low.Enqueue(v,v); } }
public decimal Value() { if(low.Count==0) throw new InvalidOperationException("empty"); return low.Count==high.Count ? ((long)low.Peek()+high.Peek())/2m : low.Peek(); }
}
Reveal answer and reasoning
The output lines, in order, are “2147483647.0”; “2147483647.0”; “2147483647.0”; “1073741823.5”. The first two maximum integers produce the same maximum median. Adding the minimum integer leaves the lower boundary at maximum because two of three values are maximum. Adding zero gives the sorted middle values zero and maximum, whose average is 1073741823.5. Converting before addition avoids overflowing the integer sum. Insertion first chooses a side by comparison with low.Peek, then moves at most one root to repair size imbalance.
Moving the maximum lower value upward or minimum upper value downward preserves ordering. The fourth output is a useful arithmetic boundary because one middle value is maximum and the other zero.
Each insertion performs a bounded number of heap operations, costing O(log n) time; reading the median is O(1). Both heaps together retain all n input values, so this exact unbounded-history structure uses O(n) storage. A streaming interface is not automatically constant-memory. Negating an integer priority to simulate a max-heap fails at int.MinValue. The comparer reverses CompareTo instead, avoiding subtraction and negation overflow.
Sliding-window medians require removing expired values or another data structure; this implementation handles append-only history only.
What a strong answer covers
- Exact output: 2147483647.0 | 2147483647.0 | 2147483647.0 | 1073741823.5
- The first two maximum integers produce the same maximum median.
- Negating an integer priority to simulate a max-heap fails at int.MinValue.
Common pitfall
Negating an integer priority to simulate a max-heap fails at int.MinValue. The comparer reverses CompareTo instead, avoiding subtraction and negation overflow. Sliding-window medians require removing expired values or another data structure; this implementation handles append-only history only.
Follow-up questions
- Test duplicates, a single minimum integer, an even pair spanning both integer extremes and querying before the first insertion. Hint: check size and ordering invariants after every insertion, not just the final printed median.
- How would expiration of the oldest value change the append-only median design?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.