今年投移动端人的特别少, 准备面试的时候都查不到什么资料, 而且自己这么菜都有人要emmm
自己真正走完流程的也就这一家, 感觉秋招还是挺顺利的, 虽然 BAT 之类的面试机会都没有, 但最先面试的美团直接通过了, 也没什么可遗憾的. 比起面经更像是自己记录一下过程, 乱七八糟的可能会有点多, 有些自己当时不熟悉并且重要的知识点之后再详细补上吧, 再不写点多西自己都闲得长毛了.
目录
预习
学校讲的课emmm基本没用, 还是得自己另学. 书籍的话, 准备面试的时候网络看了《计算机网络自顶向下方法》, 计原, 或者说编译原理方向看了《程序员的自我修养链接装载与库》算法因为时间不够, 刷了两遍多《剑指offer》, 因为现在还是 OC 主流, 补了下 OC 基础, 看了《Objective-C编程全解》《Objective-C高级编程: iOS 与 OS X 多线程和内存管理》. 其他的书都是之前积累的了, 太多了不列举了.
一面(电话面试)
8月31号投的简历, 没想到进了提前批, 没过几天就电话面试了, 免了笔试, 因为当时还没怎么准备好(当然多长时间也准备不好的), 也没抱什么希望.
自我介绍
从来没有面过技术面, 就介绍了一下自己的专业(因为是五年制, 说明了一下), 兴趣爱好, 和简历上的项目.
被问到了学校都有哪些课程, 和电有关的专业都会学到的数学, 电路理论, 模电, 数电; 计算机基础的离散数学, C语言, C++; 比较重要的编译原理, 网络, 组成原理, 操作系统; 工程方向的专业选修, 以及数据库, 软件工程之类的. 哦对, 还有日语课, 专业本身是挺好的, 就是课程安排不合理, 我在准备秋招的时候, 从日本交流回来的同学才开始学 C++, 也是有意思.
程序运行时内存的分布
-
BSS段用于存放未初始化的全局变量, 程序开始运行之后会被清空, 静态分配
-
数据段用于存放初始化后的全局变量, 静态分配
-
代码段用于存放代码
-
栈区用于存放自动变量, 以及函数调用, 由系统管理内存分配
-
堆区用于存放动态分配的内存, 要由程序员手动进行管理
又简单说了一下栈区和堆区的区别, 不多写
进程和线程的区别
进程是操作系统资源分配的最小单位, 线程是处理机分配的最小单位, 一个程序至少有一个进程, 一个进程至少有一个线程. 进程间内存虚拟地址是独立的, 而线程间内存是共享的.
被问到线程间共享的内存是上面内存分布是提到的哪些区域, 因为线程之间是可以并行的, 所以和函数调用相关的栈内存不可以区享, 而是每个线程都佳能自己独立的栈区, 堆区内存是可以共享的. 至于共享内存会出现的同步问题, 可以用线程锁或者信号量解决, 又简单说了下锁和信号量.
一个程序从编译到运行的全过程
-
宏定义展开
-
词法分析
-
语法分析
-
语义分析
-
中间代码生成
-
中间代码优化
-
生成机器码
-
链接
-
装载到内存运行
其中链接详细问了一下, 就把静态链接和动态链接的区别, 优缺点解释了一下.
网络分层
OSI 的七层当时硬是没想出来, 就按 TCP/IP 四层结构详细地讲了一遍, 因为啃过自顶向下方法那本计算机网络书, 所以自我感觉说得可以, 面试官也没多问.
HTTPS 的原理
因为我说过自己有信息安全的课程, 就问我课上都讲了什么, 其实课上也就是科普了一下加密及运用, 以及防火墙之类的东西, 自然而然地就问了下我 HTTPS 是怎么实现安全的传输的. 提了下使用非对称加密通过证书机构来验证服务器身份, 并交换对称加密的密钥, 验证身份后使用对称加密来传输数据以减少资源和时间浪费, 本来想详细说明一下过程的, 没让我讲完…
面向对象的特点
封装, 继承和多态, 然后举了例子说明了一个程序如果用面向过程的思想应该怎么写, 用面向对象的思想应该怎么写
swift 中的值类型和引用类型
讲面向对象的时候我用了 C++ 和 swift 进行了比较, 所以就问了下 swift 的问题. 值类型的变量可以保证变量本身不会被其他变量所修改, 而引用变量则可能会被其他引用(指针)对变量指向的内存进行修改. 值类型因为赋值或修改会进行复制, 会浪费性能, swift 中使用写时复制的机制来提高其性能.
举了很多值类型的例子, 所以问我如果只有值类型可不可以, 使用指针那样的机制也可以达到同样的效果. 懵了一下, 回答说那样就不能进行多态了, 然后马上意识到自己说得不对…使用指针操作值类型本身就是按照引用类型的语义来操作值类型, 还不如直接使用引用类型更容易理解一些. 和何况有些情况使用引用类型本身各贴近正常的思维, 比如一个人的多个身份相当于这个人的多个引用, 指向这个人本身.
求数组中前 k 大的数字
《剑指 offer》上的原题, 就回忆了一下:
- 数组大小 n 比较小
直接排序取前 k 个就好了, 本身也花不了多长时间, 使用快排的话时间复杂度就是 O(nlogn).
- n 很大
用于一个 k 个元素的小顶堆, 将数组中的元素入堆, 堆满之后, 下一个元素比堆顶大就弹出堆顶, 新元素入堆, 否则跳过. 相当于堆里始终存放着当前最大的 k 个元素. 小顶堆建立的过程中时间复杂度为 O(klogk), 之后每次堆的复杂度为 O(logk), 即若 k 远远小于 n 的话, 时间复杂度为 O(nlogk).
因为题目很简单, 所以问得特别细, 问了快排和堆排为什么时间复杂度是 O(nlogn). 快排每一轮都是O(n), 每轮相当于将数组分成一半, 所以排了 logn 轮(以2为底); 堆排每次调整最多要调整的次数就是堆的深度, 即 logn (以2为底).
额, 智力题
一个函数foo()会返回0或1, 概率分别是 70% 和 30%, 设计一个函数bar(), 使其返回0和1和概率各为 50%.
之前没做过这种题, 一脸懵逼, 然后想到调用两次foo()都返回0的概率是 70% * 70% = 49% , 和 50% 差不多了, 面试官应该没见过这样的操作, 也懵了hhh, 说这个方法不太好, 要是换成0和1的概率是 80% 和 20% 就行不通了, 让我再想.
后来提示我运行两次结果为01和10的概率是相同的. 当时我给出答案:
运行两次
foo(), 当结果为01时, 返回0, 结果为10时, 返回1, 其余情况不返回, 重新运行, 直接有返回为止.
现在想00, 11的概率也是相同的, 可以把00, 01分为一组, 11, 10分为一组, 就不用轮空了.
接着又问我如果还是用这个函数foo(), 设计一个随机数函数返回0到9之间的随机数应该怎么做. 根据上面的做法, 用二进制表示返回值, 9是4位二进制数, 那么运行bar()函数4次, 如果结果大于9就轮空, 否则返回.
学习 iOS 的途径
感觉学校里做 iOS 的也就我一个人了, 就谈了谈自己看过的官方文档, 书籍, 视频和博客, 以及查资料的方法. 之后闲聊几句就结束了.
二面
感觉一面很基础, 也挺简单, 但是后面智力题尬了好久, 有些担心会被刷, 结果第二天就通知我去北京总部面试. 反正不会有大公司来大连面试的, 没多想就买了小火车票, 面不上就当是见见世面了.
链表排序
一开始问我电话面试感觉怎么样, 傻傻地说了算法可能没回答好, 然后面试官就说那好我们先写个算法吧orz, 就让我写个给链表排序的算法. 算法写得少, 从来没给链表排过序…想了好久, 写了个抠脚的O(n^2)的插入排序, 还好没写错, 想着上来就写成这样应该是凉了.
接着问我复杂度是多少, 有没有更快的方法, 我就给理了一下归并排序的实现, 发现取链表中点不好取, 就使用一个指针沿链表走一步, 另一个走两步的方法. 之后立即发现了, 找中间的复杂度就已经是O(n)了, 再加上归并本身的O(nlogn), 更慢了……
又问我快排行不行, 想了一下, 快排的实现并没有信赖数组的线性储存特点, 可以进行O(nlogn)的排序, 写出来也很简单:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ListNode* partition(ListNode* start, ListNode* end) {
int key = start->value;
ListNode* p = start;
ListNode* q = p->next;
while (q != end) {
if (q->value < key) {
p = p->next;
swap(p->value, q->value);
}
q = q->next;
}
swap(p->value, start->value);
return p;
}
void qsort(ListNode* start, ListNode* end) {
if (start == nullptr || end == nullptr) {
return;
}
if (start != end) {
ListNode* mid = partition(start, end);
qsort(start, mid);
qsort(mid->next; end);
}
}
还是一道小智力题orz
真是怕什么来什么, 又问一道智力题, 6个候选人, 5个裁判, 设计一个公平的算法, 给候选人进行排序, 不允许并列.
出完题面试官就用我手机进我博客里看了(就是你现在看的这个), 我一直在想具体的实现应该怎么做, 结果面试官看完了, 我还是没有具体的方案. 面试结束后问了下这题应该怎么做, 得到的答案也很笼统, 大意就是设置好梯度…
在 swift 协议中做用泛型
其实就是associatedtype, swift 的协议中没有泛型, 因为协议是用来实现多继承, 或者模范一个类的实现, 我们可以让一个类实现一个协议, 但不会创建多个协议本身. 所以比起协议泛型, associatedtype这种类型别名的方式更适合.
可惜的是, 平时泛型用得少, 当时我忘了这个关键字就什么了, 只记得实现类的时候要对associatedtype的别名进行typealias绑定到已有的类型上…
编译, 链接过程
和一面问得差不多, 但在动态链接上问得更加详细, 编译出的二进制文件中指令操作的地址是写死的, 但动态链接库在加载时人位置不确定, 如何保证程序正常运行. 因为编译的时候不知道动态链接库的位置, 所以编译后二进制文件中动态库的地址只是占位用, 在程序装载到内存准备运行时, 会把动态库的位置替换掉原来的占位符. 当时意思是答出来了, 不知道对方有没有理解.
学习途径
说我课程时并没有 iOS 相关的东西, 为什么学起了 iOS. 就把一面时那些东西又说了一遍
最近学习过程中有什么知识点值得一提的
想着这是最后发挥的机会了, 就把准备面试过程中 OC 和 swift 的 block 原理从头到尾讲了一遍(之前文章里有写), 感觉面试官很满意.
二面一开始, 手表就提示我心率过速, 中间又提示了好几次. 面完还问了下面试官是不是自己要凉, 对方告诉我没事, 可能自己身边没人交流, 有些知识点发散得不够, 其实学过的东西还是挺扎实的.
三面
本来都以为 HR 会让自己回去了, 结果三面的面试官过来了, 顿时觉得自己还有救. 面试官刚过来就让我看一下他的牌, 说自己是美团移动端的技术总监, 当时太紧张, 上面写的什么一个字也没看进去. 一开始和我谈学校还有家里住哪之类的还以为对方是 HR, 第二天 HR 电话通知我结果的时候才知道是安卓和 iOS 双修, 两头都管的真dalao…
各种排序
还是问了下上一面都问了什么, 这回我学聪明了点, 没提智力题的事, 就说链表排序之前没写好, 费了点时间, 果然让我讲一下常用的排序. 这个肯定要好好复习的, 详细地说了一遍. 之后问了有没有O(n)的排序方法, 就提了下使用 hash, 以及基数排序.
各种 swift
我还纳闷怎么不问 iOS 相关的东西, 结果都攒到三面问了…因为我说过一直用的是 swift, 就问我 swift 与 OC 相比好在哪里, 把自己想到的都说了, 说了好久.
- 值类型&引用类型
除了一面时说的那些, 举例说明了一下值类型(struct 和 enum)和引用类型(class)的使用, 说mutation函数的时候被吐槽日语学多了英语不会读.
- 泛型
没怎么用过, 所以没说太多, 简单地和 OC 这种基本没泛型的语言比较了一下.
- 异常处理
try, catch这种语言上定义的异常处理自然要比NSError这种没有语言约束的错误处理要强, 可以强制程序员在处理会抛出异常的函数时会对错误情况进行思考写出catch条件, 而不是简单地传进一个nil指针. 同时 swift 的类型匹配以及强大的枚举类型使得可以更方便得通过抛出的Error得出异常信息, try, catch性能上的损失也远比 C++ 这要少.
- 枚举
就 siwft 中的强类型的枚举和C语言中可以用int替换的枚举进行对比, 又讨论了枚举的关联值和原始值, 还结合了一下上面提到的异常处理.
- 可选值
提到枚举又想到了可选值, 批判了NULL的问题, 讲了下可选值的解包, 可选链. 和面试官讨论了强制解包的坏处, 以及自己实践过的数组越界是不让其崩溃, 而是返回nil时带来的问题.
项目
项目没问太细, 只是了解了一下是做什么的, 用了什么技术, 用这些技术的原因.
有没有看今年的 WWDC
三面还是谈人生谈理想的东西多一些, 让我说一下对 iOS 发展的看法, 以及今年 WWDC 上有什么技术想和他说一说. 因为一直以来使用的都是越狱的 iOS, 就对苹果封闭生态的优缺点谈了谈, 认为就像逐步开放输入法, 通知中心, 分享菜单, Siri Kit 等, 越来越开放才是趋势. WWDC 这头谈了自己对ARKit以及Create ML的看法, 好在自己还真看了 WWDC, 虽然自己从来没用过, 吹吹牛逼还是可以的.
最近在看什么书, 有什么可以值得分享的
说了几本准备面试时看的 iOS 底层的书, 然后提了下之前研究过的 OpenWRT 路由和 IPv6 NAT(之前文章有写). 面试官之前做过网络, 就问了下 NAT 的实现, 怎么解决 IP 不足的. 详细地解释了一下.
介绍岗位
之后就没什么正经问题了, 给我介绍了下部门规模, 做什么业务, 最后问了下我对美团 app 的看法, 和对面试的评价, 就结束了.
本来二面觉得自己凉了, 三面之后完全没有这种感觉, 没让我想到的是面完后三面面试官开车送我到地铁站, 把我吓坏了…