CareerCup

We need to maintain 1 max heap and 1 min heap. Max heap will contain lower half of the numbers and min the upper half. Whenever, a new number comes:
1) if its less than root of max heap, it is inserted into max heap.
2) if its higher than root of min heap, it is inserted into min heap.
3) after insertion if the size difference of two heaps is greater than 1, the root of the larger heap is transferred to the other heap to balance their size.

At any point, the median will be:
1) (root of max heap + root of min heap) / 2 if size of both heap are equal.
2) root of larger heap otherwise.

1. Use binary search tree with ability to calculate order statistic. Add: O(logN), Median: O(logN).
2. Use two priority queues. One queue for N/2 greater values and another for N/2 smaller values. Add: O(logN), Median: O(1)

For the answer please refer to stackoverflow com questions 10930732 c-efficiently-calculating-a-running-median

just replace the space with / (except for the com ofcourse)

For the answer please refer to stackoverflow com questions 10930732 c-efficiently-calculating-a-running-median

just replace the space with / (except for the com ofcourse)

For the answer please refer to stackoverflow com questions 10930732 c-efficiently-calculating-a-running-median

just replace the space with / (except for the com ofcourse)

#!/bin/bash

while read line
do
newline=`echo $line | sed -e 's/,/ /g'`
array=($newline)
number_count=`echo $line | sed -e 's/,/ /g'|wc | awk '{print $2}'`
expected_mid_count=`expr $number_count / 2`
med_number=0
for ((i=0;i<$number_count;i++));
do
array_gt_count[$i]=0
next_no=`expr $i + 1`
for ((j=0;j<$number_count;j++));
do
if [ ${array[${i}]} -gt ${array[${j}]} ]; then
array_gt_count[${i}]=`expr ${array_gt_count[${i}]} + 1`
fi
done
if [ ${array_gt_count[${i}]} = $expected_mid_count ]; then
echo ${array[${i}]}
exit
fi
done

done

We just need a node (Median) whose left and right nodes are two AVL trees (or RB trees, etc.).

1. The Median node has a goLeft flag to mentain the median position.
2. If goLeft flag is on, the next insertion should be to the left tree, otherwise to the right tree.
3. If input number is bigger than median. Insert it to the right. If goLeft is true, insert median to the left, make the smallest number from right the new median and delete it from right.
4. If input number is smaller than median. Insert it to the left. If goLeft is false, insert median to the right, make the biggest number from left the new median and delete it from left.

<?php
class AvlTree {
	...
}
class Median implements SampleHandler {
	public $data;
	public $left;
	public $right;
	public $goLeft = false;
	public function __construct() {
		$this->left = new AvlTree();
		$this->right = new AvlTree();
	}
	public function addNumber($number) {
		if ($this->data === null) { 
			// First number
			$this->data = $number;
			return;
		}
		$median = $this->data; 
		if ($median > $number) {
			$this->left->insert($number);
			if ($this->goLeft === false) {
				$this->right->insert($median);
				$biggest = $this->left->last();
				$this->data = $biggest->data;
				$this->left->delete($biggest);
			}
		} else {
			$this->right->insert($number);
			if ($this->goLeft) {
				$this->left->insert($median);
				$smallest = $this->right->first();
				$this->data = $smallest->data;
				$this->right->delete($smallest);
			}
		}
		$this->goLeft = !$this->goLeft;
	}
	public function median() {
		return $this->data;
	}
}

I would actually extend NSMutableArray to create the Heap structure. With an ascending and descending flag since we then can create a max and minimum heap.

@implementation NSMutableArray (Heap)

- (void)balanceExchangeFromIndex:(NSUInteger)origin toIndex:(NSUInteger)destination inAscendingOrder:(BOOL)isAscending {
    [self exchangeObjectAtIndex:origin withObjectAtIndex:destination];
    [self balanceObjectAtIndex:destination inAscendingOrder:isAscending];
    
}

