SDE / AS / Intern · Coding

Amazon AS Coding:按 User 与 Action 统计总次数

用二层频表聚合完整记录,澄清date不参与总量键以及缺字段和重复事件。

题目重点:用二层频表聚合完整记录,澄清date不参与总量键以及缺字段和重复事件。

题意与假设

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

  • 每条记录恰3字段,user/action非None且可hash;date保留输入但不参与总计。
  • 同内容重复行照计,题目无event_id,不能推定重传去重;空输入为空dict。

解题路线

  1. 外层key user,内层key action,逐行+1;日期不用作key,因为目标是全时期总次数。若改每日统计,才增加date维。
  2. 不变量:处理前缀后counter[u][a]等于此前满足user/action的行数;每行只触及一格,归纳得到精确聚合。
  3. 类型/字段不合法应拒绝或另列invalid,训练拒绝,不能静默跳过又把结果当完整。用户缺值不与字符串“None”混成一组。
  4. 重复是业务次数还是同事件重传需额外身份字段;不能只凭user/date/action三元组去重,真实两次点击可完全相同。
  5. 流式内存按不同(user,action)对数增长,可按user分片后精确合并;输出缺省0桶或排序顺序由消费接口定义,不需要臆造有限action全集。

手动走一遍

训练[(u1,d1,view),(u1,d2,view),(u1,d2,buy),(u2,d2,view)]得u1:{view:2,buy:1},u2:{view:1}。重复第一行后u1.view应3。

Python 参考实现

下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。

代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。

def count_actions(records):
    """(user,date,action), every row counts; date not used for total grouping."""
    result={}
    for user,date,action in records:
        if user is None or action is None:raise ValueError("missing user or action")
        counts=result.setdefault(user,{})
        counts[action]=counts.get(action,0)+1
    return result

复杂度

O(n)期望时间、O(p)聚合空间,p不同user-action组合;输出O(p)。复杂日期解析不影响总量,但若筛日期范围需先核时区。

易错点与追问

容易失分的边界

  • 把date加入key导致返回日计数。
  • 相同三元组强行去重。
  • 不同用户共享同一个可变内层dict。

继续深挖

  • 加日期过滤怎样定义时区?
  • 只返回每用户TopK action?
  • 按event_id去重需要多少保留状态?
✓已复制微信号!