题目重点:以状态与事件分离处理 Welcome、到期前提醒、Expired、Updated 和 Renewed,明确同时间排序及重排边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版时间为整数日,订阅区间 [start, expiry),expiry=start+duration;schedule 中负数相对 expiry,其它键的语义按题面确定。
- 变更在时间 t 生效:t 之前已发邮件不可撤销,t 之后未发的通知根据新状态重算;同时间先处理变更再生成当日普通提醒,Updated/Renewed 插入的前后顺序另设 tie-break。
- 续期 extension_days 增加现有 expiry;若面试题是从 change_time 重新起算,公式必须改,不假定两者等价。
解题路线
- 先将每个账号的初始 start/expiry/plan 与 schedule 转为候选邮件,输出按 (day, account 原始序, schedule 序) 排序。不要依赖 map 迭代顺序作跨语言保证。
- 加入 plan change 时,把账号状态看作按时间排列的版本;生成时间 t 的邮件时读取 t 时刻有效版本。Updated 事件当天额外输出,过去邮件保持原计划。
- 续期改变 expiry,因此旧 expiry 关联的未来提醒全部失效并由新 expiry 派生;实现可按账号重算版本间时间段,或给候选事件带 generation 并在弹出时校验版本。
- 多个变更同日、提醒正好与变更同日、提醒时间早于 start、extension=0、到期之后才续期都需先确认业务口径;生产系统还要有每个逻辑事件的稳定幂等键防止重试重发。
手动走一遍
训练例:Ada 在第 0 天开始 20 天 Silver 计划,提醒设 expiry−15 与 expiry。初始在第 5 天发 Upcoming,第 20 天发 Expired。第 10 天升级 Gold,过去第 5 天的邮件仍写 Silver,第 20 天写 Gold;第 12 天续 10 天后,旧第 20 天 Expired 被撤销,新到期日第 30 天,并可在第 15 天产生新的 Upcoming。题目未明确这组数值,它用于验证重排规则。
规模与取舍
U 个用户、E 个变更、S 个 schedule offset:按用户排序变更 O(E log E),逐状态段生成至多 O((U+E)S) 个候选邮件,统一排序 O(M log M),M 为生成数量。大量实时更新宜存逻辑事件键与失效版本,避免全量重发。
易错点与追问
容易失分的边界
- 只改计划文本,续期后仍发旧到期提醒。
- 把未来所有邮件都改写后顺带篡改过去邮件。
- 把 -15 写死为唯一提前通知,漏掉多个 schedule 键。
- 未定义相同时刻更新与发送顺序,导致不同实现偶然通过不同测试。
继续深挖
- 同一账号在一天里升级两次并续期一次,输出顺序怎样稳定?
- 用户跨时区和夏令时变化时如何从当地日期映射 UTC 发送时刻?
- 实际邮件服务重试、崩溃恢复时怎样避免重复发或丢发?
