之前发了这篇 iOS 面试总结（2020 年 6 月），没想到挺受大家欢送，原本是没打算为它写答案，但有几个人倡议我最好出一篇答案，提的人多了我就许可了下来。因为最近比较忙，断断续续总算补完了，就有了这篇文章，心愿它对大家还有用途。这些都属于参考答案，如果大家感觉有不对不精确的中央也欢送指出，我会及时更新。

对于面试题

打个比方，如果把找工作了解成考大学，面试就是高考，市面上的“真题”就是模仿试卷。咱们会很容易偏向于在面试前寻找对应公司的面试“真题”，重点筹备，期待“押题”胜利。但实际上，即便面试同一家公司，它会有不同部门，不同业务线，不同面试官，即便遇到同一面试官，他也不肯定就每次考查齐全一样的内容。想想高考中那些考的好的同学，他们必定不是靠“押题”能力获得好问题吧，他们大多靠的是平时积攒及对知识点灵便把握，那面试也一样啊。执着于搜题，把面试题当做重点进行“温习”，还不如本人划出“考纲”，各个知识点逐个查看掌握情况，温习的更全面呢。

我对于面试题的认识始终是绝对激进的，这类文章个别只是内容搬运，它会存在一些偏差和误读，最重要的那就是几道题往那一扔，并没有产出有价值的货色。这也是为什么我上篇面试总结，会加了一些面试技巧，整顿面试题时，也没提他们是出自哪家公司，就是不心愿大家把题目区别对待。

说了这些并不是说面试题没用啊，而是心愿大家不要科学面试题，更多地去关注那些有品质有深度的技术文章。面试考核的是知识点而不是具体的某些题目，面试题的作用在于，掂量咱们的常识掌握情况，便于咱们查漏补缺，越说越像是针对一次“考试”了????。

总结不易，心愿这份参考答案能对你有所帮忙，如果想继续关注我，欢送订阅微信公众号：iOS 成长之路。

面试题及参考答案

Swift

1、Swift 中 struct 和 class 有什么区别？

struct 是值援用，更轻量，寄存于栈区，class 是类型援用，寄存于堆区。struct 无奈继承，class 可继承。

2、Swift 中的办法调用有哪些模式？

答：间接派发、函数表派发、音讯机制派发。派发形式受申明地位，援用类型，特定行为的影响。为什么 Swift 有这么多派发模式？为了效率。

参考文章：深刻了解 Swift 派发机制

3、Swift 和 OC 有什么区别？

Swift 和 OC 的区别有很多，这里简要总结这几条：

4、从 OC 向 Swift 迁徙的时候遇到过什么问题？

能够参考这篇文章：OC 我的项目转 Swift 指南 里的混编注意事项。

5、怎么了解面向协定编程？

面向对象是以对象的视角察看整体构造，万物皆为对象。

面向协定则是用协定的形式组织各个类的关系，Swift 底层简直所有类都构建在协定之上。

面向协定可能解决面向对象的菱形继承，横切关注点和动静派发的安全性等问题。

参考喵神的面向协定编程与 Cocoa 的邂逅 (上)”)

OC 语法

1、Block 是如何实现的？Block 对应的数据结构是什么样子的？__block 的作用是什么？它对应的数据结构又是什么样子的？

block 实质是一个对象，底层用 struct 实现。

数据结构如下：

struct Block_descriptor {
    unsigned long int reserved;
    unsigned long int size;
    void (*copy)(void *dst, void *src);
    void (*dispose)(void *);
};

struct Block_layout {
    void *isa;
    int flags;
    int reserved;
    void (*invoke)(void *, ...);
    struct Block_descriptor *descriptor;
    /* Imported variables. */
};

• isa 指针，所有对象都有该指针，用于实现对象相干的性能。
• flags，用于按 bit 位示意一些 block 的附加信息，本文前面介绍 block copy 的实现代码能够看到对该变量的应用。
• reserved，保留变量。
• invoke，函数指针，指向具体的 block 实现的函数调用地址。
• descriptor，示意该 block 的附加形容信息，次要是 size 大小，以及 copy 和 dispose 函数的指针。
• variables，capture 过去的变量，block 可能拜访它内部的局部变量，就是因为将这些变量（或变量的地址）复制到了构造体中。

