iOS面试‘腾讯阿里网易’上来就四道算法题？（一）
前言
现在出去面, 如果是面中高级的, 基本不会问那些特别基础的东西了, 底层这块问到的是最多的，现在大厂有一点，你在一个项目组面完了, 基础面试这一块就不用在面了！ 特别在乎的是做过的项目. 如果项目好久很好说话, 项目不好很被动, 不知道怎么去补。
面试的开始还是算法+底层
由于我面试的都是比较大的公司，所以自然也是做了这方面的准备，现在面试iOS中高级开发，算法题已是必然会出现的一个环节了，这里把面试遇到的算法题和LeetCode上一些比较经典的算法题做一个汇总，希望对大家有用。
持续更新--请iOS的小伙伴关注! 喜欢的话给一个赞吧！
题目
- 1 实现一个方法，计算100的阶乘。
- 2 编程实现字符串拷贝，要考虑下内存重叠问题。
- 3 对输入的字符串，去除其中的字符‘b’以及连续出现的‘a’和‘c
- 4 如何求两个View的最近公共父类
1 实现一个方法，计算100的阶乘。
主要考虑到通用性，还有就是尽量不要使用递归，会导致方法栈空间占用过大。所以采用for循环的方式进行计算就OK。
#import <Foundation/Foundation.h>
long long dofactorial(int min, int max){
if(min > max){
return 0;
}
if(min == 0){
if(max == 0){
//0的阶乘是1
return 1;
}else{
min = 1;
}
}
long long result = 1;
for (int i = min; i <= max; i++) {
result *= i;
if(result > INT_MAX){
//考虑溢出
return -1;
}
}
return result;
}
int main(int argc, const char * argv[]) {
int result = dofactorial(0, 100);
printf("result = %lld", result);
return 0;
}
2 编程实现字符串拷贝，要考虑下内存重叠问题。
解决思路：既然要考虑内存重叠的问题，就是说可能目标地址的起始位置是在源字符串的后半段，或者目标的结束位置在源字符串的前半段。第一种情况，从末尾开始复制可以解决问题，同理：第二种情况，从首位开始复制可以解决问题，代码如下：
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;
}
3. 对输入的字符串，去除其中的字符‘b’以及连续出现的‘a’和‘c’
样例：
‘aacbd’ -> 'ad'
'aabcd' -> 'ad'
'aaabbccc' -> ''
不允许使用类似string.replace函数
要求时间、空间复杂度尽量优化
4 如何求两个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;
}
4.如何用两个骰子表示一个月的完整日期
分享个以前朋友给我出的问题，问题是这样的：现有两个骰子，每个骰子6个面，全是空的，现在需要用这两个骰子表示年月日中的日的全部情况(1-31),1号算01，一个骰子只能表示一位，且不能两位都用同一个骰子，那么在这种情况下，每个骰子的六个面上该怎么刻数字呢？
解决思路：
一、月份的日期，是从1号到31号的，那十位上的所有可能性就是0、1、2、3.个位上也是包含这几个数的，那么0、1、2、3必然两个骰子上都有。
二、但是，十位为3的情况只有30，31，在两个骰子上都有0、1、2的情况下，3只在一个骰子有也可以表示出来的，颠倒位置即可，那么就是0、1、2必须每个骰子上都有。
三、两头骰子此时还剩下6个面，日期必须的数字此时还剩下，3、4、5、6、7、8、9一共7个数，数字比面数多一个，那就是还得想办法再节省一个。这个时候就要考虑下6和9能不用共用一个面了。
答案：
骰子A ： 0、1、2、3、4、5
骰子B ： 0、1、2、6、7、8
文章题目已经整理为完整的答案文档！需要的话可以添加QQiOS交流群：761407670 进群密码000,不管你是小白还是大牛欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！
另附上一份各收集的大厂面试题，进群可自行下载！
底层面试题
记不太清了23333.....底层是问最多的就是runtime,项目这块问题需要充足准备！！！
1.runtime相关问题
一个objc对象的isa的指针指向什么？有什么作用？
说一下对 isa 指针的理解， 对象的isa 指针指向哪里？isa 指针有哪两种类型？
使用runtime Associate方法关联的对象，需要在主对象dealloc的时候释放么？
2.Block
Block如何变量截获？
Block的几种形式？
3.性能优化
如何高性能的画一个圆角？
什么是 离屏渲染？什么情况下会触发？该如何应对？
如何提升 tableview 的流畅度？
4.Runloop
为什么 NSTimer 有时候不好使？
AFNetworking 中如何运用 Runloop?
PerformSelector:afterDelay:这个方法在子线程中是否起作用？为什么？怎么解决？
5.什么是函数式编程？
函数可以接受函数当作输入（参数）和输出（返回值）。
6.什么是ABI？
应用程序二进制接口（application binary interface，ABI） 描述了应用程序和操作系统之间，一个应用和它的库之间，或者应用的组成部分之间的低接口 。ABI不同于API ，API定义了源代码和库之间的接口，因此同样的代码可以在支持这个API的任何系统中编译
7.什么是MVC,请结合CocoaTouch说明？
8.什么是MVVM，请设计View moled需要考虑哪些？
- 低耦合。视图（View）可以独立于Model变化和修改，一个ViewModel可以绑定到不同的"View"上，当View变化的时候Model不可以不变，当Model变化的时候View也可以不变。
- 可重用性。你可以把一些视图逻辑放在一个ViewModel里面，让很多view重用这段视图逻辑。
- 独立开发。开发人员可以专注于业务逻辑和数据的开发（ViewModel），设计人员可以专注于页面设计，使用Expression Blend可以很容易设计界面并生成xaml代码。
- 可测试。界面素来是比较难于测试的，而现在测试可以针对ViewModel来写。
9.swift相对于OC有哪些优点？
简洁的语法：
我们不得不承认的是swift语言比OC精简，整个项目中丢掉了头文件，以及头文件的引入。
报错精准：
报错的时候直接显示报错行。
定义变量简单：
定义变量不用区分整型，浮点型等等，变量使用var，常量使用let。
可视化互动效果：
开发工具带来了Xcode Playgrounds功能，该功能提供强大的互动效果，能让Swift源代码在撰写过程中实时显示出其运行结果。
函数式编程的支持：
Swift 语言本身提供了对函数式编程的支持；
Objc 本身是不支持的，通过引入 ReactiveCocoa 这个库才可支持函数式编程。
持续更新--请iOS的小伙伴关注! 喜欢的话给一个赞吧！
该偏文章所有题目已经整理为完整的答案文档！需要的话可以添加QQiOS交流群：761407670 进群密码000,不管你是小白还是大牛欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！
