mdc
BAN USERThe naive solution would be to split the string, then reverse each substring. Many responses claim this is `O(n)`, but this is incorrect. Splitting the string is `O(n)`. Reversing a string is `O(n)`. If a split produces `m` substrings, each of them must be reversed, which is `O(mn)`, or `O(n^2)`.
A more efficient solution is as follows:
1. Initialize `reversed`, an empty, mutable string, and `reversedIndex`, the index at which we will insert characters into the reversed string.
2. Iterate over the original string in reverse order.
3. For each character in the original string, check whether it is whitespace.
3a. If it is, put it at the beginning of `reversed`, and reset `reversedIndex` to 0.
3b. If it is not, insert it into `reversed` at the `reversedIndex`. Then increment `reversedIndex`.
Objective-C code follows:
NSString *reversedWords(NSString *string) {
NSUInteger reversedIndex = 0;
NSMutableString *reversed = [NSMutableString string];
for (NSInteger i = [string length] - 1; i >= 0; --i) {
NSString *character = [string substringWithRange:NSMakeRange(i, 1)];
if ([character isEqualToString:@" "]) {
reversed = [NSMutableString stringWithFormat:@"%@%@", character, reversed];
reversedIndex = 0;
} else {
[reversed insertString:character atIndex:reversedIndex++];
}
}
return [reversed copy];
}
And here is the test:
- (void)testReversedWords {
NSString *reversed = cup_reversedWords(@"the boy ran");
XCTAssertEqualObjects(reversed, @"eht yob nar", @"");
reversed = cup_reversedWords(@"");
XCTAssertEqualObjects(reversed, @"", @"");
reversed = cup_reversedWords(@" ");
XCTAssertEqualObjects(reversed, @" ", @"");
reversed = cup_reversedWords(@"oneword");
XCTAssertEqualObjects(reversed, @"droweno", @"");
reversed = cup_reversedWords(@"oneword ");
XCTAssertEqualObjects(reversed, @"droweno ", @"");
}
You can improve the readability/maintainability of the code by replacing the call to `-isEqualToString:` with a category method. Also, you could add a method to `NSMutableString` that allows you to prepend a string to `reversed`, instead of using `+stringWithFormat:` like I did.
- mdc June 16, 2014An in-order, depth-first traversal of a binary search tree (which an AVL is by definition) produces a sorted list of all elements in O(n) time. Simply take the middle element of this list in order to retrieve the median.
typedef void (^AVLTreeTraversalBlock)(AVLTree *tree, BOOL *stop);
@implementation AVLTree (CCPMedian)
- (void)ccp_depthFirstInOrderTraversalWithBlock:(AVLTreeTraversalBlock)block {
[self.left ccp_depthFirstInOrderTraversalWithBlock:block];
if (block) {
BOOL stop = NO;
block(self, &stop);
if (stop) {
return;
}
}
[self.right ccp_depthFirstInOrderTraversalWithBlock:block];
}
- (NSNumber *)ccp_median {
__block NSMutableArray *values = [NSMutableArray array];
[self ccp_depthFirstInOrderTraversalWithBlock:^(AVLTree *tree, BOOL *stop){
[values addObject:tree.value];
}];
// Assume we have a method ccp_middleValue that returns
// the middle element of a sorted list, or the mean of the two
// middle values if there are an even number of elements
// (the definition of the median according to Wikipedia).
return [values ccp_middleValue];
}
@end
Some optimizations could be made as well; for example, if the tree maintains a count of its nodes, we could stop our traversal once we reach the middle element (the median).
- mdc May 21, 2014Here's a recursive solution in Objective-C. I believe the complexity is `O(n^2)`, but I'm not sure.
// CCPAddends.h
#import <Foundation/Foundation.h>
/**
Returns a set of sets of numbers that, when added, sum up to n.
n itself is not considered an addend; that is, ccp_addends(4)
will not include any sets containing the number 4.
Therefore, this function returns an empty set when n <= 1.
Complexity is O(n^2).
*/
extern NSSet *ccp_addends(NSUInteger n);
// CCPAddends.m
#import "CCPAddends.h"
#pragma mark - Internal Functions
void mdc_combinationsThatAddUpTo(NSUInteger sum,
NSUInteger n,
NSMutableSet *combinations,
NSMutableSet *combination) {
if (n == 0) {
// If n == 0, there are no additional numbers to
// append to this combination. Therefore, we add
// the combination to the list of combinations,
// then exit. Don't bother adding it if it's empty, though.
if ([combination count] > 0) {
[combinations addObject:[combination copy]];
}
return;
}
// For all i in range [1, n], find combinations that add up to n - i.
for (NSUInteger i = 1; i <= n; ++i) {
if (i != sum) {
// Do *not* include the original sum, since we do not
// consider (sum + 0) to be an addend of sum.
NSMutableSet *newCombination = [combination mutableCopy];
[newCombination addObject:@(i)];
mdc_combinationsThatAddUpTo(sum, n - i, combinations, newCombination);
}
}
}
#pragma mark - Public Interface
NSSet *ccp_addends(NSUInteger n) {
NSMutableSet *combinations = [NSMutableSet set];
NSMutableSet *combination = [NSMutableSet set];
mdc_combinationsThatAddUpTo(n, n, combinations, combination);
return [combinations copy];
}
// CCPAddendsSpec.m
#import <Kiwi/Kiwi.h>
#import "CCPAddends.h"
SPEC_BEGIN(CCPAddendsSpec)
describe(@"mdc_addends", ^{
__block NSUInteger n = 0;
context(@"when n is 0", ^{
beforeEach(^{ n = 0; });
it(@"returns an empty set", ^{
[[ccp_addends(n) should] beEmpty];
});
});
context(@"when n is 1", ^{
beforeEach(^{ n = 1; });
it(@"returns an empty set, since n + 0 does not count as a addend", ^{
[[ccp_addends(n) should] beEmpty];
});
});
context(@"when n is 4", ^{
beforeEach(^{ n = 4; });
it(@"returns a set of all possible addends summing to 4", ^{
NSSet *addends = ccp_addends(4);
[[theValue([addends count]) should] equal:@4];
[[addends should] contain:[NSSet setWithObjects:@1, @1, @1, @1, nil]];
[[addends should] contain:[NSSet setWithObjects:@1, @1, @2, nil]];
[[addends should] contain:[NSSet setWithObjects:@2, @2, nil]];
[[addends should] contain:[NSSet setWithObjects:@1, @3, nil]];
});
});
});
SPEC_END
I forgot to include the test file:
// CCPCodeParserSpec.m
#import <Kiwi/Kiwi.h>
#import "CCPCodeParser.h"
SPEC_BEGIN(CCPCodeParserSpec)
describe(@"CCPCodeParser", ^{
__block CCPCodeParser *parser = nil;
__block NSString *code = nil;
beforeEach(^{
parser = [CCPCodeParser new];
});
describe(@"-parse:", ^{
context(@"when the code is nil", ^{
it(@"raises", ^{
[[theBlock(^{ [parser parse:code]; }) should] raise];
});
});
context(@"when the code is empty", ^{
beforeEach(^{ code = @""; });
it(@"produces no results", ^{
[parser parse:code];
[[parser.results should] beEmpty];
});
});
context(@"when the code is not empty", ^{
context(@"but it contains digits outside of range [1, 26]", ^{
beforeEach(^{ code = @"1020"; });
it(@"raises", ^{
[[theBlock(^{ [parser parse:code]; }) should] raise];
});
});
context(@"and it only contains digits within range [1, 26]", ^{
beforeEach(^{ code = @"1123"; });
it(@"parses the code", ^{
[parser parse:code];
[[theValue([parser.results count]) should] equal:@5];
[[parser.results should] contain:@"aabc"];
[[parser.results should] contain:@"kbc"];
[[parser.results should] contain:@"alc"];
[[parser.results should] contain:@"aaw"];
[[parser.results should] contain:@"kw"];
});
});
});
});
});
SPEC_END
Here's a recursive solution in Objective-C, composed of two classes:
1. `NSString (CCPCharacterCode)` is a category on `NSString` that converts a string between `@"1"` and `@"26"` to a string containing an letter between `@"a"` and `@"z"`.
2. `CCPCodeParser` parses a code and stores the results in a `results` property.
I believe the complexity is `O(n^2)`, but I'm not 100% sure.
// NSString+CCPCharacterCode.h
#import <Foundation/Foundation.h>
@interface NSString (CCPCharacterCode)
/**
Converts a string representing a single- or double-digit integer
to a string representing a character matching that integer,
where a = 1, b = 2, and so on until z = 26.
Raises an exception if code represents an integer outside the
range of [1, 26].
Complexity is O(1).
*/
+ (NSString *)stringWithCharacterCode:(NSString *)code;
@end
// NSString+CCPCharacterCode.m
#import "NSString+CCPCharacterCode.h"
@implementation NSString (CCPCharacterCode)
#pragma mark - Public Interface
+ (NSString *)stringWithCharacterCode:(NSString *)code {
int value = [code intValue];
NSParameterAssert(value >= 1 && value <= 26);
return [NSString stringWithFormat:@"%c", 'a' - 1 + value];
}
@end
// CCPCodeParser.h
#import <Foundation/Foundation.h>
@interface CCPCodeParser : NSObject
/**
The results of one or more calls to -parse:.
If -parse: has not yet been called, or if -parse: has only been
called with an empty strings, this is an empty set.
*/
@property (nonatomic, readonly) NSSet *results;
/**
Parses a code composed of digits within the range [1, 26]
and stores the results in -results.
Raises an exception if code is nil, or if it contains digits
outside of the range [1, 26].
Complexity is O(n^2).
*/
- (void)parse:(NSString *)code;
@end
// CCPCodeParser.m
#import "CCPCodeParser.h"
#import "NSString+CCPCharacterCode.h"
@interface CCPCodeParser ()
@property (nonatomic, strong) NSMutableSet *parsed;
@end
@implementation CCPCodeParser
#pragma mark - Object Lifecycle
- (instancetype)init {
self = [super init];
if (self) {
_parsed = [NSMutableSet set];
}
return self;
}
#pragma mark - Public Interface
- (NSSet *)results {
return [self.parsed copy];
}
- (void)parse:(NSString *)code {
NSParameterAssert(code != nil);
[self parse:code prefix:@""];
}
#pragma mark - Internal Methods
- (void)parse:(NSString *)code prefix:(NSString *)prefix {
if ([code length] >= 2) {
[self parseTwoDigitsIfValidCode:code prefix:prefix];
[self parseOneDigit:code prefix:prefix];
} else if ([code length] == 1) {
[self parseOneDigit:code prefix:prefix];
} else if ([prefix length] > 0) {
[self.parsed addObject:prefix];
}
}
- (void)parseOneDigit:(NSString *)code prefix:(NSString *)prefix {
NSString *digit = [code substringWithRange:NSMakeRange(0, 1)];
prefix = [NSString stringWithFormat:@"%@%@", prefix, [NSString stringWithCharacterCode:digit]];
[self parse:[code substringFromIndex:1] prefix:prefix];
}
- (void)parseTwoDigitsIfValidCode:(NSString *)code prefix:(NSString *)prefix {
NSString *digits = [code substringWithRange:NSMakeRange(0, 2)];
if ([digits intValue] <= 26) {
prefix = [NSString stringWithFormat:@"%@%@", prefix, [NSString stringWithCharacterCode:digits]];
[self parse:[code substringFromIndex:2] prefix:prefix];
}
}
@end
Here's a recursive solution in Objective-C, with a complexity of `O(n)`, where `n` is the number of characters in the string.
// KPalindrome.h
#import <Foundation/Foundation.h>
/**
Determines whether string is a k-palindrome (case-sensitive, whitespace counts).
Raises if string is nil. Returns YES for empty or one-character strings.
Complexity: O(n), where n is the number of characters in string.
*/
extern BOOL ccp_isKPalindrome(NSString *string, NSUInteger k);
// KPalindrome.m
#import "KPalindrome.h"
extern BOOL ccp_isKPalindrome(NSString *string, NSUInteger k) {
if (string == nil) {
// Raise if string is nil.
[NSException raise:NSInvalidArgumentException
format:@"string cannot be nil"];
} else if ([string length] <= 1) {
// Return YES if string is empty "" or one character "a",
// as it most certainly is the same backwards and forwards.
return YES;
}
// Split the string into two halves, then reverse the second half.
// If the string is an odd number of characters, the second half will be longer.
NSUInteger middle = [string length]/2;
NSString *front = [string substringToIndex:middle];
NSString *back = [string substringFromIndex:middle];
for (NSUInteger i = 0; i < [front length]; ++i) {
// Iterate over each character of the front and back strings.
NSRange frontRange = NSMakeRange(i, 1);
NSRange backRange = NSMakeRange([back length] - 1 - i, 1);
NSString *frontCharacter = [front substringWithRange:frontRange];
NSString *backCharacter = [back substringWithRange:backRange];
if ([frontCharacter compare:backCharacter] != NSOrderedSame) {
if (k == 0) {
// If they're not the same, and we can no longer remove any
// characters, then game over: these are not palindromes.
return NO;
} else {
// If we *can* remove a character, do so and try again.
NSMutableString *newBack = [back mutableCopy];
[newBack deleteCharactersInRange:backRange];
return ccp_isKPalindrome([NSString stringWithFormat:@"%@%@", front, newBack],
k - 1);
}
}
}
// If we've iterated over each character and haven't exceeded our allotment
// of removable characters, we have two k-palindromes.
return YES;
}
// KPalindromeSpec.m
#import <Kiwi/Kiwi.h>
#import "KPalindrome.h"
SPEC_BEGIN(KPalindromeSpec)
describe(@"mdc_isKPalindrome", ^{
context(@"when the string is nil", ^{
it(@"raises", ^{
[[theBlock(^{ ccp_isKPalindrome(nil, 0); }) should] raise];
});
});
context(@"when the string is empty", ^{
it(@"returns YES", ^{
[[theValue(ccp_isKPalindrome(@"", 0)) should] beYes];
});
});
context(@"when the string is a palindrome", ^{
it(@"returns YES", ^{
[[theValue(ccp_isKPalindrome(@"abccba", 0)) should] beYes];
});
});
context(@"when the string is a k-palindrome", ^{
it(@"returns YES", ^{
[[theValue(ccp_isKPalindrome(@"abxa", 1)) should] beYes];
[[theValue(ccp_isKPalindrome(@"abxaxx", 3)) should] beYes];
});
});
context(@"when the string is not a k-palindrome", ^{
it(@"returns NO", ^{
[[theValue(ccp_isKPalindrome(@"abdxa", 1)) should] beNo];
[[theValue(ccp_isKPalindrome(@"abxaxx", 2)) should] beNo];
});
context(@"and string and k are huge", ^{
__block NSString *string = nil;
__block NSUInteger k = 0;
beforeEach(^{
string = [NSString stringWithContentsOfFile:@"/var/log/system.log"
encoding:NSUTF8StringEncoding
error:nil];
k = 30;
});
it(@"returns NO", ^{
[[theValue(ccp_isKPalindrome(string, k)) should] beNo];
});
});
});
});
SPEC_END
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
Typo: in the tests, it should be `reversedWords`, not `cup_reversedWords`.
- mdc June 16, 2014