__block的作用是能够获取对应变量的指针，使其能够在 block 外部被批改。通过反编译的代码咱们能够看到该对象是这样的：

struct __Block_byref_i_0 {
    void *__isa;
    __Block_byref_i_0 *__forwarding;
    int __flags;
    int __size;
    int val; // 变量名
};

对于 block 的深刻理解，能够参考《Objective- C 高级编程》第二章或者唐巧的这篇谈 Objective-C block 的实现

2、GCD 中的 Block 是在堆上还是栈上？

堆上。能够通过 block 的 isa 指针确认。

3、NSCoding 协定是干什么用的？

一种编码协定，归档时和解档时须要依赖该协定定义的编码和解码办法。Foundation 和 Cocoa Touch 中的大部分类都遵循了这个协定，个别被 NSKeyedArchiver 做自定义对象长久化时应用。

4、KVO 的实现原理

利用 Runtime 生成一个两头对象，让原对象的 isa 指针指向它，而后重写 setter 办法，插入 willChangeValueForKey 和 didChangeValueForKey 办法。当属性变动时会调用，会调用这两个办法告诉到外界属性变动。

5、NSOperation 有哪些个性，比着 GCD 有哪些长处，它有哪些 API？

NSOperation 是对 GCD 的封装，具备面向对象的特点，能够更不便的进行封装，能够设置依赖关系。

API 能够查看 NSOperation 文档。

6、NSNotificaiton 是同步还是异步的，如果发告诉时在子线程，接管在哪个线程？

同步。子线程。

UI

1、事件响应链是如何传递的？

手势的点击会产生两个重要事件，事件传递和事件响应。

事件传递：从 UIApplication 开始，到 window，再逐渐往上层（子视图）找，直到找到最深层的子视图，其为 first responder。用到的判断办法是 pointInside:withEvent 和hitTest:withEvent。

事件响应：从辨认到的视图（first responder）开始验证是否响应事件，如果不能就交给其下层（父视图）视图，如果能相应将不再往下传递，如果直到找到 UIApplication 层还没有相应，那就疏忽该次点击。用到的判断办法是 touchesBegan:withEvent、touchesMoved:withEvent 等。

这两个过程大抵的相同的。

2、什么是异步渲染？

异步渲染就是在子线程进行绘制，而后拿到主线程显示。

UIView 的显示是通过 CALayer 实现的，CALayer 的显示则是通过 contents 进行的。异步渲染的实现原理是当咱们扭转 UIView 的 frame 时，会调用 layer 的 setNeedsDisplay，而后调用 layer 的 display 办法。咱们不能在非主线程将内容绘制到 layer 的 context 上，但咱们独自开一个子线程通过 CGBitmapContextCreateImage() 绘制内容，绘制实现之后切回主线程，将内容赋值到 contents 上。

这个步骤能够参照 YYText 中 YYTextAsyncLayer.m 文件中的实现形式。

3、layoutsubviews 是在什么机会调用的？

• init 初始化不会触发。
• addSubview 时。
• 设置 frame 且前后值变动，frame 为 zero 且不增加到指定视图不会触发。
• 旋转 Screen 会触发父视图的 layoutSubviews。
• 滚动 UIScrollView 引起 View 从新布局时会触发 layoutSubviews。

4、一张图片的展现经验了哪些步骤？

这个能够参考我之前写的一篇文章 iOS 开发图片格式抉择 中的前半部分内容。

5、什么是离屏渲染，什么状况会导致离屏渲染？

如果要在显示屏上显示内容，咱们至多须要一块与屏幕像素数据量一样大的 frame buffer，作为像素数据存储区域。如果有时因为面临一些限度，无奈把渲染后果间接写入 frame buffer，而是先暂存在另外的内存区域，之后再写入 frame buffer，那么这个过程被称之为离屏渲染。

以暗影为例，为什么它会导致离屏渲染。因为 GPU 的渲染是遵循“画家算法”，一层一层绘制的，但暗影很非凡，它须要全部内容绘制实现，再依据外轮廓进行绘制。这就导致了，暗影这一层要始终占据一块内存区域，这就导致了离屏渲染。

相似导致离屏渲染的状况还有：

