网传清华学子斩获6个互联网大厂Offer的面试题汇总
看到这些题目忍不住转过来，觉得能把这些都完整解答，功力不是一般深厚了。有具体的coding、大量算法还有一些常用的基础知识和原理等。
转自微信公众号：程序猿石头，PC版链接：羡慕，又一清华学弟斩获 6 个大厂 SSP Offer | 面经分享。
数据结构与算法
- 链表分组翻转（注：leetcode）
- 矩阵的最大子矩阵和（注：leetcode，子矩阵占据的行的情况有
n(n-1)/2种，遍历之后用前缀和） - 求一个数的平方根（注：leetcode，石头多次强调，可参考《从一道面试题谈谈一线大厂码农应该具备的基本能力》 ）
- 实现
nth_element（注：类似于快排，可参考 《STL 源码剖析》） O(1)空间复杂度的归并排序（注：从小到大合并）- 给定两组区间，每组区间内部没有重叠，求这两组区间的交和并。
- 两个单向链表的第一个交点（注：leetcode经典题目，快慢指针）
- 用两个栈模拟队列（注：leetcode经典题目）
- LRU Cache（注：面试常见经典题目）
- 计算一个含有
+-*/()的算术表达式（注：后缀表达式） - 求一个数组前缀和，假设有无限多线程，时间复杂度
logn。（注：商汤三面问了这个，当时不会，问了同学才知道是 Parallel Scan） - 如何修改红黑树，使之支持查找第k大的元素。（注：在node中记录子树的大小）
ConcurrentHashMap应该如何设计，怎样加上持久化的功能？要求持久化时不影响并发读写（不能使用fork，因为fork在大内存下也会卡）（注：原子操作、日志、checkpoint、hashmap扩容）Hashmap冲突时应该如何解决？（注：链表与红黑树）- 描述一下红黑树在插入/删除时怎样保持自身的结构性质的。（注：左旋/右旋）
- 介绍一下布隆过滤器
- 单例要怎么实现？
- 无锁队列是怎么实现的？（注：CAS）
语言与程序
- C++的 lambda 表达式是怎么实现的？有什么缺陷和坑？（注：函数对象，悬挂指针和引用）
- 介绍一种GC的方法。（注：例如 Go的三色标记，常见的还有 Java 的）
- 怎样设计一个内存池和内存分配器。
malloc如何申请大内存和小内存。（注：使用大的内存块，根据申请的内存的大小分桶，brk,mmap，之前石头在面试 MS 的时候也遇到过这个题目） - 介绍程序运行时的内存布局。动态链接库是怎么加载的？动态链接库中的函数是怎样调用的？各种类型的变量是放在什么地方的？（注：
.code, .data, .bss、 堆、动态链接库、栈，动态链接器，plt表，got表） shared_ptr/weak_ptr的工作原理。weak_ptr::lock()是怎么实现的？（注：引用计数，_Sp_counted_base）- 使用过协程吗？说一下你对协程的理解。
- 简述一下编译和链接的过程。（注：推荐《程序员修炼之道》）
- 描述一下结构体对齐。
- C++的虚表，对
sizeof的影响，空类的大小，dynamic_cast是怎么实现的。（注：虚表指针、RTTI） deque是怎么实现的？（注：分块，块之间使用链表）- 设计一个线程池。
- 描述vector扩容方法，每次扩容选取什么倍数最好？（注：1.5倍好像更好，但我不知道为什么）
计算机网络
- TCP的总体过程，
time_wait的时间以及为什么。（注：三次握手、四次挥手、状态机、2MSL） - 简述TCP/IP的每层有哪些协议。（注：TCP/UDP/IP/ICMP/ARP）
- 全连接队列/半连接队列是什么？如何控制他们的大小。（注：通过内核参数和backlog）
- 介绍一下IO多路复用。（注：select/poll/epoll, 红黑树, 数据传输量）
- 介绍一下HTTP的新版本 。（注：2.0, 二进制协议, 3.0, UDP）
- UDP的使用场景是什么，如何保证其可靠性。（注：例如音视频）
- 介绍一下HTTPS建立的过程，以及如何避免攻击。（注：公私钥, 证书）
操作系统/体系结构
- 简述物理内存管理(buddy system, slab)，以及页表的实现方式。（注：四级页表）
- CFS基本过程, 包括如何处理新线程和唤醒的线程. 调度的触发时机是什么？（注：时间记账，返回用户态或线程阻塞）
- 文件从打开到读写的过程是什么样的？（注：名字解析, inode, fs, mount point, 文件描述符, buffer/cache）
- 简述信号处理的基本过程。信号处理函数是如何被调用的，调用后如何返回内核。（注：sigmask, 返回用户态时, sigreturn）
- 介绍一下linux的命名空间。（注：pid, rpc, network, …）
- 中断处理的主要过程。（注：保存现场, 上半部/下半部, 恢复现场, 工作队列）
- 多核处理器是如何启动的？（注：BSP/AP, IPI）
- 假设内存有一个数组，要计算数组的和。有什么方法可以进行优化？（SIMD，循环展开）。循环展开的次数受到什么的限制？（L1 cache大小、寄存器数量、寄存器重命名）
- 多线程求和的最佳线程数应该怎么确定。（注：这个不是很会, 猜测是CPU核数）
- MESI协议。有一段多线程求和的代码，用一个数组
a[8]保存每个线程的中间结果(a[i] += nums[j])，问有什么问题。（注：cache ping-pong） - 介绍一下虚拟化是怎么实现的，包括CPU/内存/IO的虚拟化。中断如何注入到虚拟机？影子页表是怎么实现的？（注：Intel VT-x, VMCS, IOMMU, EPT）
- 介绍一下死锁。（注：条件，解决方法）
- CPU在执行完一个写操作后是否会被其他的核看到？（store buffers）
- 怎么实现的内存管理？（注：单页申请/释放物理内存, 4级页表）
- 如何保护内核态数据不被用户态访问？（注：权限检查）
- 发生异常/中断时如何处理流水线？（注：清空某阶段之前的所有指令）
其他
- 介绍一下redis，它是如何实现集群和主从的？如何持久化？
- 联合索引是什么？（数据库不是很懂，每次面试都不太会）
- 简述Raft协议的基本过程
- 介绍一下两阶段提交
- 性能测试是怎么做的？并发数/QPS是多少？
- 实习项目相关。
场景设计
- 给定若干个电梯，设计一个电梯调度算法，并给出需要有哪些类。（注：这个答的不太好…）
- 在一个游戏场景中有两个AI，他们可以做的操作有: 左移一步，右移一步，判断当前位置另一个AI是否来过，设计一个使他们能相遇的方法。只可以使用三种操作或者根据判断结果进行跳转。AI不知道自己的序号是多少。（注：都向右移动，每移动一次检查一次，检测到对方后不断右移，石头之前面试中也遇到过这个题目）
- 设计一个限流器。（注：令牌桶）
- 设计一个定时器类，允许添加大量定时器。（注：用堆实现）
智力题
- 用两个杯子量出一定体积的水。
- 有若干个鸡蛋和一座楼，测量鸡蛋的耐摔程度。
- 注：其实这些都是经典问题了，类似的还有 “天平+砝码，称重”、“火柴+绳，计时”等等
行为类面试题
- 团队合作
- 经历过哪些团队合作？发挥了什么作用？
- 在队友不给力时应该怎么做？
Loading ...
