题目重点：Uber 两篇 Phone Screen 面经给 add、addByReferral、showRevenue 与 TopSmallestK 查询。建模客户收入和有序索引，并明确第二篇新客户收入示例的自相矛盾。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练契约：add(revenue) 创建新 customerId，初始累计收入为 revenue；addByReferral(revenue,parentId) 创建新客户收入 revenue，同时把 revenue 加到直接推荐人 parentId 的累计收入。
- 只更新直接推荐人，不沿推荐链递归传播；题目没有明确多代累计规则。第二篇写新客户收入 10 而调用参数为 30，本文不把这个不一致的值当成确定题意。
- TopSmallestK(k,threshold) 返回当前累计收入严格大于 threshold 的 k 个最小 customerId，按 (收入,ID) 排序；k=0 返回空，候选不足返回全部。
解题路线
- 保存 customerId→当前累计收入，以及按 (收入,ID) 排序的索引。add 创建 ID 并插入索引；addByReferral 先验证 parent 存在，再创建新客户、从索引移除父客户旧键并插入其新键。
- showRevenue 直接查当前收入表。TopSmallestK 从 (threshold,+∞) 之后的第一条索引记录开始取 k 个，严格大于阈值而非 ≥。
- 若语言没有有序树，可用收入表全量过滤排序作为正确性基线；读多写少时定期构建排序快照，写多读少时按需排序，具体取舍由调用比例决定。
手动走一遍
add(10)→客户1收入10；add(20)→客户2收入20；按本文训练契约 addByReferral(30,1)→客户3收入30、客户1收入40。此时 TopSmallestK(2,20) 取客户3与客户1；客户2收入正好20被严格阈值排除。题目把客户3写成10，需现场澄清。
规模与取舍
用平衡有序索引，add 与 referral 更新为 O(log N)，showRevenue 期望 O(1)，阈值查询 O(log N+k)，空间 O(N)。全量过滤排序基线的查询为 O(N log N)、更新期望 O(1)。
易错点与追问
容易失分的边界
- 旧收入键不从有序索引删除会让同一客户在 Top K 中出现两次；懒删除堆要额外校验版本与当前收入。
- 收入相等时只按 revenue 建索引会丢客户；使用 (revenue,customerId) 唯一键。
- 第一帖没有 Top K 完整接口，第二帖的 referral 示例又自相矛盾；不能凭猜测宣称某个新客户收入规则就是面试原题。
继续深挖
- 若收入可减少或退款，有序索引仍可删除旧键、插入新键；只增收入的单调性优化不能复用。
- 若并发 addByReferral，生成客户 ID、读取父收入、更新两项及有序索引需放在同一事务/锁范围，避免丢失父收入增量。