• cornerRadius+clipsToBounds
• group opacity 组透明度
• mask 遮罩
• UIBlurEffect 毛玻璃成果

有一篇文章具体的探讨了这些状况：对于 iOS 离屏渲染的深入研究

如果你正在跳槽或者正筹备跳槽无妨动动小手，增加一下咱们的交换群 1012951431 来获取一份具体的大厂面试材料为你的跳槽多添一份保障。

6、CoreAnimation 这个框架的作用什么，它跟 UIKit 的关系是什么？

CoreAnimation 尽管直译是外围动画，但它其实是一个图像渲染框架，动画实现只是它的一部分性能。

看这张图咱们能够晓得，它是 UIKit 和 AppKit 的底层实现，位于 Metal、Core Graphics 和 GPU 之上之上。

苹果官网文档：About Core Animation

援用计数

1、ARC 计划的原理是什么？它是在什么时候做的隐式增加 release 操作？

ARC(Automatic Reference Cunting)主动援用计数，意即通过 LLVM 编译器主动治理对应的援用计数状态。ARC 开启时无需再次键入 retain 或者 release 代码。

它是在编译阶段增加 retain 或者 release 代码的。

2、循环援用有哪些场景，如何防止？

循环援用及两个及以上对象呈现援用环，导致对象无奈开释的状况。个别在 block，delegate，NSTimer 时容易呈现这个问题。

解决方案就是让环的其中一环节实现弱援用。

3、为什么当咱们在应用 block 时里面是 weak 申明一个 weakSelf，还要在 block 外部应用 strong 再持有一下？

block 外界申明 weak 是为了实现 block 对对象的弱持有，而外面的作用是为了保障在进到 block 时不会产生开释。

4、Autoreleasepool 是实现机制是什么？它是什么时候开释外部的对象的？它外部的数据结构是什么样的？当我提到哨兵对象时，会持续问哨兵对象的作用是什么，为什么要设计它？

Autoreleasepool 的原理是一个双向列表，它会对退出其中的对象实现提早开释。当 Autoreleasepool 调用 drain 办法时会开释外部标记为 autorelease 的对象。

class AutoreleasePoolPage {
    magic_t const magic;
    id *next;
    pthread_t const thread;
    AutoreleasePoolPage * const parent;
    AutoreleasePoolPage *child;
    uint32_t const depth;
    uint32_t hiwat;
};

哨兵对象相似一个指针，指向主动开释池的栈顶地位，它的作用就是用于标记以后主动开释池须要开释外部对象时，开释到那个中央完结，每次入栈时它用于确定增加的地位，而后再次挪动到栈顶。

对于主动开释池的底层探索能够看 draveness 的这篇主动开释池的前世今生 —- 深刻解析 autoreleasepool

5、哪些对象会放入到 Autoreleasepool 中？

有两种状况生成的对象会退出到 autoreleasepool 中：

• 非 alloc/new/copy/mutablecopy 开始的形式初始化时。
• id 的指针或对象的指针在没有显示指定时

援用计数带来的一次探讨

6、weak 的实现原理是什么？当援用对象销毁是它是如何治理外部的 Hash 表的？（这里要参阅 weak 源码）

runTime 会把对 weak 润饰的对象放到一个全局的哈希表中，用 weak 润饰的对象的内存地址为 key，weak 指针为值，在对象进行销毁时，用通过本身地址去哈希表中查找到所有指向此对象的 weak 指针，并把所有的 weak 指针置位 nil。

Runtime

1、音讯发送的流程是怎么的？

OC 中的办法调用会转化成给对象发送音讯，发送音讯会调用这个办法：

objc_msgSend(receiver, @selector(message))

该过程有以下关键步骤：

• 先确定调用办法的类曾经都加载结束，如果没加载结束的话进行加载
• 从 cache 中查找办法
• cache 中没有找到对应的办法，则到办法列表中查，查到则缓存
• 如果本类中查问到没有后果，则遍历所有父类反复下面的查找过程，直到 NSObject

2、关联对象时什么状况下会导致内存泄露？

关联对象能够了解就是持有了一个对象，如果是 retain 等形式的持有，而该对象也持有了本类，那就是导致了循环援用。

