腾讯 TEG 一面（已挂）：从三极管问到时间轮算法

《面试题目》

1. 从实习项目入手：项目的瓶颈在哪？（追问非常底层，涉及三极管、计算机组成和汇编）
2. 手撕：实现 string 与十六进制字符串互相转化，先讲位运算的思路。
3. 为什么要用 16 进制？16 进制有什么优点？
4. 场景题：时间轮算法。

《参考解析》

string 与 hex 互转怎么写

编码方向要逐字节处理，并且必须转成无符号类型：unsigned char c = s[i];，否则负数直接参与移位会被符号扩展污染结果。取高低半字节 (c >> 4) & 0xF 和 c & 0xF，查表 "0123456789abcdef" 输出；想输出大写就换表。解码方向先校验长度是偶数、字符合法（否则返回错误而不是静默跳过），再把两个字符合成一个字节 (hi << 4) | lo，大小写都要接受。为了性能可以用一张 256 项的查表把字符映射成 0 到 15，非法值给 -1，这样一次查表替代分支判断，也顺便完成了合法性校验。边界要主动讲：空串、奇数长度、带 0x 前缀、超长输入、UTF-8 多字节字符是逐字节还是逐字符转换（一般按字节）。复杂度是 O(n)，空间 O(n)，可以用 reserve 预分配避免反复扩容。

为什么用十六进制

十六等于 2 的 4 次方，一个十六进制位恰好对应 4 个二进制位，所以字节和十六进制之间是纯位操作、不需要除法和进位。8 位、16 位、32 位、64 位分别对应 2、4、8、16 个十六进制字符，位数永远对齐，人眼可以直接把每个字符翻译成半字节，调试内存和二进制协议时极其方便。十进制和二进制之间不存在这种幂次关系，转换要做反复除法，而且位数对不上；八进制是 3 位一组，在现代 8 位字节体系下不对齐，所以基本只用于文件权限这类 3 位语义。十六进制的另一个优势是定长：哈希值、密钥、MAC 地址、颜色值用十六进制表示时长度固定，便于比较和截断显示。

时间轮算法

时间轮把定时任务按到期时间散列到环形槽（bucket）里，指针每 tick 走一格，走到哪一格就取出该槽的任务执行；槽内用双向链表以便 O(1) 删除。单层时间轮能表示的范围是 tick 间隔乘槽数，超出的任务没法放，所以生产实现都用分层时间轮：比如 Kafka 的 TimingWheel，第一层 tick 是 1 毫秒、20 个槽，超出范围的降级放到上一层，上层的 tick 变成 20 毫秒，逐层往上；随着时间推进，上层槽里的任务会被重新分配回下层。插入和删除都是 O(1)，优于最小堆的 O(log n)，Netty 的 HashedWheelTimer 就是典型实现。

工程上的坑要讲出来：槽内任务需要记「还剩几圈」（remainingRounds），因为同一个槽会被多次经过；当所有任务都很远时要做空推进优化，用 startTime 对齐直接跳格而不是一格一格空转；任务执行必须异步，否则一个慢任务会阻塞整个 tick 线程，导致后续任务全部延迟；取消任务要从链表里摘除并防止内存泄漏；系统时钟回拨要有防护。

「项目瓶颈在哪」这类底层追问怎么答

面试官问瓶颈，实际是在看你对系统能从现象追到硬件有多深的链条。可用的链条是：现象（P99 上升、QPS 打满、超时率上升）→ 度量（perf 火焰图、top -H 看线程、vmstat 看上下文切换、iostat 看 IO、抓包）→ 定位到具体资源（CPU 分支预测失败、缓存未命中、内存带宽打满、锁竞争、GC 停顿、网络重传）→ 优化动作 → 结果复测。从软件一路问到三极管、汇编和计算机组成，考的是你对自己写的东西愿意往下钻多深。答不出就明确说这块不清楚，同时把相邻知识给出来（例如从 CPU 流水线、分支预测、缓存行、指令级并行、内存屏障这些方向说你知道的部分），硬编反而更致命。

手撕题的通用答题流程

先确认输入输出和边界（空、非法字符、大小写、奇数长度、超长）→ 讲思路和复杂度 → 写代码 → 自己举两个例子走查一遍（比如 "\x00\xff" 和 "0F"）→ 最后说优化方向（查表、批量处理、SIMD）。先讲思路这一步在腾讯这类面试里几乎是硬要求，直接沉默写代码会被打断。