SDE · Phone Coding

Amazon Audible:阅读事件流识别 Abusive Books,跳读证据与比例分母怎么定?

拆最后5%、先前10%与book事件比率,说明当前位置无法还原真实播放覆盖,给透明训练状态机。

题目重点:拆最后5%、先前10%与book事件比率,说明当前位置无法还原真实播放覆盖,给透明训练状态机。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 题目completed10%究竟是先前position、累计播放时间或覆盖区间没有定义;这是核心待核,当前位置不能证明真实听完比例。
  • 为可执行思路明确教学合同:检查当前事件之前的最大已观测position是否≥10%,当前position≥95%则作为near-end;不是实际收听覆盖算法。
  • 比例分母教学按全部有效read事件,>20%严格超过,不按unique user或仅completion事件;若正式合同不同需调整。无重复题目允许,但乱序/session/时长变动未给。

解题路线

  1. 先展示信息不足:同样position=100与980、duration=1000的事件,一个人可能正常连续听了中间内容,也可能直接seek到980;只看两个位置无法区分真实覆盖。不能用max position把跳转当听完。
  2. 在声明的先前位置合同下,状态maxPrior[(user,book)],先计算nearEnd及prior低于10%,累计book总事件与abusive事件,最后更新maxPrior。先更新再判会让每个near-end事件同时满足已过10%而永不abusive。
  3. 检查duration>0、0≤pos≤duration,比较可用整数比例20pos≥19duration及10prior≥duration避免浮点阈值误差。首次near-end没有先前观测,教学prior=0,但真实缺失历史可能误判,需session/初始状态合同。
  4. book标记abusive_count/total_count>0.2,整数5·abusive>total,无需TopK。若新事件改变比率可能从true变false,不能只维护首次命中过的永久黑名单。分母不同会造成完全不同稀释效应。
  5. 真实听完比例若需覆盖区间,事件应有播放起止/时间/seek/session等足够观测,再对合法播放区间取union/累计时间。重复/乱序要event ID与watermark/重放,题目允许无重复不等于允许无序无限累加。
  6. 并发同一(user,book)检查与更新、book计数要一致,单独atomic counter不足以避免先前状态race;可按book分区串行处理或事务/锁。多实例分区迁移需带状态/checkpoint和去重,不能两边都计票。

手动走一遍

教学duration1000:用户先pos50,后pos960;后事件near-end且先前50<100,abusive。若先pos100,则按“至少10%”合同不abusive。一个book总5事件其中1abusive恰20%不标,6事件中2abusive约33.3%标。真实听完合同下这组position不足以断言是否跳读,仍需证据。

规模与取舍

先前位置教学每事件期望O(1),状态O(活跃user/book对+book数);session/TTL必须定义否则历史无界。真实区间union每对O(I)空间、插入成本取决区间索引,不宣称同样常量空间。

易错点与追问

容易失分的边界

  • max position当真实听完。
  • 先更新再看previous。
  • 20%用≥而非>。
  • atomic counter保证整套状态原子。
  • 分母偷偷改成completion或unique user。
  • 旧session永久影响新阅读。

继续深挖

  • 真实播放覆盖需要补哪些事件字段?
  • duration变更/重复阅读怎样分session?
  • 全事件分母怎样被高频用户稀释?
  • 分布式分区如何保持状态和计数一致?
✓已复制微信号!