3、音讯转发的流程是什么？

音讯转发是产生在接收者（receiver）没有找到对应的办法（method）的时候，该步骤有如下几个关键步骤：

• 音讯转发的时候，如果是实例办法会走resolveInstanceMethod:，如果是类办法会走resolveClassMethod:，它们的返回值都是 Bool，须要咱们确定是否进行转发。
• 如果第一步返回 YES，确定转发就会进到下个办法forwardingTargetForSelector，这个办法须要咱们指定一个被用 receiver。
• methodSignatureForSelector用于指定办法签名，forwardInvocation用于解决 Invocation，进行残缺转发。
• 如果音讯转发也没有解决即为无奈解决，会调用doesNotRecognizeSelector，引发解体。

更多理解能够参考 iOS 开发·runtime 原理与实际: 音讯转发篇(Message Forwarding) (音讯机制，办法未实现 +API 不兼容奔溃，模仿多继承) (音讯机制，办法未实现 +API 不兼容奔溃，模仿多继承)”)

4、category 是否增加属性，为什么？是否增加实例变量，为什么？

能够增加属性，这里的属性指 @property，但跟类里的@property 又不一样。失常的 @property 为：实例变量 Ivar + Setter + Getter 办法，分类里的@property 这三者都没有，须要咱们手动实现。

分类是运行时被编译的，这时类的构造曾经固定了，所以咱们无奈增加实例变量。

对于分类自定义 Setter 和 Getter 办法，咱们能够通过关联对象（Associated Object）进行实现。

5、元类的作用是什么？

元类的作用是存储类办法，同时它也是为了让 OC 的类构造可能造成闭环。

对于为甚设计元类有以下起因；

• 在 OC 的世界里所有皆对象（借鉴于 Smalltalk），metaclass的设计就是要为满足这一点。
• 在 OC 中 Class 也是一种对象，它对应的类就是 metaclass，metaclass 也是一种对象，它的类是 root metaclass，在往上根元类（root metaclass）指向本人，造成了一个闭环，一个齐备的设计。

如果不要 metaclass 可不可以？也是能够的，在 objc_class 再加一个类办法指针。然而这样的设计会将消息传递的过程复杂化，所以为了消息传递流程的复用，为了所有皆对象的思维，就有了 metaclass。

对于这一话题的深刻探讨能够参考这两篇文章：

为什么要存在 MetaClass

为什么要设计 metaclass

6、类办法是存储到什么中央的？类属性呢？

类办法和类属性都是存储到元类中的。

类属性在 Swift 用的多些，OC 中很少有人用到，但其实它也是有的，写法如下：

@interface Person : NSObject
// 在属性类别中加上 class
@property (class, nonatomic, copy) NSString *name;
@end
// 调用形式
NSString *temp = Person.name;

须要留神的是跟实例属性不一样，类属性不会主动生成实例变量和 setter，getter 办法，须要咱们手动实现。具体实现办法能够参考这个文章：Objective-C Class Properties

7、讲几个 runtime 的利用场景

• hook 零碎办法进行办法替换。
• 理解一个类（闭源）的公有属性和办法。
• 关联对象，实现增加分类属性的性能。
• 批改 isa 指针，自定义 KVO。

如果你正在跳槽或者正筹备跳槽无妨动动小手，增加一下咱们的交换群 1012951431 来获取一份具体的大厂面试材料为你的跳槽多添一份保障。

Runloop

1、讲一下对 Runloop 的了解？

Runloop 就是一个运行循环，它保障了在没有工作的时候线程不退出，有工作的时候即便响应。Runloop 跟线程，事件响应，手势辨认，页面更新，定时器都有着紧密联系。

深刻理解举荐 ibireme 的这篇深刻了解 RunLoop

2、能够用 Runloop 实现什么性能？

• 检测卡顿
• 线程保活
• 性能优化，将一些耗时操作放到 runloop wait 的状况解决。

性能优化

1、对 TableView 进行性能优化有哪些形式？

• 缓存高度
• 异步渲染
• 缩小离屏渲染

2、Xcode 的 Instruments 都有哪些调试的工具？

• Activity Monitor（流动监视器）：监控过程的 CPU、内存、磁盘、网络应用状况。是程序在手机

  运行真正占用内存大小

