腾讯 WXG 后端一面：三道算法题开场——IP 与端口打包、分段反转链表、16 位随机数抽 1 万中奖者

《面试题目》

1. 给定 IPv4 地址和端口号，如何将 IP 放入一个 64 位无符号整数的高 32 位、端口放入低 32 位，并输出十进制结果？
2. 如何分别反转单向链表的前半段和后半段？长度为奇数时中间节点保持不动。只有 1 个或 2 个节点时怎么办？时间与空间复杂度是多少？代码报错时你怎么定位问题？
3. 公司有 30 万名员工，如何使用 16 位随机数生成器等概率抽出 1 万名中奖者？抽出人数不足或超过 1 万怎么办？如何证明每个人中奖概率相同？入选边界处出现相同随机数怎么办？
4. 实习是自己找的还是学校安排的？实习中学到了什么？
5. 平时会用 AI 写代码吗？遇到过什么问题？
6. Codex 这类 AI 编程工具的基本原理是什么？
7. 你了解大语言模型的训练和推理吗？
8. RAG 是什么？基本流程是什么？
9. 了解向量检索相关的方法或算法吗？稠密检索、稀疏检索、混合检索和重排序分别是什么？
10. 了解传统搜索引擎的架构吗？了解推荐系统吗？
11. Redis 常见的数据类型有哪些？底层是如何实现的？
12. 跳表是什么？查找、插入和删除分别怎么做？
13. 了解哪些大数据处理组件？消息队列有什么作用？

《参考解析》

打包 IP 与端口的本质是移位加或。IPv4 转成一个 32 位无符号整数（a<<24 | b<<16 | c<<8 | d），然后 (uint64(ip) << 32) | port；输出十进制时注意语言里要按无符号打印（Java 用 Long.toUnsignedString，C++ 用 %llu），因为最高位为 1 时会被当成负数。反向拆解就是 ip = v >> 32、port = v & 0xFFFFFFFF。考点是位运算边界与符号问题，不是乘除法。

分段反转链表先要定「前半段」的定义：偶数长度各占一半，奇数长度中间节点不动、前 (n-1)/2 和后 (n-1)/2 分别反转。实现上先遍历求长度（或快慢指针找中点），再对两段各做一次标准三指针反转，最后把中间节点接回去；边界 n=1、n=2 分别返回原链表与交换。时间 O(n)、空间 O(1)。「代码报错怎么定位」答成流程即可：复现 → 看栈与变量 → 二分注释缩小范围 → 单测小用例（空、单节点、双节点、奇偶）→ 打印或断点确认指针；链表题最常见的错是丢 next、断链和尾部没有置 null。

抽奖题是「随机数区间映射 + 重复处理」的经典。30 万人编号 0299999，16 位随机数只有 65536 个取值，直接 rand()%N 会有偏（不能整除时余数段偏多）且重复严重，所以不能「抽一次删一个」这种 O(n) 空间的做法就完事，要说明取舍：若允许一次性打乱，用 Fisher-Yates 只洗前 1 万名（O(n) 时间、O(1) 额外空间，用随机下标交换）；若必须用 16 位随机数，用拒绝采样把 065535 映射到 0~299999（拼两个随机数或取 r*300000/65536 并对超界区重采），重复则置标记跳过。人数不足就继续抽（有放回抽样），超过就截断；边界重复用「已中奖集合 + 布隆或位图」判重。等概率的证明：每个编号被选中的概率是对称的（Fisher-Yates 的第 i 位来自均匀随机交换），或拒绝采样后映射是均匀的 / 每步独立同分布，用归纳法说明第 k 个位置的条件概率恒为 1/(n-k+1)。

跳表是给有序链表加多级索引：底层存全集，每上一层以 1/2 概率提升，查找从最高层的头节点开始，右边比目标小就往右、否则下一层，期望 O(log n)；插入先查找定位到每层的前驱，随机决定层数后逐层插入；删除是从底层删掉节点、再把上层孤立索引摘掉。相比红黑树，跳表实现简单、范围查询友好、并发下更容易做无锁（Redis 的 zset 就用它）。

RAG 与混合检索按「离线建库 + 在线检索 + 生成」三段讲，检索部分点明稀疏（BM25）管字面、稠密（embedding）管语义、融合用 RRF、重排序用小模型或 LLM 精排，召回 topK 与上下文长度要一起看预算。Redis 数据类型要落到编码：String（int / embstr / raw）、List（quicklist）、Hash（listpack / hashtable）、Set（intset / listpack / hashtable）、ZSet（listpack / skiplist）。消息队列的作用答解耦、削峰、异步、广播与顺序性，顺带说一句重复消费要靠幂等。