Meta 定时转账与合并：预留资金、取消和支出排名

题意与假设

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

• 这是可辨接口构成的训练合同：schedule创建时预留并扣source资金，due执行给target到账并增加source支出；cancel在due之前退款。与接受型transfer和包含deposit的Activity不同。
• 时间严格递增，due≤当前时间的任务先执行，再处理当前请求；delay>0，同deadline按单调serial执行。merge吸收账户的余额/支出及pending两端，旧ID不保留alias。
• 合并导致pending源目标相同时仍按已有预留转账结算并记支出，这是明确训练选择；另一合法规则是取消内部转账退款，实际要求需先定。该二手接口记录不代表所有银行题共享这套规则。

解题路线

1. 用balance/spending/job三组状态和(due,serial)heap。schedule先验证不同且存在账户、额度足够，再扣款写pending。deposit不增spending，withdraw立即增，schedule只有实际执行增。
2. 推进时间用heap逐个取due任务，只执行仍pending记录。cancel不必从heap中部删除，状态改cancelled并退款，后来遇到旧heap项跳过。返回bool/剩余余额与失败None要一致。
3. cancel校验当前source与pending；等于due的请求先让任务执行，所以取消失败。serial不使用timestamp+source字符串，保证未来支持同刻多请求时不会碰撞。
4. merge把absorbed余额、累计支出并入survivor，再重定向所有pending source和target，然后删除absorbed。heap只存serial，执行读job当前端点，避免heap内旧ID导致向已删除账户写入。
5. merge之后取消吸收用户原转账由survivor执行，退款记survivor；到期转账也记录survivor支出。已完成历史记录可保留原身份用于审计，当前排名只包含存续账户，别重写历史来伪造原交易。
6. TopSpending应包含零支出账户，按(-spending,id)排序。若缓存排序结果，create/merge/withdraw/settlement都必须失效；简单全排序基线更容易验证，再优化索引。

手动走一遍

a余额10，schedule(a→b,7,due24)后a可用3。t5把a并入b，pending两端都改b，b可用3。t6由b取消可恢复10；若不取消到24，则b到账7、可用10并记支出7。两种规则选择必须固定，否则合并后钱会丢失或重复增加。

Python 参考实现

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

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

import heapq

class ScheduledBank:
    """Training: reserve funds now; settle at deadline; spending at settlement.

    Due transfers execute before the operation at the same timestamp. Delay>0.
    Merge absorbed into survivor; pending endpoints are remapped, no old ID alias.
    Scheduled self-transfer after merge settles and counts outgoing spending.
    """
    def __init__(self):
        self.balances={};self.spending={};self.jobs={};self.queue=[]
        self.serial=0;self.last=float('-inf')

    def _advance(self,t):
        if t<=self.last:raise ValueError('strictly increasing timestamps required')
        self.last=t
        while self.queue and self.queue[0][0]<=t:
            _,serial=heapq.heappop(self.queue);j=self.jobs[serial]
            if j[4]=='pending':
                source,target,amount,_,_=j
                self.balances[target]+=amount;self.spending[source]+=amount;j[4]='done'

    def create(self,t,account):
        self._advance(t)
        if account in self.balances:return False
        self.balances[account]=0;self.spending[account]=0;return True

    def deposit(self,t,account,amount):
        self._advance(t)
        if amount<=0:raise ValueError('positive amount')
        if account not in self.balances:return None
        self.balances[account]+=amount;return self.balances[account]

    def withdraw(self,t,account,amount):
        self._advance(t)
        if amount<=0:raise ValueError('positive amount')
        if account not in self.balances or self.balances[account]<amount:return None
        self.balances[account]-=amount;self.spending[account]+=amount
        return self.balances[account]

    def schedule(self,t,source,target,amount,delay):
        self._advance(t)
        if amount<=0 or delay<=0:raise ValueError('positive amount and delay')
        if source==target or source not in self.balances or target not in self.balances:return None
        if self.balances[source]<amount:return None
        self.serial+=1;self.balances[source]-=amount
        self.jobs[self.serial]=[source,target,amount,t+delay,'pending']
        heapq.heappush(self.queue,(t+delay,self.serial));return self.serial

    def cancel(self,t,account,serial):
        self._advance(t);j=self.jobs.get(serial)
        if j is None or j[0]!=account or j[4]!='pending':return False
        self.balances[account]+=j[2];j[4]='cancelled';return True

    def merge(self,t,survivor,absorbed):
        self._advance(t)
        if survivor==absorbed or survivor not in self.balances or absorbed not in self.balances:return False
        self.balances[survivor]+=self.balances.pop(absorbed)
        self.spending[survivor]+=self.spending.pop(absorbed)
        for j in self.jobs.values():
            if j[4]=='pending':
                if j[0]==absorbed:j[0]=survivor
                if j[1]==absorbed:j[1]=survivor
        return True

    def top(self,t,n):
        self._advance(t)
        if n<0:raise ValueError('negative count')
        return sorted(self.spending.items(),key=lambda p:(-p[1],p[0]))[:n]

复杂度

普通余额操作O(1)加到期摊销，schedule O(log T)、清理每项O(log T)，merge当前扫描O(T)，排名O(A log A)，空间O(A+T)。每账户pending索引能加速merge，但需同步更新source/target双索引。

易错点与追问

容易失分的边界

• heap保存source/target旧值，merge仅改job却执行时读取heap旧端点，会找不到账户。
• reserve时记支出、due再次记会翻倍，cancel又容易漏减；合同在settlement记一次更清楚。
• 取消需refund预留款，不能只是标记cancelled。

继续深挖

• 如果选择due时才扣款，余额不足的失败与同deadline顺序会如何改变？这是不同合同，需要新的状态与测试。
• 合并后的历史余额和外部账户号alias怎样处理？保存生命周期与映射版本，不能永远把旧ID实时映射到survivor。