• Allocations（内存调配）：跟踪过程的匿名虚拟内存和堆的对象提供类名和可选保留 / 开释历史
• Core Animation（图形性能）：显示程序显卡性能以及 CPU 应用状况
• Core Data：跟踪 Core Data 文件系统流动
• Energy Log：耗电量监控
• File Activity：检测文件创建、挪动、变动、删除等
• Leaks（透露）：个别的措施内存应用状况，查看透露的内存，并提供了所有流动的调配和透露模块的类对象调配统计信息以及内存地址历史记录
• Network：用链接工具剖析你的程序如何应用 TCP/IP 和 UDP/IP 链接
• System Usage：记录对于文件读写，sockets，I/ O 系统活动，输入输出
• Time Profiler（工夫探查）：办法执行耗时剖析
• Zombies：测量个别的内存应用，专一于检测适度开释的野指针对象。也提供对象调配统计以及被动调配的内存地址历史

3、讲一下你做过的性能优化的事件。

这个依据本人状况来说吧。

4、如何检测卡顿，都有哪些办法？

• FPS，通过 CADisplayLink 计算 1s 内刷新次数，也能够利用 Instruments 里的 Core Animation。
• 利用 Runloop，实时计算 kCFRunLoopBeforeSources 和 kCFRunLoopAfterWaiting 两个状态区域之间的耗时是否超过某个阀值
• 子线程检测，每次检测时设置标记位为 YES，而后派发工作到主线程中将标记位设置为 NO。接着子线程沉睡超时阙值时长，判断标记位是否胜利设置成 NO，如果没有阐明主线程产生了卡顿。参考 ANREye 的实现

5、放大包体积有哪些计划？

• 图片压缩，无用图片删除
• 一些大图能够动静下发
• 删除无用类，无用办法
• 缩小三方库的依赖

计算机相关

1、我的项目编译的流程是什么？手机上的应用程序自点击图标开始到首屏内容展现都经验了哪些步骤？

编译流程：

• 预处理：解决宏定义，删除正文，开展头文件。
• 词法剖析：把代码切成一个个 token，比方大小括号等于号还有字符串
• 语法分析：验证语法是否正确，合成形象语法树 AST
• 动态剖析：查找代码谬误
• 类型查看：动静和动态
• 指标代码的生成与优化，包含删除多余指令，抉择适合的寻址形式，如果开启了 bitcode，会做进一步的优化
• 汇编：由汇编器生成汇编语言
• 机器码：由汇编语言转成机器码，生成.o 文件

利用启动的流程：

启动的前提是实现编译，运行程序即运行编译过后的目标程序，它分为 main 函数前和 main 函数后：

main 前

• 加载可执行文件（App 的.o 文件汇合）
• 加载动态链接库（零碎和利用的动态链接库），进行 rebase 指针调整和 bind 符号绑定
• Objc 运行时的初始解决，包含 Objc 相干类的注册，category 注册，selector 唯一性查看
• 初始化，包含执行 +load()、attribute(constructor)润饰的函数的调用、创立 C ++ 动态全局变量

main 后

• 首页初始化所须要配置文件的读写操作
• 首页界面渲染

2、对于根本数据类型，个别是存储到栈中的，它有没有可能存在堆上，什么状况下会存储到堆上？

栈和堆都是同属一块内存，只不过一个是高地址往低地址存储，一个从低地址往高地址存储，他们并没有严格的界线说一个值只能放在堆上或者栈上。所以根本数据类型也是能够存储到堆上的。

当该根底类型变量被 __block 捕捉时，该变量连同 block 都会被 copy 到堆上。

3、数据库中的事务是什么意思？

事务就是拜访并操作各种数据项的一个数据库操作序列，这些操作要么全副执行，要么全副不执行。如果其中一个步骤出错就要撤销整个操作，回滚到进入事务之前的状态。

4、应用过什么数据库（我答复的 Sqlite，Realm），Realm 在应用时有哪些注意事项，如何实现批量操作？

对于 Realm 感兴趣的同学能够看下其官网文档。

Realm 须要留神的次要就是不能间接跨线程拜访同一对象。

批量操作能够在一个独自的事务中执行多个数据库的批改。

