FizzBuzz撮合市场：FIFO部分成交与参与者对聚合

题意与假设

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

• Fizz/Buzz一对一单位兑换，数量为非负整数，按输入次序处理，名字作为参与者身份。
• 同一(FizzName,BuzzName)聚合，代码返回tuple-key map；格式字符串/结果排序在输出层按明确合同生成。

解题路线

1. 新Fizz消费Buzz队头，反向同理，每次amount=min两余额。某旧offer耗尽弹队头，新offer剩余才入己方队尾。
2. 每次撮合累加有向身份对(Fizz参与者,Buzz参与者)，不依新offer类型颠倒键。用tuple避免名字含冒号导致字符串键碰撞。
3. 队列FIFO是合同本身，不按数量排序。输出聚合掩盖逐笔次序，若需要审计必须另保留成交事件。输入对象不原地修改，便于重放/测试。

手动走一遍

Alice Fizz5；Bob Buzz3成交3；Catherine Buzz4再成交2余2；Alice Fizz4与其成交2余2；Bob Buzz2成交2。聚合Alice:Bob5，Alice:Catherine4。数量0offer不入队不产生记录；同名多offer聚合为同参与者对。

Python 参考实现

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

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

from collections import deque


def match_offers(offers):
    fizz,buzz=deque(),deque();matched={}
    for kind,name,quantity in offers:
        if kind not in ('Fizz','Buzz') or type(quantity) is not int or quantity<0:raise ValueError("invalid offer")
        own,opposite=(fizz,buzz) if kind=='Fizz' else (buzz,fizz)
        while quantity and opposite:
            other,remaining=opposite[0];amount=min(quantity,remaining)
            key=(name,other) if kind=='Fizz' else (other,name)
            matched[key]=matched.get(key,0)+amount
            quantity-=amount;opposite[0]=(other,remaining-amount)
            if remaining==amount:opposite.popleft()
        if quantity:own.append((name,quantity))
    return matched

复杂度

n offer，每次撮合至少耗尽一侧，最多O(n)撮合步骤与期望聚合更新时间；状态O(n+p)，p实际不同匹配对≤撮合数。

易错点与追问

容易失分的边界

• 输出名称顺序依新offer类型变化会把同对拆成两键。
• 题目priority是FIFO，不是构造按quantity的优先队列。

继续深挖

• 支持取消未成交offer时需要哪些ID索引与lazy标记？
• 分布式分片能否独立撮合，哪些键需要同一串行顺序？