面试题：后端

后端工程师岗位相关的接口设计、服务端基础、并发、存储和稳定性面试准备。

如何反转单链表，并说明时间复杂度和边界节点处理？

反转单链表时维护前驱、当前和后继三个引用，逐个改变 next 指针；空链表和单节点链表应直接返回。

用一个虚拟头节点逐步选择两个链表中较小的节点，某一条链表耗尽后把另一条的剩余部分直接接上。

HashMap 用于按 key O(1) 找节点，双向链表维护最近使用顺序；访问或写入时把节点移动到头部，淘汰尾部节点。

数据能放入内存时可排序或用最小堆；数据流或数据量很大时维护大小为 K 的最小堆，必要时做分片统计再合并。

在有序数组中维护左闭右开区间，遇到大于等于目标值时收缩右边界，否则收缩左边界，循环结束的 left 即答案。

右指针扩展窗口，窗口违反约束时移动左指针恢复合法性；每个元素最多进出窗口一次，通常是 O(n)。

用队列保存待处理节点，每轮记录当前队列长度作为一层边界，依次取出节点并加入左右子节点。

简单计数器可用原子加法保证递增不可分割；涉及多个字段或需要复合不变式时仍需锁、事务或消息串行化。

队列需要容量、入队等待、出队等待和关闭状态；关闭后禁止新生产，消费者按策略处理剩余任务并最终退出。

令牌按固定速率补充并限制桶容量，请求消耗令牌；桶容量决定允许的最大突发，补充速率决定长期平均速率。