CareerCup

After careful thoughts and trying to understand the question, I believe the question can be solved in O(n) algorithm complexity and O(n) space

- (void)commonView:(UIView *)a1 with:(UIView *)a2 {

    NSMutableSet *s = [[NSMutableSet alloc] initWithCapacity:[[a1 subviews] count]];
    for (UIView *a1SubViews in [a1 subviews]) {
        [s addObject:[a1SubViews class]];
    }
    
    for (UIView *a2SubView in [a2 subviews]) {
        if ([s containsObject:[a2SubView class]]) {
            NSLog(@"#Boom, I found the common view %@", a2SubView);
            return;
        }
    }
    NSLog(@"NO common subview");
    return;
}

Diego,

So let me rephrase this question. Suppose A1 has many subviews in its tree hierarchy and among them we have one view, say MyViewToFind which say exists at ith location on A1's tree.

Taking the ith view (MyViewToFind) from A1, do I have to check to see (or find out the same view) in A2's view hierarchy?

Can you give an idea of how to do with DP for regex parsing.

NSMutableArray *result;
NSMutableString *tempSolution;
NSArray *dict;


void printAllPossibleCombo() {
    dict = @[ @"",
              @"",
              @"ABC",
              @"DEF",
              @"GHI",
              @"JKL",
              @"MNO",
              @"PQRS",
              @"TUV",
              @"WXYZ"];
    
    result = [[NSMutableArray alloc] init];
    tempSolution = [[NSMutableString alloc] init];
    backtracking(@"234", 0);
    for (NSString *s in result) {
        NSLog(@"%@", s);
    }
}

void backtracking(NSString *s, NSInteger i) {
    NSString *setOfLetters = [dict objectAtIndex:([s characterAtIndex:i] - '0')];
    for (NSInteger a = 0; a < [setOfLetters length]; a++) {
        unichar ch = [setOfLetters characterAtIndex:a];
        [tempSolution appendString: [NSString stringWithCharacters:&ch length:1]];
        if (i == s.length - 1) {
            [result addObject:[tempSolution copy]];
        } else {
            backtracking(s, i+1);
        }
        [tempSolution deleteCharactersInRange:NSMakeRange((tempSolution.length-1), 1)];
    }
}

Credit goes to Sir CodesALot

void oneEditApart(NSString *a, NSString *b) {
    if ([a length] - [b length] == 1 || [a length] - [b length] == -1) {
        printf("false\n");
        return;
    } else if ([a length] == [b length]){
        int opts = 0;
        for (int i=0; i< [a length];i++) {
            if ([a characterAtIndex:i] != [b characterAtIndex:i])
                opts++;
            if (opts > 1) {
                printf("false\n");
                return;
            }
        }
    } else {
        NSString *s = ([a length] > [b length])? b : a;
        NSString *l = ([a length] > [b length])? a : b;
        int opts = 0;
        for (int i=0; i < [s length]; i++) {
            if ([s characterAtIndex:i] != [l characterAtIndex:i+opts]) {
                opts++;
            }
            if (opts > 1) {
                printf("false\n");
                return;
            }
        }
    }
    printf("true\n");
}

Here is the class for

MinHeapNode

#import <Foundation/Foundation.h>

@interface MinHeapNode : NSObject
@property (nonatomic, strong) NSNumber *num;
@property (nonatomic, assign) NSInteger arrayIndex;
@property (nonatomic, assign) NSInteger nextElement;
@end

Next is the

MinHeap

class required for storing the data.

#import <Foundation/Foundation.h>
#import "MinHeapNode.h"

@interface MinHeap : NSObject

- (id)initWithSize:(NSInteger)size;
- (void)add:(MinHeapNode *)a;
- (MinHeapNode *)findMin;
- (MinHeapNode *)deleteMin;
- (void) heapify;
- (BOOL)isEmpty;
- (void) printHeap;
@end

Next is the

MinHeap

implementation

#import "MinHeap.h"

@interface MinHeap() {
    NSMutableArray *array;
}

@end
@implementation MinHeap

- (id)initWithSize:(NSInteger)size {
    self = [super init];
    if (self) {
        array = [NSMutableArray arrayWithCapacity:size];
    }
    return self;
}

