Go 手写题与连续追问

本章选两道与简历直接相关的题：DAG 拓扑排序和支持取消的有界工作池。目标是检验独立编码、边界意识和解释能力。它们是独立教学实现，没有改动 Flostra、Gline 或 Nyauth 的业务代码。

完整可运行答案见 answers.go，关键行为验证见 answers_test.go。练习时先隐藏答案，只看题目写 15–20 分钟，再用追问检查自己的设计。

1 手写环节的真实流程

用一两分钟复述输入、输出、异常和规模，确认题意。
说明数据结构与核心不变量，不急着写完整代码。
写主流程，优先让正常与失败路径都能结束。
用普通输入、边界输入和一个失败场景手工演算。
说明复杂度和实际系统还缺什么，接受条件变化后的追问。

遇到问题应解释哪里不确定，避免一边沉默修改一边试图碰到正确输出。

2 追问树

K1 返回工作流的一个合法拓扑顺序
├─ K1.1 重复边 孤立节点和非法 ID 如何处理
├─ K1.2 为什么处理数量不足就说明有环
│  └─ K1.2.1 剩下的节点全是环上的节点吗
└─ K1.3 有拓扑顺序是否就能并发执行
   ├─ K1.3.1 A→B A→D B→D 该怎样执行
   └─ K1.3.2 前驱失败或分支跳过怎么办
K2 实现有界并发映射 保序 支持取消和失败返回
├─ K2.1 为什么结果写入不需要全局锁
│  └─ K2.1.1 如果改成 append 或共享指针呢
├─ K2.2 谁关闭 jobs 谁等待 Worker
│  └─ K2.2.1 context 能停止永远阻塞的 fn 吗
├─ K2.3 第一个错误怎样安全返回
│  └─ K2.3.1 是否能保证取消后绝不再调用 fn
└─ K2.4 输入有一千万个任务怎么办
   └─ K2.4.1 如果必须全局保序 如何限制内存

K1 工作流拓扑排序

**题目：**节点编号为 [0,n)，边 [u,v] 表示 u 必须先于 v 完成。返回任意一个合法拓扑顺序。存在环或非法输入时返回错误，不返回可被误用成完整结果的部分顺序。重复边表示同一个依赖，允许空图。

**参考解法：**使用 Kahn 算法。邻接表保存后继；入度记录每个节点还需要消除多少依赖。把所有零入度节点加入队列，取出一个节点就将它的后继入度减一，减到零再入队。实现将结果切片同时作为队列，以 head 下标前移，避免不断从头复制切片。

**正确性说明：**节点只有在所有入边都已被消除时才能入队，因此输出时其所有前驱已经在它之前。若存在环，环上的节点无法互相解除最后一条入边；如果输出了全部 n 个节点，则不存在这种残余依赖。

**复杂度：**使用哈希集合对边去重时，期望时间为 O(V+E)，额外空间 O(V+E)。如果要求每次都选编号最小的就绪节点，可把队列改成最小堆，会增加排序成本；题目没有这个要求，所以不增加复杂度。

K1.1 重复边孤立节点和非法 ID 怎么处理

**触发：**面试官检查你是否只实现 happy path。

**参考回答：**重复边先去重，避免把一项依赖重复计数；孤立节点入度为零，正常进入结果；节点编号越界或 n 为负直接报错。自环属于有环，不是一个可以忽略的重复边。重复边也可以选择每次都计数并对称消除，但必须保持一致；本答案明确采用去重契约。

K1.2 为什么处理数量不足就说明有环

**触发：**候选人使用 len(order) != n。

**参考回答：**当队列为空时，剩余节点都仍有来自剩余集合的入边。在有限图里持续沿前驱寻找，必然重复遇到某个节点，从而形成环。这个论证依赖节点和边已校验、入度更新正确；不能用这个条件掩盖实现漏处理某条边的问题。

K1.2.1 剩余节点是不是全在环上

**触发：**面试官要求返回环的具体位置。

**参考回答：**不是，依赖于环的下游节点也可能残留。Kahn 适合判断是否存在环；若要返回一个环路径，可以使用 DFS 的递归栈/颜色状态；如果要找所有循环组件，可以计算强连通分量。不要把所有剩余节点都标为环成员。

K1.3 有了拓扑顺序是否就能把列表直接并发运行

**触发：**题目转向真实 Flostra 调度。

**参考回答：**不能。拓扑顺序只保证顺序执行时依赖合法；并发执行要在前驱真正完成、输出可用后才解除后继依赖。不能在“任务已启动”时就减少完成依赖数，也不能因为上游之一有输出，就认为所有必需输入已经满足。

K1.3.1 A→B A→D B→D 怎样执行

**触发：**候选人把并发分层说得过于简单。

**参考回答：**先执行 A。A 完成后 B 就绪，但 D 仍等待 B，因此 B 完成后才能执行 D。对无依赖的其他节点可以并发。这个不等深汇合场景比对称菱形更容易暴露“任一输入可用就运行”的错误。

K1.3.2 前驱失败或条件分支不走怎么办

**触发：**从图论转向工作流语义。

**参考回答：**图论上的“前驱处理完”不足以表达运行语义。要定义成功、失败、跳过、取消等状态，以及后继需要全部成功、部分成功还是特定控制边触发。先确定产品契约，再决定传播与调度。不能无条件把失败当成完成然后执行所有后继，也不能让确定不会触发的分支永远占着待完成计数。

K2 有界并发映射

