基础算法

当前节奏：不设单题完成期限，同一道题可以跨多次推演。实现用于验证完整思路，不通过即时反馈逐个猜测和修补 case；单次结果不外推为长期能力判断。

当前验收：先检查题意、返回值和关键搜索状态是否一致；命名、注释、goto、代码长度、性能和测试框架暂不处理。单题正确性站住后可以进入下一题，结构优化与自动测试统一在五题完成后回看。

第五题：LRU Cache

用 Go 实现一个固定容量的 LRU Cache：

type LRUCache struct {
    // 字段自行设计
}

func NewLRUCache(capacity int) (*LRUCache, error)
func (c *LRUCache) Get(key int) (int, bool)
func (c *LRUCache) Put(key int, value int)

• capacity <= 0 时，构造函数返回错误。
• Get 命中时返回值和 true，并把该 key 记为最近使用；未命中时返回零值和 false，已有顺序不变。
• Put 已有 key 时更新 value，并把该 key 记为最近使用，缓存大小不变。
• Put 新 key 且容量已满时，先淘汰最久未使用的 key，再写入新值。
• Get 和 Put 的平均时间复杂度均为 O(1)。

范围：单线程、纯内存；可以使用 Go 标准库，不使用第三方库。不扩 TTL、持久化、并发、分片和容量动态调整。

基本用例：

cache, _ := NewLRUCache(2)

cache.Put(1, 10)
cache.Put(2, 20)
cache.Get(1)       // 10, true；1 成为最近使用
cache.Put(3, 30)  // 淘汰 2
cache.Get(2)       // 0, false

cache.Put(1, 11)  // 更新已有 key，1 成为最近使用
cache.Put(4, 40)  // 淘汰 3
cache.Get(1)       // 11, true
cache.Get(3)       // 0, false
cache.Get(4)       // 40, true

还需自行覆盖：容量为 1、重复更新同一 key、读取不存在的 key，以及构造容量为 0 或负数。

验收边界：解释每一步之后谁是最近使用、谁是最久未使用；跑通上述用例和四类边界；说明复杂度。先保证正确性，不扩展功能。

2026-07-22 练习记录：已用 map[int]*Node 与手写双向链表完成固定容量 LRU；链表头表示最久未使用，链表尾表示最近使用，命中、更新与淘汰路径均保持平均 O(1)。第一版运行题面主样例符合预期。

review 修正：第一版没有拒绝非正容量，删除唯一节点时也会解引用空的头尾指针。随后补上构造参数校验，并让删除操作覆盖唯一节点、头、尾和中间节点；容量为 1 的命中路径实际运行得到 10, true，go vet 与 gofmt 检查通过。

当前边界：修正后没有重新执行完整主样例，也没有继续运行重复更新、未命中不改变顺序、容量 0 与负数等其余边界。静态检查未发现新的正确性问题，但这些 case 不记为已经通过；本题按当前决定停止追加验证，阶段结束。

学习材料：链表：从指针到索引，从本题的唯一节点边界展开到环形链表和跳表。

第四题：Token Bucket

用 Go 实现一个由调用方传入逻辑时间的单机令牌桶：

type TokenBucket struct {
    // 字段自行设计
}

func NewTokenBucket(
    capacity int,
    refillPerTick int,
    startTick int64,
) (*TokenBucket, error)

func (b *TokenBucket) Allow(nowTick int64, n int) bool

本题中的 tick 只是单调递增的整数时间单位。不要调用 time.Now()，也不要用 sleep 驱动测试。

• capacity 是桶最多容纳的令牌数，必须大于 0。
• refillPerTick 是每经过一个 tick 补充的令牌数，必须大于 0。
• 新桶在 startTick 时是满的。
• 每次 Allow 先根据距上次更新时间经过的 tick 补充令牌，但不能超过容量；再判断能否消费 n 个令牌。
• 令牌足够时扣除并返回 true；不足时不扣除并返回 false。
• n <= 0 返回 false，状态不变。
• nowTick 小于上次更新时间时返回 false，状态不变。
• 假设传入数值足够小，不考虑整数溢出；不要求并发安全。

纸上样例：

b, _ := NewTokenBucket(5, 2, 100)

b.Allow(100, 3) // true，剩余 2
b.Allow(100, 3) // false，仍为 2
b.Allow(101, 3) // true，先补到 4，再消费，剩余 1
b.Allow(103, 5) // true，先补到容量上限 5，再消费，剩余 0
b.Allow(103, 1) // false，仍为 0
b.Allow(102, 1) // false，时间倒退，状态不变
b.Allow(104, 0) // false，无效请求，状态不变

