网传清华学子斩获6个互联网大厂Offer的面试题汇总

看到这些题目忍不住转过来，觉得能把这些都完整解答，功力不是一般深厚了。有具体的coding、大量算法还有一些常用的基础知识和原理等。

转自微信公众号：程序猿石头，PC版链接：羡慕，又一清华学弟斩获 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. 在队友不给力时应该怎么做？