腾讯WXG 暑期实习面经 [OC]

个人情况

西南某末流985大三
绩点年级前3%
无实习经历
项目偏硬件(基于MIPS指令集的五级流水线CPU设计, 使用Verilog编写)
刷了70道Leetcode, 耗时近一周
八股复习了两天, 主要是C++、OS和计网

面试进度

3.31 一面 [提前一周约面]
4.7 二面 [提前2小时邮件通知 - -!]
4.8 HR面
4.8 云证
4.9 OC

一面

"先来做几道题"(40min)

1. 二叉树层序遍历 (Leetcode原题)
2. 滑动窗口的最大值 (Leetcode原题)
3. 反转链表 (Leetcode原题)
第一题和第三题: 5分钟秒了, 甚至反转链表的递归和迭代都写了
第二题: 之前没有做过, 写了个`O(n²)`的解法, 面试官不是很满意, 然后我优化成`O(nlogk)`, 事后去LeetCode学习了O(n)的方法

项目+八股

介绍一下你的 MIPS指令集的五级流水线CPU设计的项目
流水线的作用
中断的作用, 中断的种类
时间片调度是怎么实现的, CPU怎么判断时间片结束了
Cache的作用
CPU取指令是从内存吗
CPU是直接访问进程的地址空间吗
进程切换的开销
进程切换和线程切换的区别, 页表需要切换吗
CPU频繁切换进程, 性能损失主要是因为什么
多线程, 保护临界数据的措施
多进程同步和多线程同步的区别
怎么申请共享内存 (不了解)
讲讲协程
C++你用过哪些容器
unodered_map和map, 底层数据结构的区别
unodered_map怎么解决hash冲突 (不了解)
vector怎么扩容
使用迭代器, 一般要注意一些什么问题 (我只说了类型问题, 应该还要考虑越界之类的, 迭代器不太熟悉)
new / malloc 的区别 (我只说了参数和返回值的区别, 其余当时并不清楚, 其实还有构造析构对象和自由存储区等等)
C++怎么实现多态
虚函数表什么时候时候创建的 (我答错了, 答的对象构造时, 应该是编译时)
虚表指针什么时候时候创建的
了解HTTP和HTTPS吗 (不了解)
TCP / UDP 区别
TCP 流量控制 / 拥塞控制区别
拥塞控制的几种算法
拥塞控制, 慢开始的过程
time_wait状态的作用
有学习过一些网络安全相关的知识吗 (没有)
有用过一些数据库吗 (这学期正在学, 没有用过)
有接触过一些微服务相关的概念或者组件吗 (没有)
什么时候能来实习

因为我没有学过数据库和微服务相关的, 并且第2道算法题做得不好, C++也有答错一些, 以为凉了
一周后收到二面邮件, 12点收到邮件, 14点二面

二面

两道情景编程题(60min)

开发一个直播间监控系统，需求：
①管理所有直播，新开播就加入到系统，直播结束就从系统去掉
②直播间热度不断变化，热度出现变化时往系统更新这个直播当前热度值
③运营人员日常巡查希望可以在任何时刻都知道当前热度最高的100个直播间
根据上述需求，请设计实现一个类(直播间的属性有id和热度)
30万个员工，工卡是1-30万，抽出10万个员工发奖。
已有一个随机数生成函数rand()能够生成0-65535的整数，写一个公平的抽奖程序，输出这10万个员工的工卡号码
(进阶：30万抽99999个员工)

八股

vector底层
set底层 (我说的是哈希表, 答错了, 应该是二叉树)
讲讲TCP滑动窗口
讲讲虚拟内存, 以及它解决了什么问题
快排的时间复杂度, 最好, 最坏, 什么时候最坏

第一道情景题, 一开始写了一个复杂度很高的思路, 并且因为一些语法很久没用生疏了, 并没有完全写出来...
后来大致讲了一下思路, 大概就是topK的思路, 创建和删除是O(1), 查询top100是O(nlog100)
第二道情景题, 之前有刷到过, 三分钟秒了

面完之后以为凉了, 过了3分钟之后刷新, 居然直接到HR面了, 受宠若惊