Bloomberg Fraud Transactions：金额门槛与 60 分钟跨地点窗口

题意与假设

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

• 训练版以 name 当账户键且所有时间在同一天；若同名有不同账户，必须改用真正 accountId。
• 时间差 ≤60 分钟算‘在 60 分钟内’，相关两笔均标记； 没有定义边界与输出形式，训练版返回原输入下标升序。
• 默认金额门槛 2000 对应；LC1169 变体把门槛改为 1000 且输入保证时间有序，不能把两个版本的门槛混用。

解题路线

1. 先给基线：逐对检查同账户、不同地点与绝对时间差，并单独标记 amount>threshold，O(n²) 适合核规则。
2. 优化时按账户分组并按分钟排序；若输入已按时间有序，如 所述变体，可省排序。对每个交易，前向维护过去 60 分钟地点频数；若窗口总数大于同地点数量，当前交易有跨地点前驱。
3. 再从后往前做对称窗口，找未来 60 分钟内跨地点的交易；两次扫描并集会把一对冲突交易的前后两端都标记。
4. 索引随事件保存，最终按输入顺序返回；相同分钟的不同地点也满足时间窗口。若时间戳跨日需日期/时区，不能直接比较 LocalTime。

手动走一遍

同账户 A：09:00/$2000/NY、10:00/$20/SF、10:01/$2001/SF。前两笔恰好 60 分钟且地点不同，训练版均标记；第三笔又因金额 >2000 标记。若第一笔改成 $2001 也只返回一次。

Python 参考实现

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

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

from collections import Counter, defaultdict, deque


def find_fraud(transactions, threshold=2000, presorted=False):
    """Return input indices flagged by the public interview rules.

    Each transaction has name, amount, location and time (minutes of one day).
    Two different locations within 60 minutes flag both transactions.
    """
    flagged = {i for i, tx in enumerate(transactions) if tx["amount"] > threshold}
    by_name = defaultdict(list)
    for i, tx in enumerate(transactions):
        by_name[tx["name"]].append((tx["time"], i, tx["location"]))

    for events in by_name.values():
        if not presorted:
            events.sort()
        for order in (events, list(reversed(events))):
            window = deque()
            locations = Counter()
            for time, index, location in order:
                while window and abs(time - window[0][0]) > 60:
                    _, old_location = window.popleft()
                    locations[old_location] -= 1
                    if locations[old_location] == 0:
                        del locations[old_location]
                if len(window) > locations.get(location, 0):
                    flagged.add(index)
                window.append((time, location))
                locations[location] += 1
    return sorted(flagged)

复杂度

一般输入按账户排序总 O(n log n)，两向扫描 O(n) 期望；若如 已按时间排序，分组后保留顺序可达 O(n) 期望。窗口地点表与输出 O(n) 空间；暴力基线 O(n²) 时间。

易错点与追问

容易失分的边界

• 把 amount=2000 判作高额欺诈。
• 只标记后发生的一笔。
• 仅按姓名分组却忘了同名不同账户歧义。
• 把 LocalTime 直接用于跨日比较。
• 窗口移除旧交易后未同步更新地点频次。

继续深挖

• 时间刚好 60 分钟算不算？
• 跨午夜怎么做？
• 若流式实时到达且乱序怎么办？
• 账号跨城市高频旅行如何降低误报？