搜狗、字节，iOS面试算法题 (2020)

现在面试iOS中高级开发，算法题已是必然会出现的一个环节了，这里把面试遇到的算法题做一个小汇总，希望对大家有用。大部分公司是需要直接手写算法题的，这块儿的能力不容忽略的。

• 1：编程实现字符串拷贝，要考虑下内存重叠问题。 (搜狗)
• 2：对输入的字符串，去除其中的字符‘b’以及连续出现的‘a’和‘c’ (字节)
• 3：如何求两个View的最近公共父类 (字节)

1：编程实现字符串拷贝，要考虑下内存重叠问题。(搜狗)

解决思路：既然要考虑内存重叠的问题，就是说可能目标地址的起始位置是在源字符串的后半段，或者目标的结束位置在源字符串的前半段。第一种情况，从末尾开始复制可以解决问题，同理：第二种情况，从首位开始复制可以解决问题，代码如下：

char *memcpy_qi(char *dst, const char* src, int cl)
{
    assert(dst != NULL && src != NULL);
    char *ret = dst;
    if (dst >= src && dst <= src+ cl-1) //内存重叠，从高地址开始复制
    {
        //挪开空间
        dst = dst+ cl-1;
        //将指针挪到结尾
        src = src+ cl-1;
        while (cl—)
            *dst— = *src—;
    }
    else    //正常情况，从低地址开始复制
    {
        while (cl—)
            *dst++ = *src++;
    }
    
    return ret;
}
char * strcpy_qi(char *dst,const char *src)
{
    assert(dst != NULL && src != NULL);
    char *ret = dst;
    memcpy_qi(dst, src, strlen(src)+1);
    return ret;
}

2：对输入的字符串，去除其中的字符‘b’以及连续出现的‘a’和‘c’ (字节)

样例：
‘aacbd’ -> 'ad'
'aabcd' -> 'ad'
'aaabbccc' -> ''
不允许使用类似string.replace函数
要求时间、空间复杂度尽量优化

3：如何求两个View的最近公共父类 (字节)

解决思路：
首先，这个问题必然不能按照常规的方式去对一个VIew的所有父类去进行for循环比较，那这个题出的就没有意义。
然后，每个类的所有父类组成了一个继承链，而在UIKit下，所有的UIView的最终父类也必然是NSObject，其实就相当于这两个类的继承链从NSObject开始向下一直是重合的，直到最后的一个公共父类才开始分开，这个最后的公共父类也是最近的公共父类，这是典型的倒Y字型链表组合。那么解题思路就很好做了，具体代码如下：

- (void)viewDidLoad {
    [super viewDidLoad];
    Class commonClass = [self commonClass1:[ViewA class] andClass:[ViewB class]];
    NSLog(@"最近公共父类为:%@",commonClass);
}
// 获取所有父类
- (NSArray *)superClasses:(Class)class {
    if (class == nil) {
        return @[];
    }
    NSMutableArray *result = [NSMutableArray array];
    while (class != nil) {
        [result addObject:class];
        class = [class superclass];
    }
    return [result copy];
}
//对两条链表进行比对
- (Class)commonClass1:(Class)classA andClass:(Class)classB {
    NSArray *arr1 = [self superClasses:classA];
    NSArray *arr2 = [self superClasses:classB];
    NSInteger count = arr1.count < arr2.count ? arr1.count : arr2.count;
    Class resultClass;
    for (NSUInteger i = 0; i < arr1.count; ++i) {
        Class classA = arr1[arr1.count - i - 1];
        Class classB = arr2[arr2.count - i - 1];
        if(classA == classB){
            resultClass = classA;
        }else{
            break;
        }
    }
    return resultClass;
}

• 另外小编整理了一份 2020年《大厂最新常问iOS面试题+答案》，有需要，直接加iOS技术交流群：937194184，免费获取；群内更有内推机会！
• 【点击快速加入】：与更多iOS开发者一起交流