需要自行补出的最小用例：构造参数非法；空桶后逐步恢复；长时间后只补到容量上限；一次请求恰好耗尽；请求量大于容量。

验收边界：能逐次写出 tokens 和上次更新时间的变化，并说明 capacity 为什么允许突发、refill rate 为什么限制长期速率。

停止条件：独立推演并跑通上述边界后停止。不扩真实时钟、浮点速率、并发锁、分布式限流、持久化或动态配置；不设完成期限。

2026-07-22 练习记录：约 30 分钟写出第一版，题面样例运行符合预期，但因为急于先交付，遗漏构造参数校验，并把“补充令牌”写回对象、却只在消费成功时更新时间，形成令牌与时间检查点的部分提交；失败后再次调用可能重复计算同一段时间。review 后补上参数校验，并改为先在局部变量计算候选状态，只有消费成功时才同时提交令牌和时间。

• 核心理解：失败请求不能扣除请求的令牌；时间经过带来的补充不是污染。立即保存补充状态，或者像当前实现一样在失败时令牌与时间都不提交、下次统一结算，都是自洽模型；不能只提交其中一个。
• 当前实现：采用延迟结算。在调用方传入的 nowTick 单调不减、固定速率、单线程且内部字段不对外暴露时，它与每次调用立即结算在后续 Allow 结果上等价。
• 验证边界：构造校验和题面样例已进入代码；“空桶后在 tick 2 / 3 / 4 请求”的失败路径经过 review 推演，尚未固化成自动测试。没有关闭参考后空白重写。
• 停止决定：核心正确性到此接受，进入下一阶段；命名、table-driven test、立即 / 延迟结算取舍及并发扩展留到五题完成后统一回看。

第三题：Producer / Consumer

用 Go 实现：

func processJobs(
    jobs []int,
    workers int,
    queueSize int,
    handle func(int) int,
) ([]int, error)

一个生产者提交任务，多个消费者并发调用 handle。本题只处理内存中的有限任务，不涉及网络、持久化或分布式队列。

• workers 表示最多同时工作的消费者数量，必须大于 0。
• queueSize 表示有界任务队列容量；允许为 0，表示不带缓冲；小于 0 时返回错误。
• handle 不得为 nil，并假设它可以被并发调用且不会 panic。
• 每个输入位置都必须被处理且只处理一次；值相同的任务仍是不同任务。
• 消费者可以按任意顺序完成，但返回结果必须与 jobs 的输入位置一一对应。
• 函数必须等全部任务处理完成后再返回，不能死锁，也不能在返回后留下仍在工作的 goroutine。
• 空任务返回空切片和 nil error。

样例：

square := func(v int) int { return v * v }

processJobs([]int{3, 1, 2}, 2, 1, square)
// []int{9, 1, 4}, nil

processJobs([]int{2, 2, 3}, 3, 0, square)
// []int{4, 4, 9}, nil

processJobs([]int{}, 2, 1, square)
// []int{}, nil

processJobs([]int{1}, 0, 1, square)
// nil, error

processJobs([]int{1}, 1, -1, square)
// nil, error

验收边界：先证明任务没有丢失、重复或错位，并能解释生产者、消费者、队列和关闭责任分别属于谁。不要求取消、超时、重试、错误聚合、优先级或动态扩缩容。

停止条件：本轮先以核心时间线跑通并能解释每个关闭与等待关系为界。关闭参考后的空白重建、自动测试和结构优化统一留到五题完成后回看。

2026-07-21 练习记录：开始实现 guard/cmd/jobs/main.go。第一版把 workers 个 goroutine 各执行一次接收，日志只出现两次；由此确认自己把旧代码中 workerpool.Submit / StopWait 提供的队列、持续消费和等待语义，误认为是 WaitGroup 自带的能力。查看了旧实现，但没有复制代码。

