唐磊的个人博客

羡慕,又一清华学弟斩获 6 个大厂 SSP Offer | 面经分享

关于作者:程序猿石头(ID: tangleithu),现任阿里巴巴技术专家,清华学渣,前大疆后端 Leader。欢迎关注,交流和指导!

本文首发于微信公众号,原文链接,转载请全文保留。后台回复关键字 “1024” 获取程序员大厂面试指南。

先摆几句龙门阵

正文前,先摆几句龙门阵。😑

就是这篇文章,为啥比预期来得晚些呢?因为这篇文章肝了好多个周末了,中途因为软件 crash 给肝没了。

心疼

心疼,还好是有学弟的初稿,不是从 0 开始的(不过也基本没了一半 o(╥﹏╥)o)。

加微信好友的朋友都知道,最近我去三亚浪了几天,还顺便去实测了下海南的免税店。不过大家可能感兴趣的 iPhone 是缺货的,最新的 iPhone 12 也一直没货。最近的机票真的是便宜呀,300 块左右就能从北京飞海口,然后本来有 “随心飞”,只需花 50RMB税费即可,租车也便宜,不算保险,几十块一天就搞定。

另外,别看我住的酒店不错,其实是从银行那薅羊毛薅来的。看看下图,带私人泳池的别墅,基本免费(积分兑换),真香。

O(∩_∩)O哈哈~,暴露了石头哥的一个小爱好,平时喜欢薅点小羊毛,朋友圈偶尔会分享类似的小羊毛,感兴趣可以加我哦。

废话

瞎扯几句差不多了,下面还是来一起看看这周的主题吧。

背景

《非科班学弟如何转行斩获 ATM 大厂的 Offer ?》这篇文章中,ZZ学弟作为非CS专业的选手,分享了自己转行互联网,斩获多个大厂 Offer 的经验。

本篇是此系列第 2 篇,我请到了另一个名叫 Patrick 的大牛学弟,他秋招 “身经百战”,最终拿下 6 个 SSP Offer,真的是 TQL,反正我是佩服不已。

今天这篇就是 Patrick 学弟精心总结的面经(包括面经、Offer 选择、感想三部分),我在学弟的基础上做了修改,题目没有完整的答案,但给了答题要点。其实,从某种程度上讲,把答案 “喂” 给你,真心不如你自己去探索答案,这样留下的印象更加深刻,这其实也是一种学习方法啦。(记得之前上学的时候后面复习基本上就是看目录,回忆对应的知识点、考点)

机会总是留给有准备的人的,就看你能不能把握住了。如果这些题目,你能回答个七七八八,可以来找我内推阿里哦,可免简历筛选直通面试(前提是我们团队哈,其他团队可免不了)。

下面我们还是一起来看看学弟的经验总结吧。(后文中的“我”若无特殊注明,特指 Patrick 学弟)

基本情况

我本科和硕士都在清华计算机系,研究生期间研究方向是AI相关,由于对研究方向失去兴趣决定转开发。暑假在某跳动实习,秋招主要投了基础架构方向,从 7 月下旬开始投递和面试,持续到 10 月初,期间面试了 60 多场,拿到了 6 个 SSP Offer。

下面是面试时印象比较深刻的问题,做了大致的分类和整理,有不对的地方也欢迎大家指出讨论,希望能给大家带来收获。