5、LRU 算法是否理解，如何实现一套 LRU 算法？

LRU（Least recently used 最近起码应用）算法是一个缓存淘汰算法，其作用就是当缓存很多时，该淘汰哪些内容，见名知意，它的核心思想是淘汰最近应用起码的内容。实现它的关键步骤是：

• 新数据插入到链表的头部
• 每当缓存命中时，则将数据挪动到链表头部
• 链表满时，将尾部数据革除

这个算法在 SDWebImage 和 Kingfisher 等须要解决缓存的库中都有实现。

6、晓得哪些设计模式，怎么了解设计模式的作用？

工厂模式、观察者模式、中介者模式、单例模式。这个依据理论状况说吧。

7、如果有 1000 万个 Int 类型的数字，如何对他们排序？

这里的暗藏含意是，内存不够用时如何排序，还有一个暗藏含意是硬盘足够大。这是能够采纳分而治之的办法，将数据分成若干块，使每一小块满足以后内容大小，而后对每块内容独自排序，最初采纳归并排序对所有块进行排序，就失去了一个有序序列。

8、设计一套数据库计划，实现相似微信的搜寻关键词能疾速检索出蕴含该字符串的聊天信息，并展现对应数量（聊天记录的数据量较大）

能够对聊天记录的文本值加上索引。失常状况下数据库搜寻都是全量检索的，加上索引之后只会检索满足条件的记录，大大降低检索量。

如果你正在跳槽或者正筹备跳槽无妨动动小手，增加一下咱们的交换群 1012951431 来获取一份具体的大厂面试材料为你的跳槽多添一份保障。

简历相干问题

1、Lottie 实现动画成果的原理是什么？

iOS 里的动画根本都是基于 CoreAnimation 里的 API 实现的，Lottie 也是如此。在 AE 上实现动画成果，通过插件导出对应的 json 文件，Lottie 的库解析该 json，转成对应的零碎 API 办法。图片的援用能够应用 Base64 编到 json 里，也能够通过我的项目集成，通过门路援用。

2、OClint 实现动态剖析的原理是什么，它是如何做到的？

具体能够参考我之前写的如何通过动态剖析进步 iOS 代码品质。

3、MVVM 和 MVC 有什么区别？

比照架构时，能够从是否职责拆散，可测试性，可易维护性三个维度比照。

更多比照能够参考我翻译的一篇文章：【译】iOS 架构模式 – 浅析 MVC, MVP, MVVM 和 VIPER

4、动态库和动静库的区别是什么？

动态库：链接时被残缺复制到可执行文件中，屡次应用就多份拷贝。

动静库：链接时不复制，而是由零碎动静加载到内存，内存中只会有一份该动静库。

5、理解 Flutter 吗？它有没有应用 UIKit？它是如何渲染 UI 的？

UIKit 是基于 CoreAnimation 渲染的，而 Flutter 并没有用到它，而是本人基于 C ++ 实现了一套渲染框架。

6、二进制重排的外围根据是什么？

批改链接程序，缩小启动时的缺页中断。

实际步骤能够参考李斌同学的这篇 iOS 优化篇 – 启动优化之 Clang 插桩实现二进制重排

7、如何设计一套切换主题的计划？

外围思路是观察者模式 + 协定（告诉），当获取到主题切换时，告诉各个实现了主题协定的类进行更新。

8、AVPlayer 和 IJKPlayer 有什么区别？用 IJKPlayer 如何实现一个缓存视频列表每条视频前 1s 的内容？

因为对 IJKPlayer 和 FFmpeg 理解的不是很深，这个我也没有确切答案，如果有理解的小伙伴能够评论告知我。

9、相似微博的短视频列表，滑动停留播放，如何实现？

这个次要就是检测 contentOffset 和屏幕两头地位，设置一些边界条件，解决滑动过程中的切换行为。

10、应用 python 做过哪些事？如何了解脚本语言？

多语言治理，csv 多语言文件读取，而后写入到我的项目 Localizable.strings 中；抓取我的项目中的多语言字符串。

脚本（script）其实就是一系列指令，计算机看了指令就晓得本人该做什么事件。像常见的 Python，Shell，Ruby 都是脚本语言，他们通常不须要编译，通过解释器运行。