• 已经建立：channel 承载任务；queueSize > 0 时是有界缓冲队列，等于 0 时是同步交接。worker 需要持续消费直到输入关闭；WaitGroup 只记录执行单元是否结束，不负责排队、调度或关闭 channel。
• 结果归位：Job.ID 是原输入位置。经语义提示后约两分钟独立想到按 ID 直接寻址，不需要把乱序结果再做 O(n log n) 排序；全部结果本身需要的 O(n) 空间不可避免。
• 第一次生命周期错误：曾让一个 goroutine 先发送全部 in，再收集 out；任务足够多时，producer 可能等待 in、workers 等待 out，而 collector 尚未开始，形成循环等待。
• 第二次生命周期错误：把 collector 独立成 goroutine 后，主流程等待 workers、关闭 out 并立即返回。实际运行曾先得到 [9 1 0]，最后一个结果随后才被 collector 写入，说明 close(out) 是结束信号，不是等待接收方完成。
• 当前实现：input producer 发送全部任务并关闭 in；workers 持续处理；output closer 在独立 goroutine 中等待全部 workers 后关闭 out；collector 留在当前 goroutine 持续归位，只有 range out 结束后函数才返回。三个启用样例已经得到完整结果。
• 刚建立的理解：in 只有一个发送者，由 producer 判断并关闭；out 有多个发送者，需要协调者确认全部结束后关闭；collector 决定结果何时完整，因此属于函数的同步返回边界。这里的不对称来自所有权，不是代码形式不整齐。
• 经验边界：过去写的程序很少系统考虑优雅退出，没有持续追问谁停止接收、谁关闭入口、谁排空剩余结果、谁确认后台执行单元已经退出。本题第一次把这些关系作为可推演的协议看见；当前是刚理解，不记为熟练掌握。

提示边界：在请求展开上述两个问题后，已经直接获得下面的架构级关系；这部分不再记为独立推演。

input producer：发送全部任务，然后关闭 in
workers：持续读取 in，处理后发送 out，结束时 Done
output closer：等待所有 workers，再关闭 out
collector：持续读取 out，按 ID 归位；range 结束后才允许函数返回

当前边界：channel close 只表示以后不会再发送，不表示 receiver 已经处理完成；有界队列满时发送方会阻塞，输入生产和输出消费如果被串成两个阶段，可能形成循环等待。核心时间线已经在提示后跑通，本轮进入下一题；空白重建与结构复核留到五题完成后。

第二题：BFS 最短路径

用 Go 实现：

func shortestPath(
    graph map[string][]string,
    start string,
    target string,
) ([]string, bool)

graph 是有向、无权图，邻接节点的顺序有意义。

• 返回从 start 到 target 的最短路径，包含首尾节点。
• 多条最短路径同时存在时，按邻接表给出的顺序选择。
• start == target 时返回 []string{start}, true。
• 不存在路径时返回 nil, false。
• 图可能有环和重复边，不能无限循环。
• 假设所有邻接节点都作为 key 存在于 graph 中。

当前题意解释：按普通图语义处理：同一来源到同一目标的重复邻接记录不增加新的可达关系；不同来源到同一节点属于合法合流，不能全局去重。

graph := map[string][]string{
    "A": {"B", "C"},
    "B": {"D"},
    "C": {"D"},
    "D": {},
}

shortestPath(graph, "A", "D") => [A B D], true
shortestPath(graph, "A", "A") => [A], true
shortestPath(graph, "D", "A") => nil, false

当前只保留的 Stack / Queue 语法：

// Stack
stack = append(stack, v)
v = stack[len(stack)-1]
stack = stack[:len(stack)-1]

// Queue
queue = append(queue, v)
v = queue[head]
head++

这些代码只表示两种容器的最小进出操作，不是本题解法。

已通过反例 1：分支中的最短路径

graph := map[string][]string{
    "A": {"B", "C"},
    "B": {"X"},
    "C": {"D"},
    "X": {"D"},
    "D": {},
}

start = "A"
target = "D"
当前结果：A -> C -> D
最短路径：A -> C -> D

已通过自造用例：先经过死路，再找到有效路径

graph := map[string][]string{
    "A":  {"B0", "B", "B1"},
    "B0": {"X"},
    "B":  {"C"},
    "C":  {"D"},
    "D":  {"E"},
    "E":  {},
    "B1": {"Y"},
    "X":  {},
    "Y":  {},
}

start = "A"
target = "E"
当前结果：A -> B -> C -> D -> E, true

已通过单一反例：重复边不产生新的搜索状态

graph := map[string][]string{
    "A": {"B", "B"},
    "B": {"C"},
    "C": {"D"},
    "D": {"E"},
    "E": {},
}

start = "A"
target = "E"
期望结果：A -> B -> C -> D -> E, true
当前结果：A -> B -> C -> D -> E, true
当前行为：第二条 A -> B 由已发现状态跳过，不再手动 strip 邻接表。

已通过反例：合流导致重复抵达

