## Facebook Interview Question for iOS Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
13
of 13 vote

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.

Comment hidden because of low score. Click to expand.
0

not sure this works. if you are inserting only elements less than the root in the max heap and only elements greater than the root in the min heap, the heap roots will never change and your median would always be the median of the first two values you inserted in the heaps

Comment hidden because of low score. Click to expand.
0

Look at step 3:
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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/bin/bash

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 balanceArrayWithAscendingOrder:NO];
} else {
[_minHeap balanceArrayWithAscendingOrder:YES];
}
[self balanceArrays];
}

- (void)balanceArrays {
NSInteger maxHeapCount = [_maxHeap count];
NSInteger minHeapCount = [_minHeap count];
if (abs((int)(maxHeapCount - minHeapCount)) > 1) {
if (maxHeapCount > minHeapCount) {
[_maxHeap removeObjectAtIndex:0];
} else {
[_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) {
return [NSNumber numberWithDouble:result];
} else {
return (maxHeapCount > minHeapCount)?
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

{
}

- (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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my answer:

``````#import <Foundation/Foundation.h>

@interface CXAMedian: NSObject

- (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;
}

{
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];
NSLog(@"median of %@ is: %@", m, [m median]);
return 0;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
{
}

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);
}

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
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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
end``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#import "SampleHandler.h"

@interface SampleHandler()

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

@end

@implementation SampleHandler

- (NSMutableArray*)backingArray {

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

return _backingArray;
}

[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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#import "SampleHandler.h"

@interface SampleHandler()

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

@end

@implementation SampleHandler

- (NSMutableArray*)backingArray {

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

return _backingArray;
}

[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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````@property (strong, nonatomic) NSMutableArray *numberArray;

if(self.numberArray == nil){
self.numberArray = [NSMutableArray new];
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];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````@property (strong, nonatomic) NSMutableArray *numberArray;

if(self.numberArray == nil){
self.numberArray = [NSMutableArray new];
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];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````@property (strong, nonatomic) NSMutableArray *numberArray;

if(self.numberArray == nil){
self.numberArray = [NSMutableArray new];
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];``````

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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). */

/** 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];
}

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 {
}
} 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 minimum] should] equal:@11];

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

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

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

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

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

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

describe(@"-popMinimum", ^{
it(@"pops the minimum element", ^{

[[[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 maximum] should] equal:@11];

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

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

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

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

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

[[[collection maximum] should] equal:@23];
});
});
});

describe(@"-popMaximum", ^{
it(@"pops the minimum element", ^{

[[[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:]. */

@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) {
} else {
}

[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) {
} else if (greaterCount > lessCount + 1) {
}
}

@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.median should] equal:@1];

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

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

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

[[handler.median should] equal:@1];

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

SPEC_END``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

the answer is this big? I doubt... it can be done in under 30 minutes.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.