数据结构与算法

1、什么是 Hash 表，什么是 Hash 碰撞，解决 Hash 碰撞有什么办法？

哈希表（Hash Table，也叫散列表），是依据关键码值 (Key-Value) 而间接进行拜访的数据结构。也就是说，它通过把关键码值映射到表中一个地位来拜访记录，以放慢查找的速度。咱们罕用的 Dictionary 就是一种 Hash 表。

那什么是 Hash 碰撞呢，咱们晓得 Hash 表的查找是通过键值进行定位的，当两个不同的输出对应一个输入时，即为 Hash 碰撞，也被称为 Hash 抵触。

如果应用字典的例子你可能联想不到抵触的状况，咱们假如另一种状况：假如 hash 表的大小为 9（即有 9 个槽），当初要把一串数据存到表里：5,28,19,15,20,33,12,17,10。咱们应用的 hash 函数是对 9 取余。这样的话会呈现 hash(5)=5，hash(28)=1，hash(19)=1。28 和 19 都对应一个地址，这就呈现了 Hash 抵触。

解决 Hash 抵触的形式有凋谢定址法和链地址法。

2、如何遍历二叉树？

二叉树的遍历有三种形式，对于下面这棵二叉树，他们的遍历后果为：

前序遍历：根节点 > 左子节点 > 右子节点。

10，6，4，8，14，12，16

中序遍历：左子节点 > 根节点 > 右子节点。

4，6，8，10，12，14，16

后序遍历：左子节点 > 右子节点 > 根节点。

4，8，6，12，16，14，10

3、简述下疾速排序的过程，工夫复杂度是多少？

快排的思维是通过一趟排序将要排序的数据宰割成独立的两局部，其中一部分的所有数据都比另外一部分的所有数据都要小，而后再按此办法对这两局部数据别离进行疾速排序，整个排序过程能够递归进行。

一个简略的 Swift 实现形式如下：

func quicksort<T: Comparable>(_ a: [T]) -> [T] {guard a.count > 1 else { return a}

  let pivot = a[a.count/2]
  let less = a.filter {$0 < pivot}
  let equal = a.filter {$0 == pivot}
  let greater = a.filter {$0 > pivot}

  return quicksort(less) + equal + quicksort(greater)
}

疾速排序是有好几种的，他们的区别在于如何实现 filter 和分区基准值的选取。

快排的工夫复杂度是O(nlogn)，空间复杂度是O(logn)

4、有一个整数数组，如何只遍历一遍就实现让该数组奇数都在后面，偶数都在前面？

这个是《剑指 offer》里的一道题，leedcode 也有对应题目：剑指 offer 21

这个绝对比较简单，因为不要求有序，能够采纳收尾遍历的形式，进行替换，我这有个参考答案：

func sorted(_ nums: inout [Int]) -> [Int] {
    guard !nums.isEmpty else {return []
    }
    var start = 0
    var end = nums.count - 1
    while start < end {if nums[start] % 2 != 0 {
            start += 1
            continue
        }
        if nums[end] % 2 == 0 {
            end -= 1
            continue
        }
        (nums[start], nums[end]) = (nums[end], nums[start])
    }
    return nums
}

5、假如你正在爬楼梯。须要 n 阶你能力达到楼顶。每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？

leetcode 20

6、给出一个 32 位的有符号整数，你须要将这个整数中每位上的数字进行反转

leetcode 7

7、有红、黄、蓝三种色彩的气球。在牛客王国，1 个红气球 + 1 个黄气球 + 1 个蓝气球能够兑换一张彩票

2 个红气球 + 1 个黄气球能够兑换 1 个蓝气球。

2 个黄气球 + 1 个蓝气球能够兑换 1 个红气球。

2 个蓝气球 + 1 个红气球能够兑换 1 个黄气球。

当初牛牛有 a 个红气球，b 个黄气球，c 个蓝气球，牛牛想晓得本人最多能够兑换多少张彩票。

这个是牛客网里的一道算法题，这里有个题解能够参考。

材料举荐

如果你正在跳槽或者正筹备跳槽无妨动动小手，增加一下咱们的交换群 1012951431 来获取一份具体的大厂面试材料为你的跳槽多添一份保障。