graph := map[string][]string{
    "A": {"B", "C"},
    "B": {"D"},
    "C": {"D", "X"},
    "D": {},
    "X": {"E"},
    "E": {},
}

start = "A"
target = "E"
期望结果：A -> C -> X -> E, true
此前错误队列形态：D, D, X
当前队列形态：D, X
当前结果：A -> C -> X -> E, true
当前行为：D 首次被发现时进入 Queue 并记录前驱；C 再次抵达 D 时跳过，X 仍按原顺序进入 Queue。

补课入口：图：从结构到搜索。先补图与树、重复边与合流、入度与出度、节点生命周期和控制动作作用域。

当前边界：已经明确重复记录应由搜索状态处理，但当前实现仍用前驱表和展开表共同判断，尚未把“已发现”和“已展开”统一成稳定不变量。

已通过反例 2：图中存在环

graph := map[string][]string{
    "A": {"B"},
    "B": {"A"},
    "D": {},
}

start = "A"
target = "D"
当前行为：能够结束并返回 nil, false；2026-07-20 版本也已避免 A 经 B 回到 A 时再次入队。

已完成纸上复核：起点自环不再重复入队

graph := map[string][]string{
    "A": {"A", "B"},
    "B": {},
    "D": {},
}

start = "A"
target = "D"
黑盒预期：nil, false
白盒预期：
  入队：A, B
  展开：A, B
当前纸上推演：
  入队：A, B
  展开：A, B
当前行为：展开 A 时直接忽略 A -> A；返回 nil, false。
验证边界：专项分支已经加入当前实现，但该 case 尚未固化成自动测试。

结构停车点：当前实现用前驱表、展开表和自环特判共同维持搜索状态，正确性已经覆盖现有黑盒样例与自环纸上推演；“节点入队时即标记为已发现”的统一不变量、状态精简和代码结构调整留到五题完成后处理。

2026-07-13 记录：首次独立思考 30 分钟后未完成；第二版写出了基于 Stack 的遍历，简单样例通过，但它是 DFS。

2026-07-14 记录：第三版接入了 Queue 的最小语法，并通过递归拼出连续路径；实际搜索仍由递归 DFS 推动，最短路径和有环反例尚未通过。当前继续独立完成，不查解法；需要时用纸笔推演，到达单次时间上限后停止。检查点、反例和验证结果用于校准过程，不记录修改方案。

2026-07-14 第二次记录：第四版移除递归，由 Queue 推进访问并加入访问记录；当前 6 个样例通过 5 个，起终点相同、不可达、简单环和单链路径已通过。分支反例仍返回 A -> B -> C -> D，不满足最短路径 A -> C -> D。30 分钟到点后停止，没有查看完整答案。

方法复盘：在没有先定义各份状态含义的情况下进入实现，后续转为逐个修补 case，偏离了先推导状态语义的顺序。当前继续先解释同一节点重复到达时各份状态仍表示什么，再决定是否写代码。

2026-07-15 调整：停止即时训练，不再要求一开始就写代码或在限定时间内完成。当前目标只保留一个：最终独立推演出完整思路，再用一次实现验证；完成时间随学习过程决定。

2026-07-16 记录：第五版已由 Queue 推进访问，分别记录访问状态和路径来源，并能从终点反向还原路径；原分支反例与自造分支图已通过。当前正确性缺口收敛到重复边和重复到达时的状态处理，尚未查看标准答案。

2026-07-16 第二次记录：已区分同一来源的重复边与不同来源的合法合流；前者通过稳定去重的单一反例，后者暴露出此前一直用树的心智模型理解图。曾加入队尾条件让两个样例通过，但无法从不变量解释，未接受为答案。当前停止硬改，先补最小图模型；已建立交互式教程，仍未查看标准实现。

2026-07-20 记录：当前 9 组样例输出均符合预期，分支、死路、重复边、合流和简单环已经进入同一版实现；不再通过 strip 修改邻接输入，开始用搜索状态处理重复抵达。新增展开状态后，A -> B -> A 不再重复入队；自环仍暴露状态写入时机的缺口。继续先收敛正确性和状态解释，再处理结构简化，尚未查看标准实现。

2026-07-20 第二次记录：已为起点自环增加专项处理，纸上白盒推演恢复为 入队 A, B；展开 A, B。BFS 的正确性阶段到此结束，进入下一题；当前实现不冒充最终标准结构。五题完成后，以 table-driven test 固化分支、不可达、重复边、合流、普通环和自环，再统一“已发现 / 已展开”状态并回收结构债。