- (void)balanceObjectAtIndex:(NSUInteger)childIndex inAscendingOrder:(BOOL)isAscending {
    NSUInteger parent = 0;
    if (childIndex > 1) {
        parent = childIndex/2;
        
        if (!isAscending) {
            if ([self objectAtIndex:childIndex -1] < [self objectAtIndex:parent -1]) {
                [self balanceExchangeFromIndex:childIndex-1 toIndex:parent - 1 inAscendingOrder:isAscending];
            }
        } else {
            if ([self objectAtIndex:childIndex -1] > [self objectAtIndex:parent -1]) {
                [self balanceExchangeFromIndex:childIndex-1 toIndex:parent - 1 inAscendingOrder:isAscending];
            }
        }
    }
}

- (void)balanceArrayWithAscendingOrder:(BOOL)isAscending {
    
    
    [self enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        [self balanceObjectAtIndex:idx+1 inAscendingOrder:isAscending];
    }];
    
}

@end

Now that this is done, the rest is more or less to maintain 2 arrays and check balance each time a new object has been added. Using NSInteger instead of NSNumber (i did it with NSInteger but the difference is minimum) this 3 methods should do all the exercise. To be said that the structure can be improved a bit more since we could reduce the balance enumeration for each add but, i tried to make everything in 30 min to mimic an interview.

- (void)addObjectAndBalanceHeaps:(id)object {
    //NSUInteger maxHeaphead = [[_maxHeap firstObject] unsignedIntegerValue];
    NSUInteger minHeapHead = [[_minHeap firstObject] unsignedIntegerValue];
    if ([object unsignedIntegerValue] >= minHeapHead) {
        [_maxHeap addObject:object];
        [_maxHeap balanceArrayWithAscendingOrder:NO];
    } else {
        [_minHeap addObject:object];
        [_minHeap balanceArrayWithAscendingOrder:YES];
    }
    [self balanceArrays];
}

- (void)balanceArrays {
    NSInteger maxHeapCount = [_maxHeap count];
    NSInteger minHeapCount = [_minHeap count];
    if (abs((int)(maxHeapCount - minHeapCount)) > 1) {
        if (maxHeapCount > minHeapCount) {
            [_minHeap addObject:[_maxHeap firstObject]];
            [_maxHeap removeObjectAtIndex:0];
        } else {
            [_maxHeap addObject:[_minHeap firstObject]];
            [_minHeap removeObjectAtIndex:0];
        }
        [_maxHeap balanceArrayWithAscendingOrder:NO];
        [_minHeap balanceArrayWithAscendingOrder:YES];
    }
}

- (NSNumber *)median {
    
    NSInteger maxHeapCount = [_maxHeap count];
    NSInteger minHeapCount = [_minHeap count];
    NSUInteger maxHeaphead = [[_maxHeap firstObject] unsignedIntegerValue];
    NSUInteger minHeapHead = [[_minHeap firstObject] unsignedIntegerValue];
    if ((maxHeapCount + minHeapCount) % 2 == 0) {
        double result = (maxHeaphead + minHeapHead)/2.0;
        return [NSNumber numberWithDouble:result];
    } else {
        return (maxHeapCount > minHeapCount)?
        [NSNumber numberWithInteger:maxHeaphead]:
        [NSNumber numberWithInteger:minHeapHead];
    }
    
}

No idea what the complexity of this would be, but here's a dead simple solution.

@interface SampleHandler ()

@property (nonatomic, strong) NSMutableArray *numbers;

@end

@implementation SampleHandler

- (void)addNumber:(NSNumber*)number
{
    [self.numbers addObject:number];
}

- (NSNumber*)median
{
    return [[self.numbers sortedArrayUsingSelector:@selector(compare:)] objectAtIndex:[self.numbers count] / 2];
}

- (NSMutableArray*)numbers
{
    if (_numbers == nil)
    {
        _numbers = [[NSMutableArray alloc]init];
    }
    return _numbers;
}

@end

Insertion Sort.. Return Middle element each time O(n)
2 Heaps/Priority queues : O(log n)
Balancing Binary Search Tree - Order Statistics - O(log n)

This is my answer:

#import <Foundation/Foundation.h>

@interface CXAMedian: NSObject

- (void)addNumber:(NSNumber *)number;
- (NSNumber *)median;

@end

@interface CXAMedian() {
  NSMutableArray *_orderedNumbers;
  NSMutableArray *_sortedNumbers;
}

@end

@implementation CXAMedian

