x*****n
发帖数: 195 | 1 ADP那么烂的都值那么多钱，看好zenpayroll。自己在AngelList上直接投的。大概是因
为不在湾区，要求第3轮店面，挂了。前两面题目都不难，记不清了，leetcode easy到
medium的样子。但需要很快写完code然后在codepad里跑测试，然后改点条件，你马上
改code跑新的测试用例。
第三面的题目是简化欠钱还钱关系，比如A借给B 50元，B给C 50元，C给A 20元，那最
后可以简化为A给了C 30元。输入输出数据结构自己定义。A可以多次借钱给B，这些细
节都需要自己问出来。
开头就想到了直接算每个人汇总后到底是应得x元钱还是欠人x元钱这个简化思路，但想
不出之后怎么建立最优（少）的借钱还钱mapping关系。。。于是按类似topology sort
的思想直接按各个path简化，简化到简化不下去感觉应该是最优解，知道zenpayroll的
风格是要code能跑起来，拼命写还是没写完能跑的code。最后跟面试官讨论了他的解法
，就是按我最开始时的思路统计各个人的结余，然后他说按贪心法做好了，虽然不一定
最优（简化后的借钱欠钱关系数最少），但一般也接近最优了。囧了，我死脑筋了，他
出题时说的好像的确只是简化，没说一定要简化到最少。大概刷题的副作用吧总是脑补
找最多，最少，最快，空间最小等等=。=
后来又想了一下，基于那个解法找出最优也是可以的，DFS暴力解，可以转化为NPC的
subset sum问题，效率没按toposort暴力简化paths高（但code写起来太复杂了）。整
理了一下发给email给面试小哥讲这个分析，当然没人啥卵用，几个小时后收到拒信。 | g****o
发帖数: 547 | 2 简化欠钱还钱关系 是g家常考题阿
不过看样子，要求不同。你这个是要求代码能跑起来，哪怕不是最优，解决问题就行 | p*********g
发帖数: 2998 | 3 你一开始想的统计余额是最简单的了,那么输了就是存入一个hashmap,借出做减法,借进
为加法
输出 一个排序, 2边往当中走, 负的指向正的, start+end<0 那么indxend--,start=
start+end 否则indxstart++, end=start+end |
|
