crisredfi1
BAN USERI 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];
}
}
I used a custom data structure, which is a trie. I haven't used a dictionary to do the algorithm but an array instead. if we have a dictionary like the question says, we only need to get the keys from the dictionary and treat them as the words we will search for. skipping this step, this is my objective c example.
the initialise word generator method i believe its not necessary for the interview, since we only need to code the algorithm which is, in fact a DFS algorithm.
#import "WordsGenerator.h"
#import "CRTrieStructure.h"
typedef void(^searchBlock)(NSString *word);
@implementation WordsGenerator
- (CRTrieStructure*)hasObject:(NSString *)object inArray:(NSArray *)container {
__block BOOL hasObject = NO;
__block CRTrieStructure *trie;
[container enumerateObjectsUsingBlock:^(CRTrieStructure *obj, NSUInteger idx, BOOL *stop) {
if ([obj.value isEqualToString:object]) {
hasObject = YES;
*stop = YES;
trie = obj;
}
}];
return (hasObject != NO) ? trie : nil;
}
NSMutableSet *visitedDeepNodes;
-(void)deepFirstSearch:(CRTrieStructure *)searchNode
withPattern:(NSArray *)pattern
forWords:(NSString *)words
completitionBlock:(searchBlock)block {
if (!visitedDeepNodes) {
// first time visiting the recursive function. lazy load the container
// and add the first node to it
visitedDeepNodes = [NSMutableSet set];
[visitedDeepNodes addObject:searchNode];
}
for (CRTrieStructure *newNode in searchNode.childs) {
if (![visitedDeepNodes containsObject:newNode]) {
[visitedDeepNodes addObject:newNode];
if ([newNode.value isEqualToString:[pattern firstObject]] ||
[[pattern firstObject] isEqualToString:@"."]) {
NSMutableArray *newPattern = [pattern mutableCopy];
[newPattern removeObjectAtIndex:0];
// [words enumerateObjectsUsingBlock:^(NSString *word, BOOL *stop) {
NSString *newWord = [words stringByAppendingString:newNode.value];
// }];
if ([newNode.childs count] > 0 ) {
// deepFirstSearch(newNode,newPattern,newWords);
[self deepFirstSearch:newNode
withPattern:newPattern
forWords:newWord
completitionBlock:block];
} else {
block(newWord);
// return block... with the value we need.
}
}
}
}
}
- (void)searchChilds:(NSArray *)container fromPattern:(NSString *)pattern {
NSMutableArray *characters = [NSMutableArray array];
[pattern enumerateSubstringsInRange:NSMakeRange(0, pattern.length)
options:NSStringEnumerationByComposedCharacterSequences
usingBlock:^(NSString *substring,
NSRange substringRange,
NSRange enclosingRange,
BOOL *stop) {
[characters addObject:substring];
}];
// now iterate over the container array to DFS the subchilds. do not add them in case index
// pattern is not equal to specific child
CRTrieStructure *object = [self hasObject:characters[0] inArray:container];
NSString *startPattern = characters[0];
[characters removeObjectAtIndex:0];
NSMutableSet *words = [NSMutableSet set];
[self deepFirstSearch:object
withPattern:characters
forWords:startPattern
completitionBlock:^(NSString *word) {
[words addObject:word];
}];
NSLog(@"words are %@", words);
}
- (void)initializeWordGenerator {
// insert code here...
NSArray *words = @[@"cat", @"cut", @"cot", @"cit", @"bat", @"bet"];
NSMutableArray *containerArray = [NSMutableArray array]; // main container
[words enumerateObjectsUsingBlock:^(NSString *word, NSUInteger idx, BOOL *stop) {
__block CRTrieStructure *object;
__block NSMutableArray *trieContainer = containerArray; // check for level
[word enumerateSubstringsInRange:NSMakeRange(0, word.length)
options:NSStringEnumerationByComposedCharacterSequences
usingBlock:^(NSString *substring,
NSRange substringRange,
NSRange enclosingRange,
BOOL *stop) {
if ([trieContainer count] > 0 ) {
object = [self hasObject:substring inArray:trieContainer];
if (object) {
// we have the object, set the trie container child to be
// current trie and continue in case we have more words.
trieContainer = object.childs;
} else {
CRTrieStructure *trie = [[CRTrieStructure alloc]
initWithValue:substring];
[trieContainer addObject:trie]; // add current substring to container.
trieContainer = trie.childs;
}
} else {
// initialize array.
CRTrieStructure *trie = [[CRTrieStructure alloc]
initWithValue:substring];
[trieContainer addObject:trie]; // add current substring to container.
trieContainer = trie.childs;
}
}];
}];
[self searchChilds:containerArray fromPattern:@"b.t"];
}
@end
and the CRTrieStructure part is
@interface CRTrieStructure : NSObject
@property (nonatomic, copy) NSString *value;
@property (nonatomic) NSMutableArray *childs;
- (instancetype)initWithValue:(NSString *)value;
@end
@implementation CRTrieStructure
- (instancetype)initWithValue:(NSString *)value {
self = [super init];
if (self) {
_value = value;
_childs = [NSMutableArray array];
}
return self;
}
@end
to my understanding, basically we need to pick the min number from each array to get the min combination. we really don't need to sort them. we could use a heap structure with minimum being the root node. heap structure gives us a better complexity since we dont need to sort the full array. once we have 3 heaps, pick the root node and we will get our best combination. finding the minimum will be o(1) and creating the heap will be o(n).
- crisredfi1 September 04, 2014correct me if I'm wrong since the first description of the problem was not that clear. if I put the X top most cards from the button, i should pop the number of the card according of the number i just input right?
for exaple, I put the top 4 cards, and i should pop 4 of spade right? i believe that the structure already has the missing cards. am i right? If so, then the structure won't be a heap obviously, but can be done fairly easy with a balanced binary tree and output the cards after doing a search throughout it.
heap data structure will be the data structure i would choose. maintain highest card on top, and each time you pop the root node, the biggest one will become to top one. NLogN to create the heap structure.
- crisredfi1 July 21, 2014We basically need to use the NSURLSession and all his delegates to approach this design.
I would create a View controller to handle all the UI stuff, input the url and showing the progress bars for each download. each progress bar will be shown below each other and will be created by a dynamic method (no .XIB needed).
to handle the callbacks from the UITextField we need to implement its delegates so when we click search, the delegate is triggered.
NSURL session class will be created in a singleton. here we will create once the session and all its configuration, timeout and all its delegates. The necessary delegates here are NSURLSessionDownloadDelegate,, NSURLSessionTaskDelegate, and the NSURLSessionDataDelegate.
we mostly need to implement callbacks in our singleton for all of the delegates. So basically we can create wrappers methods with also blocks pattern to respond to all delegates actions.
this way we can call our singleton from our UIViewController with a block pattern and wait for any inconvenience , progress, or end download callback. we can handle all the states they are asking by blocks. This way we can call the block and handle several downloads simultaneously, also using background threads and cache storage since NSURLSessions allows us to do all that for free.
NSURLSession also allows us to stop, pause and resume a download at any time, also it allows us to recover a failed download from a specific point.
we could also extend our explanation saying that NSURLSession handles authentication and we could actually handle URL redirections for specific authentications.
to extend this for a browser, we would need just to create a button in our UIWebView navigation bar and then pass the url to our downloader, and handle, through delegate pattern, any new callback necessary to the UIWebView. the rest of the download process and error handling can be managed in the background.
this is a design question, so apart form some UML, I don’t think they require much code.
Is there any restriction? I mean, is there any requirement or you can use any Foundation classes? if so, we just need NSorderedSet. complexity is not told by apple, but i would say its probably better than o(n), I would say is a o(logN)
NSArray *testArray = @[@"dog", @"cat", @"dog", @"fish"];
NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:testArray];
using the automatic NSString enumeration reverses the string itself..
this would be the function
NSString * swapString(NSString *inputString) {
NSMutableArray *characters = [NSMutableArray array];
[inputString enumerateSubstringsInRange:NSMakeRange(0, inputString.length)
options:NSStringEnumerationByComposedCharacterSequences | NSStringEnumerationReverse
usingBlock:^(NSString *substring,
NSRange substringRange,
NSRange enclosingRange,
BOOL *stop) {
[characters addObject:substring];
}];
return [characters componentsJoinedByString:@""];
}
obj c example. O(n) time, O1 space
#import <Foundation/Foundation.h>
int main(int argc, const char * argv[])
{
@autoreleasepool {
NSMutableArray *testArray = [NSMutableArray arrayWithObjects:@0, @3, @5, @0, @0, @0, @1, @3, @1, @3, @5, @0, @0, @1, @0, nil];
long j = testArray.count -1;
for (long i = 0; i <= j; i++) {
if ([testArray[i] integerValue] == 0) {
for (;j >= i; j--) {
if ([testArray[j] integerValue] != 0) {
[testArray exchangeObjectAtIndex:i withObjectAtIndex:j];
j--;
break;
}
}
}
}
// insert code here...
NSLog(@"array us %@ swaps num ara %lu" , testArray, testArray.count - j-1 );
}
return 0;
}
How about this. Add the items into 2 heaps, one for the positive and other for the negative numbers. both heaps will maintain the top high elements on it. then check if there are 2 negative numbers within the higher 3 possible integers to multiply, if not then select the 3 from the positive heap. that should take o(n) time for putting them into the separate heaps, and o(log n) to get them. so total o(n) complexity.
- crisredfi1 July 14, 2014I think we can start with an empty array, then for each new character, just add that character to all existing members of the empty array we had. we save quite a bit of space complexity here and duplications.
on algorithm complexity, It is o(n*m)
here is my objective c version, shame there is no better way to work with characters and strings...
NSString *string = @"abc";
NSMutableArray *characters = [NSMutableArray arrayWithCapacity:string.length];
[string enumerateSubstringsInRange:NSMakeRange(0, string.length)
options:(NSStringEnumerationByComposedCharacterSequences)
usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
[characters addObject:substring];
}];
NSMutableArray *output = [NSMutableArray arrayWithObject:@""];
[characters enumerateObjectsUsingBlock:^(NSString *obj, NSUInteger idx, BOOL *stop) {
NSArray *temporalOutput = [output copy];
[temporalOutput enumerateObjectsUsingBlock:^(NSString *newInput, NSUInteger idx, BOOL *stop) {
[output addObject:[newInput stringByAppendingString:obj]];
}];
}];
NSLog(@"output %@", output);
here goes mine in objective O(n) times i think
NSMutableArray *numbers = [NSMutableArray arrayWithObjects:@2, @11, @5, @1, @4, @7, nil];
if ([numbers count] < 3) {
NSLog(@"not enough elements");
return 0;
}
__block long sum = 0;
[numbers enumerateObjectsUsingBlock:^(NSNumber *obj, NSUInteger idx, BOOL *stop) {
sum += [obj doubleValue];
}];
if (sum %2 != 0) {
NSLog(@"cant find a sum for decimal numbers");
return 0;
}
NSSortDescriptor *sort = [NSSortDescriptor sortDescriptorWithKey:nil ascending:NO];
numbers = [[numbers sortedArrayUsingDescriptors:@[sort]] mutableCopy];
double total = sum/2;
for (int i = 0; i < numbers.count/2; i++) {
long temporal = [numbers[i] doubleValue];
for (int j = i + 1; j < numbers.count; j++) {
long maxSum = [numbers[j] doubleValue];
if ((maxSum + temporal) < total) {
NSLog(@"nothing here");
break;
} else if ((maxSum + temporal) == total) {
NSLog(@"we have a match. condition foudned sum numbers are %ld, %ld, against the rest", temporal, maxSum);
return 0;
}
}
}
This is what i think can be a good match for ios.
BOOL isAnagram(NSArray *input) {
NSMutableDictionary *anagrams = [NSMutableDictionary dictionary];
__block BOOL isAnagram = NO;
[input enumerateObjectsUsingBlock:^(NSString *word, NSUInteger idx, BOOL *stop) {
NSMutableArray *characters = [NSMutableArray array];
for (NSUInteger i = 0; i < word.length; i++) {
[characters addObject:[word substringWithRange:NSMakeRange(i,1)]];
}
// now sort the word
NSArray *sortedCharacters = [characters sortedArrayUsingSelector:@selector(compare:)];
NSString *sortedWord = [sortedCharacters componentsJoinedByString:@""];
if (anagrams[sortedWord] != nil) {
isAnagram = YES;
*stop = YES;
} else {
anagrams[sortedWord] = sortedWord;
}
}];
return isAnagram;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *input = @[@"bag", @"bat", @"tab"];
if (isAnagram(input)) {
NSLog(@"input is anagram");
} else {
NSLog(@"no Anagrams");
}
}
return 0;
}
can't find a better way to get the characters out
- crisredfi1 July 08, 2014same as I was thinking. I would only change this line
input = [input substringToIndex:input.length-4];
with this
input = [input stringByDeletingPathExtension];
RepOliviaJBlack, Consultant at Apkudo
I am Olivia from San Diego. I am working as a checker in the Thom McAn Store company. My strong ...
RepMiraDavis, Computer Scientist at Accenture
I am School librarian and also teach students the fundamentals of using a library and its resources .I write and ...
RepNatalieLutz, Applications Developer at Absolute Softech Ltd
Pitch trending story topics and continually look for ways to push breaking and/or viral stories forward with new angles ...
Repmarthavmoody, Consultant at Dell
Spent 2002-2010 investing in toy elephants in Pensacola, FL. Earned praised for my work testing the market for squirt guns ...
RepDonnaWHale, Data Engineer at ADP
Hi, I am passionate writer with a BA in English from the Ohio State University.5+ years of experience writing ...
RepRoyaltyAd is the top digital marketing company. We have a team of SEO experts that helps you to maximise your ...
Rep
objective c version using recursion and blocks:
- crisredfi1 September 29, 2014