教师资格考试因疫情无法面试可申请退费 2020年6月最新iOS面试题总结（答案篇）

教师资格考试因疫情无法面试可申请退费 2020年6月最新iOS面试题总结（答案篇）， 

教师资格考试因疫情无法面试可申请退费

受疫情影响，我省2021年下半年中小学教师资格考试面试期间，国内个别地区采取临时管控措施，有少数考生因此无法参加考试。根据教育部教师司和考试中心要求，可以为此类考生办理面试报名费退费，其笔试合格科目有效期将自动延长半年。现将有关事宜通知如下。

一、受理人员范围

安徽省16个考区中受疫情影响无法按时参加教师资格考试面试的考生。2022年1月8日-10日

二、申请材料

申请退费的考生，须在2022年1月14日17点前，按照要求提交退费申请材料如下：

1．考生退费申请表（附件1）。

2．考生本人考试预留手机号申请的“全国通信大数据行程卡”截图。截图应清晰完整。全国通信大数据行程卡。

3．考生至少提供1项能证明本人因疫情防控被限制出行的材料（如手机短信截图、所在社区张贴的相关通知、所在学校发布的相关通知、当地疫情防控部门发布的相关通知等）。其他证明材料。

三、提交方式

申请退费的考生应在规定时间内，将“考生退费申请表”、“全国通信大数据行程卡”以及“其他证明材料”的电子版打包发送至本人所报考考区的指定邮箱（附件2）。申请材料包命名格式为“考区+姓名+准考证号”。逾期或未按要求提交的退费申请将按照无效申请处理，责任由考生本人承担。

四、审核及退费程序

所在考区对申请材料进行审核。经审核通过后，由考区将符合退费条件的考生相关材料统一报送安徽省教师资格指导中心，并由安徽省教师资格指导中心统一报送教育部考试中心进行退费处理，所退费用按考生报名缴费时原缴费渠道返还考生。完成退费的考生，后续可登录中国教育考试网（http://ntce.neea.edu.cn/）“考生服务”栏目查看更新后的笔试成绩有效期。

往

安徽疾控发布紧急健康提示

期

大量入编！安徽事业单位最新招聘

推

安徽3市获国家级支持

荐

最新！安徽省工资价位表来了

来源| 安徽省教育厅

责编|何文艺编辑| 顾盼

主办单位| 安徽省政府新闻办、省网信办

平台建设及技术支持| 安徽新媒体集团

来源：安徽发布

发布于：北京


2020年6月最新iOS面试题总结（答案篇）

来自网络，笔记自用

关于面试题

打个比方，如果把找工作理解成考大学，面试就是高考，市面上的“真题”就是模拟试卷。我们会很容易倾向于在面试前寻找对应公司的面试“真题”，重点准备，期待“押题”成功。但实际上，即使面试同一家公司，它会有不同部门，不同业务线，不同面试官，即使遇到同一面试官，他也不一定就每次考察完全一样的内容。想想高考中那些考的好的同学，他们肯定不是靠“押题”才能取得好成绩吧，他们大多靠的是平常积累及对知识点灵活掌握，那面试也一样啊。执着于搜题，把面试题当做重点进行“复习”，还不如自己划出“考纲”，各个知识点逐一检查掌握情况，复习的更全面呢。

我对于面试题的看法一直是相对保守的，这类文章一般只是内容搬运，它会存在一些偏差和误读，最重要的那就是几道题往那一扔，并没有产出有价值的东西。这也是为什么我上篇面试总结，会加了一些面试技巧，整理面试题时，也没提他们是出自哪家公司，就是不希望大家把题目区别看待。

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

面试题及参考答案

Swift

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

struct是值引用，更轻量，存放于栈区，class是类型引用，存放于堆区。struct无法继承，class可继承。

2、Swift中的方法调用有哪些形式？

答：直接派发、函数表派发、消息机制派发。派发方式受声明位置，引用类型，特定行为的影响。为什么Swift有这么多派发形式？为了效率。

参考文章：深入理解 Swift 派发机制

3、Swift和OC有什么区别？

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

Swift Objective-C

语言特性 静态语言，更加安全 动态语言，不那么安全

语法 更精简 冗长

命名空间 有 无

方法调用 直接调用，函数表调用，消息转发 消息转发

泛型/元组/高阶函数 有 无

语言效率 性能更高，速度更快 略低

文件特性 .swift 单文件 .h/.m包含头文件

编程特性 可以更好的实现函数式编程/响应式编程 面向对象编程

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离屏渲染的深入研究

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不兼容奔溃，模拟多继承)

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。

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、设计一套数据库方案，实现类似微信的搜索关键词能快速检索出包含该字符串的聊天信息，并展示对应数量（聊天记录的数据量较大）

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

简历相关问题

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(_ 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个蓝气球，牛牛想知道自己最多可以兑换多少张彩票。