- (instancetype)init
{
  if (!(self = [super init]))
    return nil;

  _orderedNumbers = [NSMutableArray array];
  _sortedNumbers = [NSMutableArray array];
  return self;
}

- (void)addNumber:(NSNumber *)number
{
  [_orderedNumbers addObject:number];
  NSUInteger insertIndex = [_sortedNumbers indexOfObject:number inSortedRange:NSMakeRange(0, [_sortedNumbers count]) options:NSBinarySearchingInsertionIndex usingComparator:^NSComparisonResult(NSNumber *n1, NSNumber *n2) {
    return [n1 compare:n2];
  }];
  [_sortedNumbers insertObject:number atIndex:insertIndex];
}

- (NSNumber *)median
{
  NSUInteger count = [_sortedNumbers count];
  if (count % 2 == 0)
    return nil;

  return _sortedNumbers[count / 2];
}

@end

int main(int argc, char **argv) {
  @autoreleasepool {
    CXAMedian *m = [[CXAMedian alloc] init];
    [m addNumber:@9];
    [m addNumber:@3];
    [m addNumber:@4];
    NSLog(@"median of %@ is: %@", m, [m median]);
    return 0;
  }
}

A simple implementation in C# with Min and Max Heap

public static void Main()
	{
		int[] ar1 = {16, 17, 18, 6, 38, 19};
    	
    	MedianFinder med = new MedianFinder();
    	foreach (int elem in ar1)
    	{
    		med.Add(elem);
    	}
    	
    	Console.WriteLine(med.GetMedian());
	}
	
	public class MedianFinder
	{
		public Heap minHeap;
		public Heap maxHeap;
		public MedianFinder()
		{
			minHeap = new Heap(HeapType.Min);
			maxHeap = new Heap(HeapType.Max);
		}
		
		public void Add(int value)
		{
			if (maxHeap.heapSize == 0 || maxHeap.GetTop() > value)
			{
				maxHeap.Insert(value);
			}
			else
			{
				minHeap.Insert(value);
			}
			
			if (maxHeap.heapSize > minHeap.heapSize + 1)
			{
				int top = maxHeap.ExtractTop();
				minHeap.Insert(top);
			}
			if (minHeap.heapSize > maxHeap.heapSize + 1)
			{
				int top = minHeap.ExtractTop();
				maxHeap.Insert(top);
			}
		}
		
		public int GetMedian()
		{
			if (maxHeap.heapSize > minHeap.heapSize + 1)
			{
				return maxHeap.GetTop();
			}
			
			return minHeap.GetTop();
		}
	}
	
	
	public class Heap
	{
		private HeapType heapType;
		int[] heapElems;
		public int heapSize;
		public Heap(HeapType type)
		{
			this.heapType = type;
			this.heapSize = 0;
			heapElems = new int[100];
		}
		
		public int GetTop()
		{
			return heapElems[0];
		}
		
		public void Insert(int value)
		{
			heapElems[heapSize] = value;
			Heapify_Up(heapSize++);
		}
		
		public int ExtractTop()
		{
			int top = heapElems[0];
			heapElems[0] = heapElems[--heapSize];
			Heapify_Down(0);
			return top;
		}
		
		public void Heapify_Down(int pos)
		{
			if (pos >= heapSize) return;
			int left = Left(pos);
			int right = Right(pos);
			int elem = heapElems[pos];
			
			int replacePos = left;
			if (Compare(heapElems[left], heapElems[right]) && right <= heapSize)
			{
				replacePos = right;
			}
			
			if (replacePos <= heapSize && Compare(elem, heapElems[replacePos]))
			{
				heapElems[pos] = heapElems[replacePos];
				heapElems[replacePos] = elem;
				Heapify_Down(replacePos);
			}
		}
		
		public void Heapify_Up(int pos)
		{
			if (pos == 0) return;
			int parent = Parent(pos);
			int parentelem = heapElems[parent];
			
			if (Compare(parentelem, heapElems[pos]))
			{
				heapElems[parent] = heapElems[pos];
				heapElems[pos] = parentelem;
				Heapify_Up(parent);
			}
		}
		
		public string GetString()
		{
			string str = string.Empty;
			for (int i = 0; i < heapSize; i++)
			{
				str += ":" + heapElems[i];
			}
			
			return str;
		}
		
		public bool Compare(int elem1, int elem2)
		{
			return heapType == HeapType.Min ^ elem1 < elem2;
		}
		
		private static int Parent(int i)
		{
			
			return (i+1) /2 - 1;
		}
		
		private static int Left(int i)
		{
			return 2 * i + 1;
		}
		
		private static int Right(int i)
		{
			return 2 * i + 2;
		}
	}
	
	public enum HeapType
	{
		Min,
		Max
	}