数据结构与算法

  1. 链表分组翻转(注:leetcode)
  2. 矩阵的最大子矩阵和(注:leetcode,子矩阵占据的行的情况有n(n-1)/2种,遍历之后用前缀和)
  3. 求一个数的平方根(注:leetcode,石头多次强调,可参考《从一道面试题谈谈一线大厂码农应该具备的基本能力》
  4. 实现nth_element(注:类似于快排,可参考 《STL 源码剖析》)
  5. O(1)空间复杂度的归并排序(注:从小到大合并)
  6. 给定两组区间,每组区间内部没有重叠,求这两组区间的交和并。
  7. 两个单向链表的第一个交点(注:leetcode经典题目,快慢指针)
  8. 用两个栈模拟队列(注:leetcode经典题目)
  9. LRU Cache(注:面试常见经典题目)
  10. 计算一个含有+-*/()的算术表达式(注:后缀表达式)
  11. 求一个数组前缀和,假设有无限多线程,时间复杂度logn。(注:商汤三面问了这个,当时不会,问了同学才知道是 Parallel Scan)
  12. 如何修改红黑树,使之支持查找第k大的元素。(注:在node中记录子树的大小)
  13. ConcurrentHashMap应该如何设计,怎样加上持久化的功能?要求持久化时不影响并发读写(不能使用fork,因为fork在大内存下也会卡)(注:原子操作、日志、checkpoint、hashmap扩容)
  14. Hashmap冲突时应该如何解决?(注:链表与红黑树)
  15. 描述一下红黑树在插入/删除时怎样保持自身的结构性质的。(注:左旋/右旋)
  16. 介绍一下布隆过滤器
  17. 单例要怎么实现?
  18. 无锁队列是怎么实现的?(注:CAS)

语言与程序

  1. C++的 lambda 表达式是怎么实现的?有什么缺陷和坑?(注:函数对象,悬挂指针和引用)
  2. 介绍一种GC的方法。(注:例如 Go的三色标记,常见的还有 Java 的)
  3. 怎样设计一个内存池和内存分配器。malloc 如何申请大内存和小内存。(注:使用大的内存块,根据申请的内存的大小分桶,brk,mmap,之前石头在面试 MS 的时候也遇到过这个题目)
  4. 介绍程序运行时的内存布局。动态链接库是怎么加载的?动态链接库中的函数是怎样调用的?各种类型的变量是放在什么地方的?(注:.code, .data, .bss、 堆、动态链接库、栈,动态链接器,plt表,got表)
  5. shared_ptr/weak_ptr的工作原理。weak_ptr::lock() 是怎么实现的?(注:引用计数,_Sp_counted_base
  6. 使用过协程吗?说一下你对协程的理解。
  7. 简述一下编译和链接的过程。(注:推荐《程序员修炼之道》)
  8. 描述一下结构体对齐。
  9. C++的虚表,对sizeof的影响,空类的大小,dynamic_cast是怎么实现的。(注:虚表指针、RTTI)
  10. deque是怎么实现的?(注:分块,块之间使用链表)
  11. 设计一个线程池。
  12. 描述vector扩容方法,每次扩容选取什么倍数最好?(注:1.5倍好像更好,但我不知道为什么)

计算机网络

  1. TCP的总体过程,time_wait的时间以及为什么。(注:三次握手、四次挥手、状态机、2MSL)
  2. 简述TCP/IP的每层有哪些协议。(注:TCP/UDP/IP/ICMP/ARP)
  3. 全连接队列/半连接队列是什么? 如何控制他们的大小。(注:通过内核参数和backlog)
  4. 介绍一下IO多路复用。(注:select/poll/epoll, 红黑树, 数据传输量)
  5. 介绍一下HTTP的新版本 。(注:2.0, 二进制协议, 3.0, UDP)
  6. UDP的使用场景是什么,如何保证其可靠性。(注:例如音视频)
  7. 介绍一下HTTPS建立的过程,以及如何避免攻击。(注:公私钥, 证书)

操作系统/体系结构

  1. 简述物理内存管理(buddy system, slab),以及页表的实现方式。(注:四级页表)
  2. CFS基本过程, 包括如何处理新线程和唤醒的线程. 调度的触发时机是什么?(注:时间记账,返回用户态或线程阻塞)
  3. 文件从打开到读写的过程是什么样的?(注:名字解析, inode, fs, mount point, 文件描述符, buffer/cache)
  4. 简述信号处理的基本过程。信号处理函数是如何被调用的,调用后如何返回内核。(注:sigmask, 返回用户态时, sigreturn)
  5. 介绍一下linux的命名空间。(注:pid, rpc, network, …)
  6. 中断处理的主要过程。(注:保存现场, 上半部/下半部, 恢复现场, 工作队列)
  7. 多核处理器是如何启动的?(注:BSP/AP, IPI)
  8. 假设内存有一个数组,要计算数组的和。有什么方法可以进行优化?(SIMD,循环展开)。循环展开的次数受到什么的限制?(L1 cache大小、寄存器数量、寄存器重命名)
  9. 多线程求和的最佳线程数应该怎么确定。(注:这个不是很会, 猜测是CPU核数)
  10. MESI协议。有一段多线程求和的代码,用一个数组a[8]保存每个线程的中间结果(a[i] += nums[j]),问有什么问题。(注:cache ping-pong)
  11. 介绍一下虚拟化是怎么实现的,包括CPU/内存/IO的虚拟化。中断如何注入到虚拟机?影子页表是怎么实现的?(注:Intel VT-x, VMCS, IOMMU, EPT)
  12. 介绍一下死锁。(注:条件,解决方法)
  13. CPU在执行完一个写操作后是否会被其他的核看到?(store buffers)
  14. 怎么实现的内存管理?(注:单页申请/释放物理内存, 4级页表)
  15. 如何保护内核态数据不被用户态访问?(注:权限检查)
  16. 发生异常/中断时如何处理流水线?(注:清空某阶段之前的所有指令)

其他

  1. 介绍一下redis,它是如何实现集群和主从的? 如何持久化?
  2. 联合索引是什么?(数据库不是很懂,每次面试都不太会)
  3. 简述Raft协议的基本过程
  4. 介绍一下两阶段提交
  5. 性能测试是怎么做的? 并发数/QPS是多少?
  6. 实习项目相关。

场景设计

  1. 给定若干个电梯,设计一个电梯调度算法,并给出需要有哪些类。(注:这个答的不太好…)
  2. 在一个游戏场景中有两个AI,他们可以做的操作有: 左移一步,右移一步,判断当前位置另一个AI是否来过,设计一个使他们能相遇的方法。只可以使用三种操作或者根据判断结果进行跳转。AI不知道自己的序号是多少。(注:都向右移动,每移动一次检查一次,检测到对方后不断右移,石头之前面试中也遇到过这个题目)
  3. 设计一个限流器。(注:令牌桶)
  4. 设计一个定时器类,允许添加大量定时器。(注:用堆实现)

智力题

  1. 用两个杯子量出一定体积的水。
  2. 有若干个鸡蛋和一座楼,测量鸡蛋的耐摔程度。
  3. 注:其实这些都是经典问题了,类似的还有 “天平+砝码,称重”、“火柴+绳,计时”等等

行为类面试题

  1. 团队合作
  2. 经历过哪些团队合作?发挥了什么作用?
  3. 在队友不给力时应该怎么做?

Offer选择

考虑到户口问题,可选的offer只有字节,腾讯,小米,阿里,其中小米的薪资是另外两家的60%,阿里随机抽签,字节比腾讯高一点,但在字节的业务不太喜欢,还有大小周的问题,所以最终还是选择了腾讯。

注:其实像阿里这样的应届生户口政策其实对于优秀选手来说是一个“减分项”。因为一般而言,公司在针对应届生户口指标上,都会根据候选人面试的表现结合学校等信息给予一个优先级排序。

但阿里基本上是采取抽签的原则(当然除了极少数例如阿里星或者评级非常好的同学外),大家都一视同仁,虽然做到了公平,但这对于优秀人才的吸引力就不够了:举例在 A 家公司可以有优先的机会(甚至有的可以给到顺序排序),在 B 家就听天由命抽签决定,所以如果考虑到“户口”上,当然就会选中 A 家了。

另外,关于 Offer 选择这块,最近有不少朋友私信石头哥,求建议的。整体来说,我建议,对于大部分普通人来说,校招还是优先选择大公司。如果都是大公司,Offer 太多,怎么选择呢?我之前在《同学,这里有份程序员校招总结等你来取》 中也谈了谈当初校招我是怎样选择的。

其实选择 Offer 无外乎关注以下几个方面:

  • 薪资
  • 团队情况:是否核心,团队整体人员素质,具体业务方向?
  • 地域(城市):消费(主要考虑房价)情况,气候等等?
  • 公司名气:一线大厂?跳槽认可度?
  • 户口:比如北京、上海户口?
  • 公司福利:年假,加班情况等等

每个维度给权重,分别给待选的公司(其实一般最后就纠结两家)打分,最后算加权分即可,哈哈,当然这是一种比较理性(理想)的选择方式,当没有更好方式的时候可以尝试用这个方法。 另外,就是多获取信息输入,可以找更多的朋友(比如可以找石头哥)了解和寻求建议。

感想

  1. 秋招可以多投几家,但不要太多,实习期间大小周+周末面试让人很崩溃。
  2. 日常可以参加一下leetcode周赛/kickstart/codejam。
  3. 春招实习时也可多拿几个offer,我在 2 月份找实习时就投了一家,拿到offer后就回实验室了,但周围同学都拿了好几个。

小结

最后,再次强调,机会总是留给有准备的人,就看你能不能把握住了。上面的题目,你能了解多少?不清楚的地方,正好抓住机会学习了解一下(石头其实也有不少东西不清楚,也趁此学习了一波)。

后记

最后,求关注,求关注,求关注,本号会定期分享一些技术干货、职场经验等,如果大家对阿里或者其他大厂感兴趣,也可以找我内推,我可以帮忙提供简历 review 等,希望能和大家积极交流讨论,一起学习、共同进步。

觉得本号分享的文章有价值,记得添加星标哦。周更很累,不要白 piao,需要来点正反馈,安排个 “一键三连”(点赞、在看、分享)如何?😝 这将是我持续输出优质文章的最强动力。

关于作者:程序猿石头(ID: tangleithu),现任阿里巴巴技术专家,清华学渣,前大疆后端 Leader,欢迎关注,交流和指导!

欢迎扫码加入互联网大厂内推群 & 技术交流群,一起学习、共同进步。后台回复关键字 “0” 送阿里技术大礼包。

tanglei wechat
欢迎扫码加入互联网大厂内推群 & 技术交流群,一起学习、共同进步