- (void)add:(MinHeapNode *)a {
    [array addObject:a];
    
    if ([array count] == 1) return;
    
    NSInteger i = [array count] - 1;
    NSInteger p = 0;
    while (i >=0 ) {
        p = (i - 1)/2;
        MinHeapNode *a = [array objectAtIndex:i];
        MinHeapNode *b = [array objectAtIndex:p];
        if ([a.num integerValue] < [b.num integerValue]) {
            [self swap:p with:i];
        } else {
            break;
        }
        i = p;
    }
}

- (void) heapify {
    NSInteger i = 0;
    while (i < [array count]) {
        MinHeapNode *min = nil;
        if ([self right:i] < [array count]) {
            MinHeapNode *a = [array objectAtIndex:[self left:i]];
            MinHeapNode *b = [array objectAtIndex:[self right:i]];
            if (a.num < b.num) {
                min = a;
            } else {
                min = b;
            }
        } else {
             min = [array objectAtIndex:[self left:i]];
        }
        MinHeapNode *f = [array objectAtIndex:i];
        if ([f.num integerValue] > [min.num integerValue]) {
            NSInteger k = [array indexOfObject:min];
            [self swap:i with:k];
            i = k;
        } else {
            break;
        }
        
        if ([self left:i] > [array count] || [self right:i] > [array count]) {
            break;
        }
    }
}

- (NSInteger)left:(NSInteger)i {
    return 2*i + 1;
}

- (NSInteger)right:(NSInteger)i {
    return 2*i + 2;
}

- (MinHeapNode *)findMin {
    if ([array count] == 0) {
        return nil;
    } else {
        return [array firstObject];
    }
}

- (MinHeapNode *)deleteMin {
    if ([array count] > 2) {
        MinHeapNode *min = [array firstObject];
        MinHeapNode *last = [array lastObject];
        [array removeLastObject];
        [array replaceObjectAtIndex:0 withObject:last];
        [self heapify];
        return min;
    } else if ([array count] == 2) {
        MinHeapNode *min = [array firstObject];
        [array removeObjectAtIndex:0];
        return min;
    } else if ([array count] == 1) {
        MinHeapNode *min = [array firstObject];
        [array removeLastObject];
        return min;
    }
    return nil;
}

- (void)swap:(NSInteger)i with:(NSInteger)j {
    MinHeapNode *t = [array objectAtIndex:i];
    [array replaceObjectAtIndex:i withObject:[array objectAtIndex:j]];
    [array replaceObjectAtIndex:j withObject:t];
}

- (BOOL)isEmpty {
    return [array count] == 0;
}

- (void) printHeap {
    for (MinHeapNode *n in array) {
        printf("%d ", [n.num intValue]);
    }
    printf("\n");
}

@end

Finally the method to mergeSort the arrays

void mergeArrays(NSArray *arrays) {
    //k be number of arrays that are present.
    //n be number of elements in each array;
    
    if ([arrays count] == 1) {
        NSLog(@"%@", [arrays firstObject]);
    } else {
        NSInteger k = [arrays count];
        NSInteger n = [[arrays firstObject] count];
        
        MinHeap *minHeap = [[MinHeap alloc] initWithSize:k];
        NSMutableArray *temp = [NSMutableArray arrayWithCapacity:n*k];
        
        for (int i=0; i< k;i++) {
            MinHeapNode *t = [[MinHeapNode alloc] init];
            t.num = [[arrays objectAtIndex:i] objectAtIndex:0];
            t.arrayIndex = i;
            t.nextElement = 1;
            [minHeap add:t];
        }
        
        for (int i=0; i < n*k;i++) {
            MinHeapNode *t = [minHeap findMin];
            [temp addObject:t.num];
            if (t.nextElement < n) {
                t.num = [[arrays objectAtIndex:t.arrayIndex] objectAtIndex:t.nextElement];
                t.nextElement +=1;
            } else {
                t.num = [NSNumber numberWithInt:INT32_MAX];
            }
            [minHeap heapify];
        }
        
        NSLog(@"%@", temp);
    }
}

Which company was this?

