题目重点:Onsite 事件流样例的 abc=2200 是两个用户停留秒数相加;实时 Top K 追问看当前人数,不能沿用总时长排序。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版 create(space,user,t) 同时让创建者加入 space;join 只在 (space,user) 不活跃时成功,leave 必须匹配活跃 join/create。
- 输入按 timestamp 非递减到达;同时间戳事件按输入顺序。持续活跃到流末尾的会话不计入闭合总时长,实时人数仍包含它;若需截止时刻结算,必须给 queryTime。
- 总时长单位秒,允许同一用户离开后重新进入并累加;跨 space 的同一用户分别计时。无效重复 join/leave 的处理为训练约定,应向面试官确认。
解题路线
- 维护 active[(space,user)]=joinedAt、totals[space]、currentUsers[space]。create/join 把新活跃 pair 写入并把当前人数加 1;leave 找到 pair 后加 timestamp−joinedAt 到 totals,删活跃 pair、人数减 1。
- 打印总时长时输出闭合会话的 totals,而不是取 space 首次 create 到最后 leave 的墙钟跨度;源例 abc 从 7000 到 9000 墙钟只有 2000 秒,输出却是 2200。
- 实时 top-k 依据 currentUsers 排序,与 totals 不同。若查询少,可在每次 query 扫 S 个 space 用大小为 K 的小顶堆 O(S log K);若更新和查询都密集,用按 (count,space) 排序的索引或桶并维护并列规则。
- 大流量下按 space 分区可减少跨空间竞争,但同 space 的 join/leave 顺序必须保持;乱序事件需 watermark/重算或拒收策略,不能直接用到达顺序当事件时间。
手动走一遍
abc 在 1234567000 create(user_1),1234567100 join(user_2),1234567300 leave(user_2),1234569000 leave(user_1):总用户秒数 (7300−7100)+(9000−7000)=200+2000=2200;def 从 8000 到 8500 为 500。abc 在 7100–7300 实时人数为 2,7300 后为 1,但累计时长仍在增长。
规模与取舍
E 条有序事件平均 O(E) 处理时间,活跃 pair 与累计 space 状态 O(A+S) 空间。扫描式 Top K 查询 O(S log K) 时间、O(K) 临时空间;有序索引可把人数变化做到 O(log S),查询前 K 约 O(K)。
易错点与追问
容易失分的边界
- 把 abc 输出 2200 解释成墙钟有人的区间,实际上该区间只有 2000 秒。
- 用总参与秒数给 top-k,而追问明确是最大用户数。
- create 不让创建者进入,会少算 user_1 的 2000 秒。
- 重复 leave 找不到活跃会话时默默减人数到负数。
- 乱序事件未处理就以负时长累加。
继续深挖
- top-k 是当前并发人数还是历史去重人数?
- 如何处理迟到 join/leave 和重放重复事件?
- 若 queryTime 到来时仍有人在线,已累计时长怎样定义?
- 如果只想要 Space 有人在线的墙钟时长,和本题用户秒数有什么不同?
