最近在本地几个求职群里看到有人聊 Palantir 面试，提到最多的算法题就是 LeetCode 465，Optimal Account Balancing。我自己这段时间也在刷题，就把这题又捋了一遍，顺手比了下几种 Python 写法，记一下，给也在准备的人看看。
题意其实不复杂，给一串交易记录，每条是 ，问最少几笔转账能把所有人的账抹平。关键第一步不是直接搜，是先算每个人的净余额，收进来的减掉付出去的，最后每个账户就剩一个正数或负数。净额为零的可以直接剔掉，他们不参与结算。这一步做完，问题就从“一堆边”变成“一堆数”，规模一般小很多，后面会好弄不少。
接下来才是搜索。常见写法是 DFS 加记忆化：从第一个非零账户开始，让它跟后面每一个符号相反的账户配对，抵掉一部分金额，再递归，最后取交易笔数最少的那个分支。这里我多说一句，网上不少号称“最优解”的版本其实有问题，如果只是每次让第一个人清零，不做对称性剪枝，很容易跑出次优答案，尤其余额里有重复数字的时候。我自己的做法是把余额去重再排序，用哈希或者位掩码把算过的状态缓存住，再加一条剪枝：当前已经用掉的笔数只要大于等于已知最优解，就直接返回，不往下走。
另一种是贪心，每次拿绝对值最大的债务去配最大的债权，代码短、好讲，面试时能很快说清楚。但它只在部分数据上成立，不能当通解。我拿随机数据跑过几轮，贪心大概七成左右的用例能拿到最优，剩下的会多出一两笔。所以面试官要是追问“能不能保证最少”，还是得回到 DFS。这两种做法的取舍我觉得挺值得在面试里主动点出来，至少能说明你不是在背模板。
Palantir 那边具体怎么考，说实话我不清楚，人在 Halifax，也接触不到他们内部的东西，好在现在大多是线上视频面，地域上倒不受限制。我能感觉到的只是这类题的共性：考的不是你会不会写回溯，而是你能不能先把问题化简，再判断什么时候该剪枝、什么时候该换策略。想问下有没有真正面过的朋友，现场是给完整交易列表，还是只给净额那一步？提示一般给到什么程度？