NSMutableArray *a = [[NSMutableArray alloc] initWithCapacity:30];
        for (NSArray *t in input) {
            [a addObjectsFromArray:t];
        }
        NSArray *b = [a sortedArrayUsingComparator:^NSComparisonResult(NSNumber *obj1, NSNumber *obj2) {
            return [obj1 compare:obj2];
        }];

Shouldn't oneEditApart("cat", "cat") return false as there is no insertion, removal or replacement required to get string2?

or are we removing an empty string -> '' from "cat" to get "cat"????

What about the case

OneEditApart("cat", "dog") = ????

.

In your case, it returns true.

In this case of adding characters and using prime numbers to add, I don't see any case arising where two characters are added and that gives another two characters. Please see, I am also checking the length so that 'a' + b' = 'c' but length check wil fail it.

void groupAnagrams(NSArray *array) {
    
    NSMutableDictionary *group = [[NSMutableDictionary alloc] initWithCapacity:[array count]];
    
    for (NSString *s in array) {
        const char *c = [s UTF8String];
        int sum = sumCharacters(c);
        NSMutableArray *anagrams = [group objectForKey:[NSNumber numberWithInt:sum]];
        if (anagrams) {
            [anagrams addObject:s];
        } else {
            NSMutableArray *anagrams = [[NSMutableArray alloc] initWithCapacity:10];
            [anagrams addObject:s];
            [group setObject:anagrams forKey:[NSNumber numberWithInt:sum]];
        }
    }
    
    for (NSNumber *n in group) {
        NSArray *anagrams = [group objectForKey:n];
        printf("[");
        for (NSString *s in anagrams) {
            printf("%s,", [s UTF8String]);
        }
        printf("]\n");
    }
}

int sumCharacters(const char *c) {
    int charValues[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    int intValues[10] = {103, 107, 109, 113, 127, 131, 137, 139, 149, 151};
    int spaceValue = 157;
    int commaValue = 163;
    
    int sum = 0;
    for (int i=0; c[i] != '\0';i++) {
        if (c[i] >= 'a' && c[i] <= 'z') {
            sum += charValues[c[i] - 'a'];
        } else if (c[i] >='0' && c[i] <= '9') {
            sum += intValues[c[i] - '0'];
        } else if (c[i] == ' '){
            sum += spaceValue;
        } else if (c[i] == ','){
            sum += commaValue;
        }
    }
    
    return sum;
}

NSString * sumBinaryNumbers (NSString *b1, NSString *b2) {
    
    int counter = [b1 length];
    if ([b1 length] > [b2 length]) {
        int lenDiff = [b1 length] - [b2 length];
        NSString *zeros = [@"" stringByPaddingToLength:lenDiff * [@"0" length] withString:@"0" startingAtIndex:0];
        b2 = [zeros stringByAppendingString:b2];
    } else {
        int lenDiff = [b2 length] - [b1 length];
        NSString *zeros = [@"" stringByPaddingToLength:lenDiff * [@"0" length] withString:@"0" startingAtIndex:0];
        b1 = [zeros stringByAppendingString:b1];
    }
    
    NSMutableString *result = [NSMutableString new];
    NSString *one = [NSMutableString stringWithString:@"1"];
    NSString *zero = [NSMutableString stringWithString:@"0"];
    int carry = 0;
    
    for (int i=counter-1; i>=0; i--) {
        if ([b1 characterAtIndex:i] == '0' && [b2 characterAtIndex:i] == '0') {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
            }
        } else if ([b1 characterAtIndex:i] == '0' && [b2 characterAtIndex:i] == '1') {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
                carry = 0;
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
                carry = 1;
            }
        } else if ([b1 characterAtIndex:i] == '1' && [b2 characterAtIndex:i] == '0') {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
                carry = 0;
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
                carry = 1;
            }
        } else {
            if (carry == 0) {
                result = [NSMutableString stringWithFormat:@"%@%@", result, zero];
            } else {
                result = [NSMutableString stringWithFormat:@"%@%@", result, one];
            }
            carry = 1;
        }
    }
    
    if (carry == 1) {
        result = [NSMutableString stringWithFormat:@"%@%@", one, result];
    }
    
    return result;
}