**题目：**实现 ParallelMap(ctx, inputs, workers, fn)，同时执行 fn 的数量不超过 workers，成功结果与输入位置对应。任一任务失败时发出取消信号，等待所有 Worker 退出，丢弃部分结果并返回错误。外部取消同样需要清理。无效 Worker 数量报错，空输入正常返回。

**先说明两个前提：**fn 必须配合 context 才能及时退出；fn 自己访问的共享对象由它负责同步。这道题没有要求从任意 panic 恢复，也没有能力撤销已经发生的网络副作用。

**参考解法：**固定数量 Worker 从 jobs 取输入下标。结果切片一次性分配，每个下标只由一个 Worker 写入。sync.Once 记录首先观测到的错误并取消派生 context；生产者同时监听取消，停止继续派发；生产者关闭 jobs，WaitGroup 等全部 Worker 退出后读取错误与结果。

这里的“第一个错误”是同步竞争中首先被记录的错误，不是最小输入序号，也不是一个可由并发调度稳定定义的全局最早时刻。

**空间与并发：**工作 goroutine 数 O(min(workers,n))，jobs 不额外排队；结果空间 O(n)。当每项成本不同时，不能用总任务数直接推出运行时间等于串行时间除以 workers，下游限制和慢任务仍影响尾延迟。

K2.1 多个 goroutine 写一个 slice 为什么这里没加锁

**触发：**面试官核验数据竞争。

**参考回答：**切片长度和底层数组固定，每个输入下标只派发一次，各 Worker 写不同元素；主 goroutine 在 Wait 返回之后才读取结果。没有并发 append 或修改同一元素，所以这里不需要全局结果锁。这个结论不意味着任意并发写切片都安全。

K2.1.1 换成 append 或 fn 返回共享指针还安全吗

**触发：**面试官改变数据结构。

**参考回答：**并发 append 会修改共享切片描述符和可能相同的底层位置，需要同步或由单个收集者执行。结果是共享指针时，不同索引也可能指向同一个对象；后续修改该对象仍可能竞争。本实现保证存放结果的位置独占，不提供任意对象图的深拷贝和线程安全。

K2.2 谁关闭 jobs 谁等 Worker

**触发：**面试官询问资源所有权。

**参考回答：**唯一生产者停止派发后关闭 jobs；Worker 只接收，不关闭。每个 Worker defer Done，主流程等待全部完成。失败发生时 Worker 用 cancel 通知生产者，而不是关闭生产者仍可能发送的 channel。WaitGroup 的 Add 在启动 goroutine 之前完成，避免过早 Wait 或计数使用错误。

K2.2.1 如果 fn 不理 context 永远阻塞函数能按时返回吗

**触发：**候选人声称“无 goroutine 泄漏”。

**参考回答：**不能。本实现选择等待所有 Worker 清理，因此不合作的 fn 会阻塞返回。另起 goroutine 超时返回也不能杀死原任务，只是把泄漏藏起来。实际网络调用应设置可取消的超时；需要强制停止的任务放到可管理的独立进程。这个限制必须写在契约里，不能靠多一层 select 宣称解决。

K2.3 多个任务同时失败 firstErr 会不会数据竞争

**触发：**面试官看到共享错误变量。

**参考回答：**只有赢得 sync.Once 的调用写入 firstErr，其他 Worker 不写；主流程在 WaitGroup 完成后读取，所以同步关系成立。错误用 %w 包装保留分类。若要返回全部错误，应另设计受锁保护的集合或单个收集者，不能在多个 goroutine 中直接 append 同一个切片。

K2.3.1 cancel 之后能保证绝不再调用一次 fn 吗

**触发：**面试官要求精确取消语义。

**参考回答：**不能承诺时间上的瞬时停止。select 的多个分支可能同时就绪，即使调用前检查 ctx.Err，取消也可能恰好发生在检查之后。本答案的保证是观察到取消后停止继续工作，并等待在途调用合作退出。要控制外部动作是否允许开始，需要额外的授权/状态协议，而且仍要处理动作已提交但响应丢失。

K2.4 输入有一千万个任务还适合返回一个大 slice 吗

**触发：**面试官从正确性转向资源边界。

**参考回答：**并发数有界，但输入与结果总量仍占 O(n) 内存。大规模数据可以改成流式输入和结果消费，让调用方持久化或分批处理，并明确背压、取消和部分结果语义。这是 API 契约变化，不能只把 channel 缓冲改大。

K2.4.1 如果还要求严格输入顺序输出内存怎么控制

**触发：**面试官保留保序要求。

**参考回答：**维护有界的派发窗口，完成结果以序号暂存，只连续输出下一个期望位置。窗口最早任务过慢时暂停继续派发，让背压限制乱序缓冲。无限派发再等最慢前项，会让“保序”重新变成无界内存问题；也可以与需求方讨论是否允许分区有序或返回独立结果。

5 本次验证结果

2026-09-07，在本机 Go 1.27.0 windows/amd64 下执行：

Set-Location 'E:\Proj\interview-prep-guojiahao-2026-09-07\practice'
go test -race ./...
go vet ./...

两项通过。测试覆盖无环依赖保持、不等深汇合、重复边、环与非法节点，以及工作池并发上限、结果位置、失败取消、等待 Worker 退出和预取消输入。并发测试用同步屏障组织关键时序，没有用固定 sleep 猜测时序。

测试证明这些具体参考实现的已执行行为，不是对所有输入和调度的形式化证明，也没有替三个后端项目完成运行验收。项目代码本次仍以源码与现有测试审阅为准。