David.norman.w
BAN USERI used a custom hash table that would return false if the hash of a sorted string already existed in the hash table.
+(void)test {
NSLog(@"Anagrams in array?: %hhd", [self anagramsInArray:@[@"cat", @"cta", @"dog"]]);
}
+(BOOL)anagramsInArray:(NSArray*)array {
if (array.count < 1 || array == nil) {
return false;
}
HashTable *hashTable = [HashTable new];
for (id possibleString in array) {
if ([possibleString isKindOfClass:[NSString class]]) {
NSString *str = (NSString*)possibleString;
if (![hashTable tryAddingUniqueValue:[str sortAscending] ForKey:[str sortAscending]]) {
return true;
}
}
}
return false;
}
+(NSArray*)stringToArray:(NSString*)string {
NSMutableArray *mutableStringArray = [NSMutableArray new];
for (int i = 0; i < [string length]; i++ ) {
[mutableStringArray addObject:[NSString stringWithFormat:@"%c",[string characterAtIndex:i]]];
}
return mutableStringArray.copy;
}
I used a depth first traversal of an AVL Tree to recursively create a sorted array of all node keys. Using this array It was a simple matter of writing a method to find the mean of a sorted array (findMedianOfArray:_)
//Traverse the AVL Tree and keep track of node keys in the mutable array
-(double)findMedian:(AVLTreeNode*)node array:(NSMutableArray*)array {
if (node != nil) {
[self findMedian:node.left array:array];
[array addObject:[NSNumber numberWithInteger:node.key]];
[self findMedian:node.right array:array];
}
return [self findMedianOfArray:array.copy];
}
-(double)findMedianOfArray:(NSArray*)array {
NSNumber *medianNumber = @0;
if (array.count == 0) {
return 0;
}
if (array.count == 1) {
id medianObject = array.firstObject;
if ([medianObject isKindOfClass:[NSNumber class]]) {
return ((NSNumber*)medianObject).integerValue;
}
}
if (array.count % 2 == 1) { // is even
NSInteger medianIndex = (array.count / 2);
id medianObject = array[medianIndex];
if ([medianObject isKindOfClass:[NSNumber class]]) {
medianNumber = medianObject;
}
} else { //is odd
NSInteger medianIndex = (array.count / 2);
id medianObjectA = array[medianIndex];
id medianObjectB = array[medianIndex - 1];
if ([medianObjectA isKindOfClass:[NSNumber class]] && [medianObjectB isKindOfClass:[NSNumber class]]) {
medianNumber = [NSNumber numberWithDouble:(((NSNumber*)medianObjectA).doubleValue + ((NSNumber*)medianObjectB).doubleValue) / 2.0];
}
}
return medianNumber.doubleValue;
}
I used a combination of a couple of the top answers to come up with this solution.
-(NSArray*)findWordWithWildCard:(TrieNode*)node word:(NSString*)searchWord {
NSMutableArray *finalArray = [NSMutableArray new];
searchWord = [searchWord stringByReplacingOccurrencesOfString:@"." withString:@"*"];
if (searchWord.length <= 0) {
return nil;
}
while (searchWord.length != node.level) {
NSString *searchKey = [searchWord substringToIndex:node.level + 1];
for (TrieNode* childToUse in node.children) {
NSString *result = [self node:childToUse containsSimilarString:searchKey];
if (result != nil) {
node = childToUse;
NSString *matchingWord = [self node:node containsSimilarString:searchWord];
if (matchingWord != nil) {
[finalArray addObject:matchingWord];
}
NSArray *resultsArray = [self findWordWithWildCard:node word:searchWord];
if (resultsArray != nil) {
[finalArray addObjectsFromArray:resultsArray];
}
}
}
}
return finalArray;
}
-(NSString*)node:(TrieNode*)node containsSimilarString:searchString {
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"self like %@", searchString];
NSArray *resultArray = [@[node.key] filteredArrayUsingPredicate:predicate];
if (resultArray.count > 0) {
return resultArray.firstObject;
}
return nil;
}
In Objective-C:
+(void)printWithConsecutiveSegmentsInSortedArray:(NSArray*)sortedArray {
if (![sortedArray.lastObject isKindOfClass:[NSNumber class]]) {
return;
}
NSMutableArray *finalArray = [NSMutableArray new];
NSNumber *lastNumberInRun;
for (int i = 0; i < [sortedArray count]; i++) {
NSNumber *numberItem = sortedArray[i];
if (finalArray.lastObject == nil) {
[finalArray addObject:numberItem.stringValue];
continue;
}
if (lastNumberInRun == nil) {
if (((NSString*)finalArray.lastObject).integerValue + 1 == numberItem.integerValue) {
lastNumberInRun = numberItem;
if (i == [sortedArray count] - 1) {
if (lastNumberInRun != nil) {
[finalArray addObject:[NSString stringWithFormat:@"-%@", lastNumberInRun]];
}
}
continue;
}
[finalArray addObject:numberItem.stringValue];
} else {
if (lastNumberInRun.integerValue + 1 == numberItem.integerValue ) {
lastNumberInRun = numberItem;
if (i == [sortedArray count] - 1) {
if (lastNumberInRun != nil) {
[finalArray addObject:[NSString stringWithFormat:@"-%@", lastNumberInRun]];
}
}
continue;
}
[finalArray addObject:[NSString stringWithFormat:@"-%@", lastNumberInRun]];
lastNumberInRun = nil;
[finalArray addObject:numberItem.stringValue];
}
}
NSLog(@"%@", [finalArray componentsJoinedByString:@","]);
}
//
// MiscQuestions.m
// CrackingTheCodingInterview-objc
//
// Created by David Norman on 4/24/16.
//
#import "MiscQuestions.h"
#import "Island.h"
@implementation MiscQuestions
+(void)testRun {
NSArray* mapArray = @[
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"X", @"X", @"X"],
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"X", @"X", @"X"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"X", @"X"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"O", @"O", @"O", @"O", @"X", @"X", @"O", @"O", @"X", @"O"],
@[@"O", @"O", @"O", @"O", @"X", @"X", @"O", @"O", @"X", @"O"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"],
@[@"X", @"X", @"O", @"O", @"O", @"O", @"O", @"O", @"O", @"O"]];
[self findIslandsInMapArrays:mapArray];
}
+(void)findIslandsInMapArrays:(NSArray*)mapArrayY {
NSMutableArray* islandArray = [NSMutableArray new];
NSIndexSet *indexArraySet = [NSIndexSet new];
NSMutableArray *outerIndexArray = [NSMutableArray new];
for ( int i = 0; i < [mapArrayY count]; i++) {
indexArraySet = [mapArrayY[i] indexesOfObjectsPassingTest:^BOOL(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
return [obj isEqual: @"X"];
}];
NSMutableArray *indexArray = [NSMutableArray new];
[indexArraySet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL * _Nonnull stop) {
[indexArray addObject:[NSNumber numberWithInteger:idx]];
}];
if (indexArray != nil) {
[outerIndexArray addObject:indexArray];
} else {
[outerIndexArray addObject:[NSArray new]];
}
}
for (int j = 0; j < [outerIndexArray count]; j++) {
NSArray *innerIndexArray = outerIndexArray[j];
NSLog(@"innerIndexArray: %@", innerIndexArray);
for (int i = 0; i < [innerIndexArray count]; i++) {
NSNumber *xcoord = innerIndexArray[i];
if ( xcoord != nil ) {
NSPoint coordValue = NSMakePoint(xcoord.integerValue, j);
BOOL foundIsland = false;
//check new coord in all all islands
for (Island *island in islandArray) {
foundIsland = [island addPointIfWithinDistance:coordValue];
if (foundIsland) {
break;
}
}
if (!foundIsland) {
[islandArray addObject:[Island new]];
[((Island*)islandArray.lastObject).edgesArray addObject:[NSValue valueWithPoint:coordValue]];
}
}
}
}
NSLog(@"Island Array COUNT: %lu", (unsigned long)islandArray.count);
}
@end
//
// Island.m
// CrackingTheCodingInterview-objc
//
// Created by David Norman on 4/24/16.
//
#import "Island.h"
@implementation Island
- (instancetype)init
{
self = [super init];
if (self) {
self.edgesArray = [NSMutableArray new];
}
return self;
}
-(BOOL)addPointIfWithinDistance:(NSPoint)point {
BOOL result = false;
for (int i = 0; i < [self.edgesArray count]; i++) {
NSNumber *edge = self.edgesArray[i];
NSPoint islandPoint = edge.pointValue;
if (fabs(islandPoint.x - point.x) <= 1 && fabs(islandPoint.y - point.y) <= 1) {
[self.edgesArray addObject:[NSValue valueWithPoint:point]];
return true;
}
}
return result;
}
-(NSString *)description {
return self.edgesArray.description;
}
@end
- David.norman.w May 22, 2016