My method uses two heaps:
1. Max heap to track values less than the median
2. Min heap to track values greater than the median

Inserting n
1. If no median, assign n as median
Else
2a. If n >= median, push onto min heap
2b. If n < median, push onto max heap
3. Balance the heaps. Whichever heap is larger;
3a. Push median onto the *other* heap
3b. Pop from the larger heap, assign as median

Note that the behaviour is undefined if the n is even, but I think that's a given from the task?

Performance:
Insert: O(log n) => requires two heap insert operations, heaps are not "full size". I believe it's satisfactory to state that it's in the order of log n?
Get median: O(1)
Space: O(n)

Written is my slightly amateur Ruby :)

require 'algorithms'

class Median
	@min_heap
	@max_heap
	@median

	def initialize
		@min_heap = Containers::MinHeap.new
		@max_heap = Containers::MaxHeap.new	
	end

	def median
		@median
	end

	def add(number)
		if @median.nil?
			@median = number
		else
			if number >= @median
				@min_heap.push(number)
			elsif number < @median
				@max_heap.push(number)
			end

			if @min_heap.size > @max_heap.size
				@max_heap.push(@median)
				@median = @min_heap.pop
			elsif @max_heap.size > @min_heap.size
				@min_heap.push(@median)
				@median = @max_heap.pop
			end
		end

		@median
	end
	alias_method :<<, :add
end

All that is needed it to maintain 4 numbers. The numbers required are - the smallest, left middle, right middle and the largest

sm            lm            rm            lg

public class Median {
   int nums[4] = { -1, -1, -1, -1 };
   int sm = 0, lm = 1, rm = 2, lg = 3;
   int leftCount = 0, rightCount = 0;
   
