面试真题与回答讲解 第 50 页，共 52 页
浏览 OfferCC 面试真题与回答讲解第 50 页，查看解题思路、实现细节、追问和公开来源。
算法面试：如何从未知长度的数据流中均匀抽样？
用 Reservoir Sampling 在单次扫描和 O(k) 内存限制下维护 k 个等概率样本，推导不变量、证明正确性并处理边界。
如何设计分布式唯一 ID 生成器？
从容量约束推导 Snowflake 位布局，处理时钟回拨、worker 身份、序列溢出和多地域故障，并比较 UUIDv7 与号段方案。
类别极度不平衡时，如何选择模型指标与分类阈值？
从混淆矩阵、审核容量和误判成本推导分类指标与决策阈值，并解释 AUROC、PR 曲线、概率校准及基准率变化各自解决什么问题。
算法面试：如何选择不重叠任务以获得最大收益？
用加权区间排程把排序、二分查找与动态规划串起来，讲清楚边界定义、正确性证明、复杂度和可恢复方案。
如何设计分布式任务调度器，避免漏跑与重复执行？
从执行实例标识、分片时间索引和至少一次投递出发，设计支持单次与 Cron 任务的多租户调度器，并处理整点洪峰、错过触发、时区、取消竞态和故障恢复。
机器学习中的数据泄漏是什么？如何发现和避免？
以欺诈识别模型为例，建立预测时刻契约，排查目标、时间、实体与预处理泄漏，并设计可信的数据切分、交叉验证和最终留出测试。
编程面试：如何实现动态数组并证明 append 的摊销 O(1)？
从容量不变量、几何扩容和摊销证明出发，实现可索引的动态数组，并解释空间与最坏情况代价。
如何设计支持短信、邮件与推送的多渠道通知系统？
以每日 10 亿个渠道投递任务为假设，设计兼顾 OTP 与营销活动的通知系统，讲清优先级隔离、交付状态、乱序回执、重试和可验证的失败恢复。
流处理如何处理迟到与乱序事件，保证窗口聚合正确？
以每小时营收为例，从事件时间、水位线、允许迟到和去重状态推导流处理方案，并处理结果修正、状态清理、故障恢复与离线对账。
编程面试：如何返回出现频率最高的 K 个单词？
用哈希计数、定制最小堆和严格的频率/字典序比较器，在 O(n log k) 时间内返回 Top K 单词。
系统设计面试：如何实现跨地域全局限流？
用配额租约实现全局 API 上限，量化网络分区时的超放边界，并处理热点地域再平衡和明确的故障策略。
编程面试：如何实现不允许重叠的日程预订？
用半开区间、前驱后继查找和有序映射实现 My Calendar I，并说明边界、复杂度与扩展到并发服务的变化。
算法面试：如何排查双堆动态中位数实现错误？
针对只在交替极值、重复值和偶数长度下出错的 MedianFinder，用不变量、最小反例和对照测试定位并修复。
Coding 面试：如何实现一个 O(1) 查询最小值的栈？
通过辅助栈维护每个深度的最小值，在 push、pop 和 getMin 都保持 O(1)，并处理重复最小值与空栈边界。
编程面试：实现一个 Bloom Filter
实现支持 add 与 mightContain 的 Bloom Filter，解释误判、参数估算、删除限制和测试方法。
编程面试：实现一个线程安全的读写锁
练习用互斥量、条件变量和等待计数实现读写锁，并解释公平性、升级与失败场景。
编程面试：实现一个带 TTL 的缓存
用哈希表、过期时间和惰性清理实现可测试的 TTL 缓存，并讨论并发、容量与时间边界。
编程面试：如何实现支持合并与查询的区间集合？
实现一个维护不重叠区间的集合，支持插入、删除、点查询和区间查询，并说明边界、合并和复杂度。
编程面试：如何实现支持更新和删除的稳定优先队列？
用堆、索引表和惰性删除实现可更新优先级的优先队列，并处理相同优先级、删除、过期条目和复杂度证明。
编程面试：如何设计一个可恢复的分批迭代器？
从 hasNext/next 契约出发，设计一个按页读取远程数据、支持暂停恢复、避免重复和正确传播错误的迭代器。
算法面试：如何实现快照数组？
用按索引组织的变更历史、同版本写入合并和二分前驱查询实现快照数组，并证明时间、空间与快照语义。
算法面试：最少需要多少间会议室？
把会议区间转化为同时占用资源数，用双数组扫描线求最少会议室，并通过重叠深度证明最优性，覆盖半开区间、同刻事件、堆解法与房间分配追问。
编程面试：用拓扑排序解决外星词典
从已排序词表中只提取有依据的字符先后约束，再用拓扑排序还原未知字母表。掌握无效前缀、环检测、正确性证明、多解判断和对抗性测试。
算法面试：如何用迭代 DFS 计算岛屿数量？
从连通分量建模推导原地迭代 DFS，解释为何要在入栈时标记，并覆盖复杂度、正确性、边界测试与替代方案。