腾讯 WXG 一面面经：白板 coding 与场景设计（90 分钟）

《面试题目》

白板 coding（记事本里手写，限时 40 分钟）

1. 手写小顶堆。
2. 手写单调栈。
3. 手写最大二叉树。
4. 给定一个字符串列表，字符串只由 0 和 1 组成，再给定 m、n，求 1 的个数不超过 m、0 的个数不超过 n 的最大子集。

面试环节

5. 深挖实习项目：你在项目里具体负责什么、遇到的难点是什么？
6. 协程和线程、进程的区别是什么？
7. 场景题：如何实现「点进一个界面查看附近的人」的功能？如果在某个区域，例如演唱会，人特别多呢？

《参考解析》

手写小顶堆。堆的物理结构是数组，父下标 i 对应子节点 2i+1 与 2i+2，核心只有两个操作：上浮（插入到末尾后与父比较、小于父就交换）和下沉（取出堆顶后把末尾元素放到 0 号位，与较小的孩子交换直到满足堆序）。建堆用自底向上的下沉，从最后一个非叶节点开始，整体复杂度 O(n)，而逐个插入是 O(n log n)。白板写的时候容易在三个地方翻车：边界（只有一两个孩子时先比较两个孩子取小的）、循环终止条件（孩子下标越界）、以及 swap 之后下标的推进顺序。小顶堆的典型用途是 TopK 与优先队列，面试官如果追问「找第 K 大」要能立刻说出「维护大小为 K 的小顶堆，堆顶即答案，时间 O(n log K)」。

手写单调栈。单调栈维护的是一个「从栈底到栈顶单调」的下标序列，用来求每个元素左边或右边第一个更大/更小的元素。模板是遍历数组，while 栈非空且栈顶元素不满足单调性就弹栈并处理（此时栈顶下标的答案就是当前下标），然后把当前下标压栈；每个元素最多进出一次，整体 O(n)。常见的变形有接雨水、柱状图中最大矩形、每日温度、以及「左右各求一次组合成区间」。写的时候要明确三件事：栈里存下标还是值（存下标才能算距离）、是严格单调还是非严格（决定相等元素怎么处理）、弹栈时结算的是谁的答案。把这三点先说出来再写代码，比闷头写更容易拿分。

手写最大二叉树。最大二叉树的定义是：根是整个区间的最大值，左右子树由最大值左右两侧的子数组递归构成。朴素分治每层找最大值是 O(n^2)；要做到 O(n) 就得用单调栈：一次遍历维护一个递减栈，遇到比栈顶大的值就把栈顶弹出来挂到当前节点的左子树，最后栈底就是根。这段代码的坑在于「弹出来的节点到底挂左边还是右边」以及最后收尾要把剩余栈自底向上串成右链。白板环境下建议先写 O(n^2) 的分治版本（容易一次写对、能在 40 分钟里交付），口头说明优化到 O(n) 的思路，这样正确性和深度都能体现。

0/1 字符串最大子集。这是二维费用的 0/1 背包：每个字符串的「费用」是它含 1 的个数和含 0 的个数，「价值」都是 1，要求 0 的总数不超过 n、1 的总数不超过 m 时的最大件数。转移方程是 dp[j][k] = max(dp[j][k], dp[j - ones][k - zeros] + 1)，容量维度必须从大到小倒序遍历以保证每个字符串只用一次，时间 O(L×m×n)、空间 O(m×n)。这里特别容易犯的错是想当然地用贪心（按字符串长度排序逐个取）——贪心在二维费用下不成立，随便举两个反例就能推翻，能主动说出「这不是贪心题、要背包」是加分点。若 m、n 比较小（比如几百以内）就能直接 DP；如果容量很大，就要考虑把字符串按 ones、zeros 分桶或做启发式搜索。

协程和线程、进程的区别。进程是资源分配的单位，拥有独立地址空间，进程间切换要陷入内核并切换页表，成本最高；线程是 CPU 调度的单位，同进程内线程共享地址空间，切换只需保存寄存器与栈，但仍由内核调度。协程是用户态的轻量执行单元，调度由运行时（或语言运行时）在用户态完成，切换不进入内核、栈可以按需增长（有栈协程）或由编译器改写成状态机（无栈协程，如 async/await），所以单机可以开到几十万甚至上百万个。代价是：协程不能自动利用多核，必须由运行时把大量协程映射到少量线程上（M:N 模型，如 Go 的 GMP），而且一旦某个协程执行阻塞式系统调用或长 CPU 计算而不让出，会拖住它绑定的线程；此外协程之间共享内存，仍要处理数据竞争。答题时按「谁调度、切换成本、能否利用多核、故障隔离」四个维度对比，并补一句典型选型（Go 的 goroutine 适合高并发 IO，Java 21 的虚拟线程同理，CPU 密集任务仍应交给线程池），答案就完整了。

「查看附近的人」以及演唱会这类高密度场景。基础方案是把用户位置写入支持地理索引的存储：早期用 Redis 的 GEO（底层是 GeoHash + ZSET），按 GEORADIUS 或 GEOSEARCH 查询半径内的点；更通用的是自建 GeoHash 前缀分桶、Uber 的 H3 六边形网格或 Google S2，把二维空间映射到一维网格编号，查询时算「中心格 + 邻接格」再按距离过滤。链路一般是：客户端按频率限制上报位置（比如每 30 秒或移动超过 50 米才上报）→ 位置与网格索引写 Redis（短 TTL）→ 查询时按网格取候选 → 用 Haversine 精算距离并排序过滤 → 缓存热点网格结果。演唱会场景真正的难点不是算法而是量级：成千上万人挤在很小的半径内，单网格候选集爆炸、位置更新写放大、查询 QPS 陡增。工程手段有：把网格按人流量动态细分（密度高的区域用更小的格），对结果只返回 TopN 且允许近似（返回「附近有 XX 人」而不是全量），把位置更新合并成批量写、对同一用户的抖动做去重，热点网格的查询结果做秒级缓存，必要时把「附近的人」降级成「同一场次的人」用非地理维度兜底，并在入口做限流保护下游。答题时先说清基础方案，再主动指出密度带来的差异和降级策略，这比只背 GeoHash 更有说服力。