   public static void add (int n) {
      // insert first four numbers in sorted order
      if (leftCount == 0) { // no number yet
       ...
      }
      if (leftCount + rightCount == 1) { // 2nd number
       ...
      }
      if (leftCount + rightCount == 2) { // insert 3rd }
      if (leftCount + rightCount == 3) { // insert 4th }
      
      // all other inserts
      if (n <= nums[sm]) { nums[sm] = n; leftCount++; return; }
      if (n <= nums[rm]) { leftCount++; return; }
      if (n >= nums[lg]) { nums[lg] = n; rightCount++; return; }
      if (n >= nums[rm]) { rightCount++; return; }
      
      if (n > nums[lm] && n < nums[lm]) {
         if (leftCount > rightCount) { // insert left or right whichever is smaller
            nums[rm] = n; rightCount ++; return;
         } else {
            nums[lm] = n; leftCount++; return;
         }
      }
   }
   
   public int median() {
      if (leftCount > rightCount) return num[lm];
      if (rightCount > leftCount) return num[rm];
      return (num[lm] + num[rm]) / 2;
   }
}

#import "SampleHandler.h"

@interface SampleHandler()

@property (nonatomic) NSMutableArray<NSNumber*> *backingArray;

@end

@implementation SampleHandler


- (NSMutableArray*)backingArray {

if (!_backingArray) {
_backingArray = [[NSMutableArray alloc] init];
}

return _backingArray;
}

- (void)addNumber:(NSNumber*)number1 {

[self.backingArray insertObject:number1 atIndex:0];
self.backingArray = [[self.backingArray sortedArrayUsingSelector:@selector(compare:)] mutableCopy];

}
- (NSNumber*)median {

NSNumber *median = nil;
NSUInteger numberOfElements = self.backingArray.count;
NSUInteger halfOfElementsCount = numberOfElements / 2;

if (numberOfElements % 2 == 0) {
median = @(([self.backingArray[halfOfElementsCount - 1] integerValue] + [self.backingArray[halfOfElementsCount] integerValue])/2);
}
else {
median = self.backingArray[halfOfElementsCount];
}

return median;
}

@end

#import "SampleHandler.h"

@interface SampleHandler()

@property (nonatomic) NSMutableArray<NSNumber*> *backingArray;

@end

@implementation SampleHandler


- (NSMutableArray*)backingArray {
   
    if (!_backingArray) {
        _backingArray = [[NSMutableArray alloc] init];
    }
    
    return _backingArray;
}

- (void)addNumber:(NSNumber*)number1 {
    
    [self.backingArray insertObject:number1 atIndex:0];
    self.backingArray = [[self.backingArray sortedArrayUsingSelector:@selector(compare:)] mutableCopy];
    
}
- (NSNumber*)median {
    
    NSNumber *median = nil;
    NSUInteger numberOfElements = self.backingArray.count;
    NSUInteger halfOfElementsCount = numberOfElements / 2;
    
    if (numberOfElements % 2 == 0) {
        median = @(([self.backingArray[halfOfElementsCount - 1] integerValue] + [self.backingArray[halfOfElementsCount] integerValue])/2);
    }
    else {
        median = self.backingArray[halfOfElementsCount];
    }
    
    return median;
}

@end

@property (strong, nonatomic) NSMutableArray *numberArray;

-(void)addNumber:(NSNumber*)number{
	if(self.numberArray == nil){
		self.numberArray = [NSMutableArray new];
		[self.numberArray addObject: number];
		return;
	}
	int max = [self.numberArray count]-1;
	int min = 0;
	int middle;
	while(min =< max){
		middle = (min + max)/2;
		if(number < [self.numberArray objectAtIndex:middle]){
			max = middle-1;
		}
		else if(number > [self.numberArray objectAtIndex:middle]){
			min = middle+1;
		}
	}
	[self.numberArray addObject: number at Index: middle];
}



-(NSNumber*)median{
	if(self.numberArray == nil){
		return nil;
	}
	int max = [self.numberArray count]-1;
	int min = 0;
	int middle = (max + min)/2;
	return [self.numberArray objectAtIndex:middle];
}

@property (strong, nonatomic) NSMutableArray *numberArray;

-(void)addNumber:(NSNumber*)number{
	if(self.numberArray == nil){
		self.numberArray = [NSMutableArray new];
		[self.numberArray addObject: number];
		return;
	}
	int max = [self.numberArray count]-1;
	int min = 0;
	int middle;
	while(min =< max){
		middle = (min + max)/2;
		if(number < [self.numberArray objectAtIndex:middle]){
			max = middle-1;
		}
		else if(number > [self.numberArray objectAtIndex:middle]){
			min = middle+1;
		}
	}
	[self.numberArray addObject: number at Index: middle];
}



-(NSNumber*)median{
	if(self.numberArray == nil){
		return nil;
	}
	int max = [self.numberArray count]-1;
	int min = 0;
	int middle = (max + min)/2;
	return [self.numberArray objectAtIndex:middle];
}

@property (strong, nonatomic) NSMutableArray *numberArray;

-(void)addNumber:(NSNumber*)number{
	if(self.numberArray == nil){
		self.numberArray = [NSMutableArray new];
		[self.numberArray addObject: number];
		return;
	}
	int max = [self.numberArray count]-1;
	int min = 0;
	int middle;
	while(min =< max){
		middle = (min + max)/2;
		if(number < [self.numberArray objectAtIndex:middle]){
			max = middle-1;
		}
		else if(number > [self.numberArray objectAtIndex:middle]){
			min = middle+1;
		}
	}
	[self.numberArray addObject: number at Index: middle];
}



-(NSNumber*)median{
	if(self.numberArray == nil){
		return nil;
	}
	int max = [self.numberArray count]-1;
	int min = 0;
	int middle = (max + min)/2;
	return [self.numberArray objectAtIndex:middle];

}

My answer involves maintaining two sorted arrays: one for numbers less than the current median, and one for numbers greater than the current median. The current median can always be calculated thusly:

1. If the number of elements less than the median are equal to the number of elements greater than the median, the median is the average of the largest less-than element and the smallest greater-than element.
2. If the number of elements less than the median is greater than the number of elements greater than, the median is the largest less-than element.
3. If the number of elements greater than the median is greater than the number of elements less than, the median is the smallest greater-than element.

However, it is important to "balance" the two arrays; their lengths must never differ by more than one.

The code is separated into three files:

1. `NSNumber+CCPAverage` provides methods to average an array of `NSNumber` instances.
2. `CCPSortedCollection` provides a collection class that remains sorted as elements are added.
3. `CCPNumberStreamHandler` parses a stream of numbers and provides a median.

Adding an element is `O(log n)`. Finding the median is `O(1)`.

// NSNumber+CCPAverage.h

#import <Foundation/Foundation.h>

@interface NSNumber (CCPAverage)

/**
 Returns the average of an array of numbers. Raises an exception if the array
 is nil or empty. Complexity is O(n).
 */
+ (NSNumber *)ccp_average:(NSArray *)numbers;

@end

// NSNumber+CCPAverage.m

#import "NSNumber+CCPAverage.h"

@implementation NSNumber (CCPAverage)

#pragma mark - Public Interface

+ (NSNumber *)ccp_average:(NSArray *)numbers {
    NSParameterAssert(numbers != nil);
    NSParameterAssert([numbers count] > 0);

    double sum = 0;
    for (NSNumber *number in numbers) {
        sum += [number doubleValue];
    }

    return @(sum/[numbers count]);
}

@end

// NSNumber+CCPAverageSpec.m

#import <Kiwi/Kiwi.h>
#import "NSNumber+CCPAverage.h"

SPEC_BEGIN(NSNumber_CCPAverageSpec)

describe(@"NSNumber (CCPAverage)", ^{
    __block NSArray *numbers = nil;

    describe(@"+ccp_average:", ^{
        describe(@"when the array is nil", ^{
            beforeEach(^{
                numbers = nil;
            });

            it(@"raises", ^{
                [[theBlock(^{
                    [NSNumber ccp_average:numbers];
                }) should] raise];
            });
        });

        describe(@"when the array is empty", ^{
            beforeEach(^{
                numbers = @[];
            });

            it(@"raises", ^{
                [[theBlock(^{
                    [NSNumber ccp_average:numbers];
                }) should] raise];
            });
        });

        describe(@"when the array contains numbers", ^{
            it(@"returns the average", ^{
                [[[NSNumber ccp_average:@[@1]] should] equal:@1];
                [[[NSNumber ccp_average:@[@1, @2]] should] equal:@1.5];
                [[[NSNumber ccp_average:@[@1, @2, @3]] should] equal:@2];
            });
        });
    });
});

SPEC_END

// CCPSortedCollection.h

#import <Foundation/Foundation.h>

@interface CCPSortedCollection : NSObject

/** The smallest object in the collection. Complexity is O(1). */
@property (nonatomic, readonly) id minimum;

/** The largest object in the collection. Complexity is O(1). */
@property (nonatomic, readonly) id maximum;

/**
 Returns the number of elements in the colleciton. Complexity is equivalent to
 -[NSMutableArray count], which is probably O(1).
 */
@property (nonatomic, readonly) NSUInteger count;

/**
 Designated initializer. The comparator argument is used to compare
 elements as they are inserted, thereby determining their position in
 the collection.
 */
- (instancetype)initWithComparator:(NSComparator)comparator;

/** Adds an object to a sorted collection. Complexity is O(log n). */
- (void)addObject:(id)object;

/** Removes the minimum from the collection and returns it. Complexity is equivalent to -minimum. */
- (id)popMinimum;

/** Removes the maximum from the collection and returns it. Complexity is equivalent to -maximum. */
- (id)popMaximum;

@end

// CCPSortedCollection.m

#import "CCPSortedCollection.h"

@interface CCPSortedCollection ()
@property (nonatomic, assign) NSComparator comparator;
@property (nonatomic, strong) NSMutableArray *elements;
@end

@implementation CCPSortedCollection

#pragma mark - Object Lifecycle

- (instancetype)initWithComparator:(NSComparator)comparator {
    NSParameterAssert(comparator != nil);
    self = [super init];
    if (self) {
        _comparator = comparator;
        _elements = [NSMutableArray array];
    }
    return self;
}

#pragma mark - Public Interface

- (NSUInteger)count {
    return [self.elements count];
}

- (id)minimum {
    return [self.elements firstObject];
}

- (id)maximum {
    return [self.elements lastObject];
}

- (void)addObject:(id)object {
    NSComparisonResult result = NSOrderedSame;
    NSUInteger location = 0;
    NSUInteger length = self.count;

    while (length > 0) {
        // Grab the pivot at approximately the middle of the array.
        NSUInteger pivotLocation = location + length/2;
        id pivot = self.elements[pivotLocation];

        // Compare the to-be-inserted object to the pivot.
        result = self.comparator(object, pivot);
        if (result == NSOrderedSame) {
            // If they're equal, no need to keep searching;
            // just insert the object in the pivot location.
            // It doesn't matter whether it's inserted before or after.
            location = pivotLocation;
            break;
        } else if (result == NSOrderedAscending) {
            // If the object is less than the pivot, then search
            // only the first half of the array--in other words,
            // location stays the same, but length is halved.
            length /= 2;
        } else {
            // If the object is greater than the pivot, search
            // the second half of the array.
            length /= 2;
            location += length;
        }
    }

    // -[NSMutableArray insertObject:atIndex:] inserts an object at the
    // index, moving all other to the right. If our object is greater,
    // we want to insert at index + 1. The following code is made uglier
    // by bounds checking.
    if (result == NSOrderedDescending) {
        location += 1;
        if (location < self.count) {
            [self.elements insertObject:object atIndex:location];
        } else {
            [self.elements addObject:object];
        }
    } else {
        [self.elements insertObject:object atIndex:location];
    }
}

- (id)popMinimum {
    id minima = self.minimum;
    [self.elements removeObjectAtIndex:0];
    return minima;
}

- (id)popMaximum {
    id maxima = self.maximum;
    [self.elements removeObjectAtIndex:self.count - 1];
    return maxima;
}

@end

// CCPSortedCollectionSpec.m

#import <Kiwi/Kiwi.h>
#import "CCPSortedCollection.h"

SPEC_BEGIN(CCPSortedCollectionSpec)

describe(@"CCPSortedCollection", ^{
    __block CCPSortedCollection *collection = nil;
    beforeEach(^{
        collection = [[CCPSortedCollection alloc] initWithComparator:^NSComparisonResult(NSNumber *number, NSNumber *pivot) {
            return [number compare:pivot];
        }];
    });

    describe(@"-minimum", ^{
        context(@"when the collection is empty", ^{
            it(@"returns nil", ^{
                [[[collection minimum] should] beNil];
            });
        });

        context(@"when the collection is not empty", ^{
            it(@"returns the smallest element in the collection", ^{
                [collection addObject:@11];
                [[[collection minimum] should] equal:@11];

                [collection addObject:@2];
                [[[collection minimum] should] equal:@2];

                [collection addObject:@3];
                [[[collection minimum] should] equal:@2];

                [collection addObject:@11];
                [[[collection minimum] should] equal:@2];

                [collection addObject:@23];
                [[[collection minimum] should] equal:@2];

                [collection addObject:@(-10)];
                [[[collection minimum] should] equal:@(-10)];

                [collection addObject:@(-12)];
                [[[collection minimum] should] equal:@(-12)];
            });
        });
    });

    describe(@"-popMinimum", ^{
        it(@"pops the minimum element", ^{
            [collection addObject:@10];
            [collection addObject:@5];

            [[[collection popMinimum] should] equal:@5];
            [[[collection popMinimum] should] equal:@10];
            [[theBlock(^{
                [collection popMinimum];
            }) should] raiseWithName:NSRangeException];
        });
    });

    describe(@"-maximum", ^{
        context(@"when the collection is empty", ^{
            it(@"returns nil", ^{
                [[[collection maximum] should] beNil];
            });
        });

        context(@"when the collection is not empty", ^{
            it(@"returns the largest element in the collection", ^{
                [collection addObject:@11];
                [[[collection maximum] should] equal:@11];

                [collection addObject:@2];
                [[[collection maximum] should] equal:@11];

                [collection addObject:@3];
                [[[collection maximum] should] equal:@11];

                [collection addObject:@11];
                [[[collection maximum] should] equal:@11];

                [collection addObject:@23];
                [[[collection maximum] should] equal:@23];

                [collection addObject:@(-10)];
                [[[collection maximum] should] equal:@23];

                [collection addObject:@(-12)];
                [[[collection maximum] should] equal:@23];
            });
        });
    });

    describe(@"-popMaximum", ^{
        it(@"pops the minimum element", ^{
            [collection addObject:@10];
            [collection addObject:@5];

            [[[collection popMaximum] should] equal:@10];
            [[[collection popMaximum] should] equal:@5];
            [[theBlock(^{
                [collection popMaximum];
            }) should] raiseWithName:NSRangeException];
        });
    });
});

SPEC_END

// CCPNumberStreamHandler.h

#import <Foundation/Foundation.h>

@interface CCPNumberStreamHandler : NSObject

/** The median of the series. Returns nil if the series is empty. Complexity is O(1). */
@property (nonatomic, readonly) NSNumber *median;

/** Add a number to the series. Complexity is equivalent to -[CCPSortedCollection addObject:]. */
- (void)addNumber:(NSNumber *)number;

@end

// CCPNumberStreamHandler.m

#import "CCPNumberStreamHandler.h"
#import "CCPSortedCollection.h"
#import "NSNumber+CCPAverage.h"

@interface CCPNumberStreamHandler ()
@property (nonatomic, strong) CCPSortedCollection *less;
@property (nonatomic, strong) CCPSortedCollection *greater;
@end

@implementation CCPNumberStreamHandler

#pragma mark - Object Lifecycle

- (instancetype)init {
    self = [super init];
    if (self) {
        NSComparator comparator = ^NSComparisonResult(NSNumber *number, NSNumber *pivot) {
            return [number compare:pivot];
        };
        _less = [[CCPSortedCollection alloc] initWithComparator:comparator];
        _greater = [[CCPSortedCollection alloc] initWithComparator:comparator];
    }
    return self;
}

#pragma mark - Public Interface

- (void)addNumber:(NSNumber *)number {
    if (self.median && [number compare:self.median] == NSOrderedDescending) {
        [self.greater addObject:number];
    } else {
        [self.less addObject:number];
    }

    [self balanceCollections];
}

- (NSNumber *)median {
    NSUInteger lessCount = [self.less count];
    NSUInteger greaterCount = [self.greater count];

    if (lessCount == 0 && greaterCount == 0) {
        return nil;
    }

    if (lessCount == greaterCount) {
        return [NSNumber ccp_average:@[self.less.maximum, self.greater.minimum]];
    } else if (lessCount > greaterCount) {
        return self.less.maximum;
    } else {
        return self.greater.minimum;
    }
}

#pragma mark - Internal Methods

- (void)balanceCollections {
    NSUInteger lessCount = [self.less count];
    NSUInteger greaterCount = [self.greater count];

    if (lessCount > greaterCount + 1) {
        [self.greater addObject:[self.less popMaximum]];
    } else if (greaterCount > lessCount + 1) {
        [self.less addObject:[self.greater popMinimum]];
    }
}

@end

// CCPNumberStreamHandlerSpec.m

#import <Kiwi/Kiwi.h>
#import "CCPNumberStreamHandler.h"

SPEC_BEGIN(CCPNumberStreamHandlerSpec)

describe(@"CCPNumberStreamHandler", ^{
    __block CCPNumberStreamHandler *handler = nil;
    beforeEach(^{
        handler = [CCPNumberStreamHandler new];
    });

    describe(@"-median", ^{
        context(@"when the store is empty", ^{
            it(@"returns nil", ^{
                [[handler.median should] beNil];
            });
        });

        context(@"when the store is not empty", ^{
            it(@"returns the median", ^{
                [handler addNumber:@1];
                [[handler.median should] equal:@1];

                [handler addNumber:@2];
                [[handler.median should] equal:@1.5];

                [handler addNumber:@10];
                [[handler.median should] equal:@2];

                [handler addNumber:@(-10)];
                [[handler.median should] equal:@1.5];

                [handler addNumber:@(-20)];
                [[handler.median should] equal:@1];

                [handler addNumber:@(-40)];

                [[handler.median should] equal:@(-4.5)];
            });
        });
    });
});

SPEC_END