知识记录

# 前言

---

> 在易鑫服务了一年多，因为种种原因，还是自己的原因最主要吧，选择了离开易鑫，开始寻找新的方向，在此期间收到了很多公司的面试，也不伐一些大厂，在此做一个总结，送给准备和我做一样or类似决定的同事们，感谢大家一年多的关照与教导。

我将会进我可能，按照面试的公司分别记录相应的面试题，面试题以基础-发散-算法的结构描述（也是面试的一般的面试套路），然后我会附上我找到的一些答案链接，或者说一下自己的见解，对于答案，大家见仁见智。在最后做一个概括性的总结，期间难免有所遗漏，还请大家见谅。

A lot of thanks!

# 面试题/公司(/部门)

---

## 美团点评-打车部门

### 基础

1. **Objc 动态性**

参考答案：**动态类型**、**动态绑定**和*动态加载*，[参考链接](https://blog.csdn.net/cordova/article/details/53876682)；

2. **Objc Runtime**

* **Objc 内存布局**

参考答案：直接给出陈宜龙对于 sunnyxx 面试题的答案：[参考链接](https://github.com/ChenYilong/iOSInterviewQuestions/blob/master/01《招聘一个靠谱的iOS》面试题参考答案/《招聘一个靠谱的iOS》面试题参考答案（上）.md#19-一个objc对象如何进行内存布局考虑有父类的情况)；

* **消息机制（dynamic binding-动态绑定）**

参考答案：消息机制，相信大家都知道这个过程，具体我就不细说了，我的理解就是消息机制提供了静态语言例如（C、C++）提供不了的间接性，对此，苹果也做了相应的介绍，详见[苹果官方文档](https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/ObjCRuntimeGuide/Articles/ocrtForwarding.html#//apple_ref/doc/uid/TP40008048-CH105-SW1)，具体章节忘记了，自行阅读；

* **分类方法加载的优先级**

参考答案：在[苹果开源网站上](https://opensource.apple.com)大家可以下载到一些*源码*，我猜测，这里的*源码*和线上的代码一定不同哈，不过也能够看出一些东西，可以解释这个问题。看一下runtime.h中对于Class的源码中，方法列表 methodLists 的定义可以看出，methodLists 是一个指向指针的指针（**pointer），在加载分类方法时，是倒插入这个列表中的，然而因为消息机制也是倒着找方法的，找到之后存入方法cache中，所以下次就不会再重新找，这样也就是分类的优先级高于原类的优先级的原因；

* **分类中添加属性**

参考答案：答案当然就是我们常用的**关联属性（Associate Objects）**，实际上应该是存储在一个全局的 hash table 中，具体请看[这篇](https://www.jianshu.com/p/79479a09a8c0)，当然这个源码我还没有读到，大家感兴趣也可以自己看源码；

* **Weak 的实现**

参考答案：其实不论是 weak 或者是对象的引用计数信息都是存放在一张全局的 hash table 中，详细的话可以看看[这个](https://www.jianshu.com/p/ed43b17c8a72)，当然这个我是随便搜的，网上找一找，特别多，如果这个写的不好，大家再搜搜别的；

3. **@property**

参考答案：我所理解的， @property = _ivar + getter + setter。具体内存管理语义修饰符相信大家也都知道，贴出一个[链接](https://blog.csdn.net/u014205968/article/details/64443443)；

4. **Copy & MutableCopy**

参考答案：直接上[链接](https://www.jianshu.com/p/22affaf798f8)了，这个是我之前写的一点东西，大家看看哈，别喷我；

5. **Responder Chain(响应链)**

参考答案：响应链是[职责链模式](https://www.cnblogs.com/cxxjohnson/p/6403849.html)的一种具体实现吧，在 SpringBoard 接收到 touch 之后，将触摸打包成 UIEvent 发送给当前的 application，application收到之后事件之后，将决定如何响应这个触摸，也就是由谁来响应。大概为如下过程：

**a. 从下向上找到触摸的视图；**

**b. 从上到下找到处理触摸的 target，包括 UIReponder(UIView、UIControl等) 和 UIGesture；**

**c. 如果找不到，那么最后会尝试让 application 去处理；**

**d. 如果 application 还是无法响应，那么会让 app delegate 去处理（也就是常问的， appDelegate 是继承于 UIReponder 的）；**

**e. 如果还是没有得到处理，就抛弃。**

其中，一般会问到，如果一个**视图超出了父视图的边界（bounds），如何使之响应**这种问题，一般来说就可以通过```- hitTest:withEvent: 和 -pointInside:withEvent:```这两个方法来处理。具体链接大家还是自己找吧，不贴了；

4. **block**

参考答案：乏善可陈，总而言之看[llvm 的block imp](http://clang.llvm.org/docs/Block-ABI-Apple.html#layout-of-block-marked-variables)吧；

### 发散

1. **MVC、MVVM、VIPER(可选，我是尝试过 VIPER)**

答案：这里我贴出两个链接，一个是 [casa 的系列文章](https://casatwy.com/iosying-yong-jia-gou-tan-viewceng-de-zu-zhi-he-diao-yong-fang-an.html)，另一个是 [objccn 的 VIPER](https://objccn.io/issue-13-5/)，见仁见智吧；

2. **如何处理忘记移除通知观察者的问题**

参考答案：我没有尝试过，也没想过具体怎么弄，大家自己查吧；

3. **CPU 流水线（可选）**

参考答案：自己查吧，我是看过相关方面的书；

4. **高速缓存（可选）**

参考答案：自己查吧，我是看过相关方面的书；

5. **友盟崩溃率计算方式等**

参考答案：我也不知道具体公式是啥，大家自己查吧..

### 算法

1. **洗牌算法，给你一个数组，打乱这个数组，有可用的随机数函数。**

参考答案：说一个大概的思路，就是每次随机从有序数组中抽取出一个元素，然后加到乱序数组中，把有序数组抽空，乱序数组就满了；

2. **使用 C 语言写一个 stack，考虑多线程**

参考答案：我是用链表实现的，这里大家随便找，有的是文章；多线程这个我只知道加锁，自己看咋弄吧...

3. **统计一个已知函数的运行时间，只允许在一处插入代码，考虑多线程**

参考答案：经过面试官提示，采用了递归的思路（如果需要考虑多线程的话，那么可以想办法把这个插入的 flag 和线程绑定），具体实现看demo：

```

/// 原函数

int test(int param)

{

/// 各种分支

if (param > 0) {

return param * param;

}

if (param == 0) {

return param;

}

return param / 3;

}

```

/// 插入统计时间的代码后

```

int test(int param)

{

///插入的代码

static int flag = 1;

if (flag) {

flag = 0;

clock_t start = clock();

int retVal = test(param);

clock_t end = clock();

flag = 1;

printf("Duration is %lu.\n", end - start);

return retVal;

}

/// 各种分支

if (param > 0) {

return param * param;

}

if (param == 0) {

return param;

}

return param / 3;

}

```

## 搜狗-金融部门

### 基础

1. **RunLoop**

参考答案：参考的 YYKit 作者的[深入理解 RunLoop](https://blog.ibireme.com/2015/05/18/runloop/)，以及 [RunLoop开源源码](https://opensource.apple.com)；

2. **内存管理**

参考答案：自己找吧，反正我看源码是存在 **side table** 中的，这块我面试的时候，我也不知道 **side table** 这种东西，也就说了 retain release 啥的，当然比如 globle object 、 static object 和 tagged pointer 不用做这些操作；

3. **锁（数据竞争问题处理方式）**

参考答案：参考官方文档的 [Thread Programming Guide 中的 Syncronization 一节](https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/Multithreading/ThreadSafety/ThreadSafety.html#//apple_ref/doc/uid/10000057i-CH8-SW1)；当然还有我也才知道的 [CAS 乐观锁](https://blog.csdn.net/liubenlong007/article/details/53761730)等，当然我的理解不深，或者说我不会...

4. **Grand Central Dispatch**

参考答案：我在这里谈谈我个人的理解，当然我没有看源码...我的理解 dispatch_queue 是一个**任务队列**，我们在使用 GCD 的时候一般是把任务添加到队列中，队列要么是串行，要么是并发。那么串行队列语义就是顺序执行任务，并发队列顺序不确定。我的理解是这样的，串行队列是顺序取出内部添加的任务，然后派发到线程中去执行；并行队列也是顺序取出任务，但是执行顺序不确定，因为并发队列取出多个任务，然后派发到不同的线程中去，这些线程的执行顺序不确定。

* Extra: 在一个**串行队列**中派发了10个**任务**，那么这10个任务会在同一个线程执行吗？

参考答案：**不一定**。如果我先在队列中派发了一个任务，这个任务做完之后，队列发现没有要做的任务了，那么会把用到的线程归还到线程池中。再派发第二个任务的时候，队列发现有任务要做，但是没有可用的线程，队列会去线程池中取一个线程出来，这个时候，就出现了两个线程，而且有非常大的可能不是同一条线程了。所以对于串行队列我的理解是**语义上保证了任务的执行顺序，但是不一定是同一条线程**；

5. **KVO**

参考答案：[KVO原理分析及使用进阶](https://www.imooc.com/article/24023)，我大概看了下，大家也可以自行查询哈，不保证一定是对的。大概的思路就是动态生成一个子类，然后去重写 setter（KVO setValue:forKey:也会处理），发送相应的消息出去；

6. **@property**

参考答案：重复问题；

7. **Copy & MutableCopy**

参考答案：重复问题；

### 发散

1. **怎么做一个 Crash 统计**

参考答案：自己搜吧...我知道的有两个点，一个是 ```NSSetUncaughtExceptionHandler``` ，但是这种只能处理 NSException 类型的异常；另一种就是 C 语言的函数 ```signal(int, void (*)(int))``` 去注册发生对应信号的异常处理函数，比如说定义在 signal.h 中的常量宏 SIGFPE 等，对应的也有很好的注释。其他的我暂时也不是很清楚了；

2. **有没有遇到过 CGRectNull 崩溃问题**

参考答案：我还真没遇到过这个具体的，不过我遇到过 ```CGRectInfinite```、以及 ```NaN (Not a Number)``` 发生的崩溃。在做车贷后台模糊效果的时候，有遇到过因为 webView 中的这种*非正常* 的 rect 在绘图过程中导致了崩溃，每个系统发生的问题，打印的错误也都不大一样，还是自行研究吧；

3. **老生常谈的 UITableView（UICollectionView）卡顿优化**

参考答案：大家自己查吧..我的理解是从两个层面考虑：**CPU卡顿**、**GPU**卡顿，在这二者之间维持一个平衡；如果怎么样都做不到平衡之后不卡顿，那么可以考虑比如 **缓存** ？用 **过渡动画** 等提高用户体验 ？在此贴出[表哥 Delpan 的 页面间跳转性能优化系列](https://www.jianshu.com/p/77847c0027c9)；

### 算法

1. **10000个数中找出最大的3个数（Top(n)） 问题**

参考答案：网上针对于 **Top(n)** 问题好像有三种解决方案，我只知道一个，就是用**优先队列（小顶堆）**来解决，[贴个链接](https://blog.csdn.net/gaoranfighting/article/details/44784059)；

2. **全世界有没有两个人的头发数量是相同的（WTF）**

参考答案：**有的**，意思是说只要人的数量远大于头发的数量，那么头发的假设头发的数量是100W，也就是头发数量是 0-100W，人的数量为 60 亿，那么就一定有两个人头发数量是相同的；反正我挂了...

3. **数组与链表**

参考答案：这个问题就比较简单了，相信大家都会..

4. **MVC、MVVM、VIPER**

参考答案：重复问题；

## 滴滴-顺风车

### 基础

>到了滴滴这边，好多就都是重复的了，而且我的本上也没有那么多东西..

1. **RunLoop**

2. **@property**

3. **NSCache**

参考答案：自己查咯，我也没说明白这个玩意儿，因为几乎不咋用..

...

### 发散

1. **如何设计一个图片缓存组件**

参考答案：这个说起来比较多，比如 URL-ImageFileName 映射，中间处理过程、内存以及硬盘缓存（这里有一个思想，就是高速缓存的思想，一般来说速度快的缓存，造价更高，容量也就比较小；比如内存造价比硬盘更贵，容量更小，所以内存是硬盘的高速缓存，以提高读取速度）、淘汰策略（[FIFO 、LRU、LFU等](https://blog.csdn.net/clementad/article/details/48229243)）...

### 算法

1. **打印菱形**

**Description:**  写一个函数 ```void printStar(unsigned int n)```，具体我插入一张图片吧：

参考答案：在这里我给出的答案如下：

```

static void _printStar(unsigned int cnt)

{

while (cnt) {

putchar('*');

cnt--;

}

}

static void _printWhiteBlank(unsigned int cnt)

{

while (cnt) {

putchar(' ');

cnt--;

}

}

static void _printReturn(void)

{

putchar('\n');

}

static void drawStars(unsigned int n)

{

unsigned int halfn; /// half n ..

unsigned int nos = 1, nob; /// number of stars, number of blanks

unsigned int idx = 0;

/// 如果 n 是偶数，那么 n 加等于 1，使之成为奇数

/// 这里我们并没有把这件事做的高效，如果需要高效，可以 |= 1 这种方式，效率应该比 % 高很多很多

if (n % 2 == 0) {

n += 1;

}

halfn = nob = n / 2; /// 这里也可以通过 >> 1 ，使之高效

/// 先打印上半部分

while (idx < halfn) {

_printWhiteBlank(nob);

_printStar(nos);

_printWhiteBlank(nob);

_printReturn();

idx += 1;

nos += 2;

nob -= 1;

}

/// 打印中间的 *

idx += 1;

_printStar(nos);

_printReturn();

/// 打印下半部分

nos = n - 2;

nob = 1;

while (idx < n) {

_printWhiteBlank(nob);

_printStar(nos);

_printWhiteBlank(nob);

_printReturn();

idx += 1;

nos -= 2;

nob += 1;

}

}

int main(int argc, char * argv[])

{

drawStars(7);

}

```

2. **已知有一个顺序数组，数组中放着 1, 2 ... n 的数字，我们在这个数组中随机抽取出两个数，然后打乱顺序，得到乱序后的数组 randArray；问：数组中抽取出的是哪两个数，怎么做，时间复杂度，空间复杂度。**

参考答案：我只有一个思路哈，我最近也没查。大概思路就是做一个桶，也就是说我们申请一个容量为 n 的数组 bucket，顺序从乱序数组中取数字，比如第一次取出 7，我们把 7 放到 bucket 的下标 7 中，再去一个 3 ，把 3 放到 bucket 的下标 3 中... 当取光了乱序数组之后，遍历桶 bucket，那么随机取出的两个数字就是桶中数字为 0 的下标。这种做法一共遍历了两次，时间复杂度为 O(n)，空间复杂度为一个桶，也就是 O (n)。不过面试官说空间复杂度太高...更优解大家再查查，或者研究研究...

3. **有 25 匹马，5 条赛道，没有计时器，怎么样找出最快的 3 匹马..**

参考答案：面试官提示，这个是二维数组淘汰，于是我就画了一下二维数组，但是这个问题我也没试过...我当时给出的答案是跑 9 次，大概是先分五组跑，得出五组有序的数组，然后拿出一个标识数组的后两个，再拿另一个数组的前三个比赛，跑完后更新标识数组，再拿出下一组...依次类推，一共是跑了九次得到最快的一组，然后前三名就是最快的马了。不过面试官说可以优化的，浪费的信息比较多... 最优解大家还是查查吧；

4. **把一个单位长度为 1 的线段随机分成三份，能够构成三角形的概率是多少？

参考答案：我贴个链接吧，这个算是数学问题.. [参考答案](https://www.zybang.com/question/b1c54cd15031071b7d902710067a8109.html)。

### Other

1. **Weak实现**

2. **反转链表**

3. **Hash table**

# 总结

---

1.面试过程中的很多问题我都记不太清了，在这里把一些有印象的题目分享给大家，当然一些小公司的也有，不过因为面试体验渣等问题..就不多说了...

2.面试问到我网络，我都说我不会...我只知道都是 I/O...网络方面，大家自行搞定吧..

3.很多问题，其实在苹果开源的代码中都能得到具体的答案，不过我比较懒，没咋看，以后希望多看看，更希望大家也都多看看；

4. 希望大家读一读 [深入理解计算机系统](http://product.dangdang.com/24106647.html)这本书，这本书真的讲了很多内容，函数调用、信息表示、CPU、跳转、异常处理、多线程等，出去也有的吹，哈哈。然后再读一本 [深入解析Mac OS X & iOS 操作系统](http://product.dangdang.com/23453263.html)，相信读完之后大家的技术也都精进了很多了..

5. 当然，我在这里更希望大家看很多东西的时候不要看是怎么做的，更多去思考一下为啥这么做... 出去面试就算说不清细节，也能白话一会儿。

# 结束语

> 感谢大家一年多的关心与照顾，无论我离职与否，我都会在心里记得大家，记得这一年多的光阴，希望大家都越混越好。泪奔...