一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 7180|回复: 39
收起左侧

Google面经——一道可能被大家低估的题

[复制链接] |试试Instant~ |关注本帖
南慕伦 发表于 2016-9-16 12:45:46 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
别的题太水,懒得写了。
只说一个被大家忽视的题,也可能是我这次挂的原因。
. visit 1point3acres.com for more.
这题是简化债务关系,就是给一堆人的账面交易记录,求最少交易次数使得账面平衡。

这题一般有两个思路,一个是把一个人当做中转站,所有人都跟他交易;第二个思路是把所有人的待结款项算出来,然后排序,用two pointer做。

然而这两个方法都不能保证所有情况下交易次数最少,这题实际上是一个NPC问题,可以归结为,在当前集合待结款项正数和负数两个集合中,找到两个不相交的最小子集,使得二者刚好能够结余。不停地寻找这样的子集,删掉,就能够得到最优。然而 subset sum 是NPC,我没想到这一层,结果跪了。. visit 1point3acres.com for more.

另外大家平时在做简单题的时候能够注意一下常数优化,比如减少不必要地循环次数,以及内外层循环计算等问题,我面试的时候这个被问了很多次。. visit 1point3acres.com for more.

第二次被狗家拒,从上海到美国,可能这辈子都不会去Google了。希望下次大家看到这题看到这题能够有所帮助,祝大家好运!

评分

4

查看全部评分

本帖被以下淘专辑推荐:

virpro 发表于 2016-10-6 01:07:10 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
看起来很多同学没理解这个题的考点,我来举例说明一下吧。

假设有A, B, C D, E五个人,债务情况是
A, B, 2
A, C, 4.1point3acres缃
B, D, 5.1point3acres缃
C, D, 4
D, E, 7

那么债务结清之后每个人的结余应该是. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
A, -6.鐣欏璁哄潧-涓浜-涓夊垎鍦
B, -3
C, 0
D, 2
E, 7

这时候C不用参与支付,省下A, B, D, E需要找到最少的支付次数来达到这个状态。最简单的情况是 A ->B -> D -> E (6, 9, 7),需要3次支付。但是如果最终的状态是
A -3,
B -2,
C, 0 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
D, 2
E, 3
那么只需要两次支付就能达到这个状态A -> E (3), B -> D (2)。

类似的,我们可以把所有结余为负的人看成一个集合,例如{A, B},同样的,所有结余为正的人看成一个集合{D, E}。对于正的集合,假设我们能找的一个划分,使得划分后的每一个小集合都能对应到负的集合的一个划分中的一个小集合,那么就能减少需要支付的次数。那么此题就转为求两个集合的最大数量的划分,使得划分中的所有子集都能找到另一个集合的划分里的一个子集。

例如集合{A, B}可以划分为{{A}, {B}}。如果能分别对应到{D, E}到划分{{D},{E}}中的两个子集,即A + E = 0 并且B + D = 0,那总的支付次数会少一次。到这里应该就是楼主说的NPC问题了。

回到这道题,我能想到的一个搜索方法的方式是,对于正负两个集合,找到所有的子集的和,然后在这些和中寻找相等的一对子集。比如我们找到A+E = 0和B+D = 0。那么就可以递归的去求最多的划分次数。这里涉及到重复计算的子问题,可能自底向上更好解决。不知道有没有高手能想出更好的解法。
回复 支持 2 反对 0

使用道具 举报

 楼主| 南慕伦 发表于 2016-9-17 01:56:11 | 显示全部楼层
关注一亩三分地微博:
Warald
这题的做法就是,算清各自应得/应付账款之后,分为正数负数两个集合,0扔掉,然后在正数里面找最小的子集,负数里面找另一个子集,使得存在两个不等于全集的子集,他们的和是相反数,然后合并这两个集合,这样一定是最优的。而找子集的过程就是subset sum,目前看只能穷举,要是你多项式时间做出来,那就图灵奖了。
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-9-16 13:06:58 | 显示全部楼层
楼主能具体说说这道题的输入是什么?用什么数据结构表示这些人的交易记录呢?
回复 支持 反对

使用道具 举报

 楼主| 南慕伦 发表于 2016-9-16 13:33:46 | 显示全部楼层
wtcupup 发表于 2016-9-16 13:06
楼主能具体说说这道题的输入是什么?用什么数据结构表示这些人的交易记录呢?

三元组吧
(a, b, v)
账面交易a需要给b v元
回复 支持 反对

使用道具 举报

hulahu 发表于 2016-9-16 13:52:46 | 显示全部楼层
坐等大牛们的code
回复 支持 反对

使用道具 举报

siriuswang 发表于 2016-9-16 14:11:05 | 显示全部楼层
请问楼主,这是什么意思?“找到两个不相交的最小子集,使得二者刚好能够结余。” 能举个例子吗?
回复 支持 反对

使用道具 举报

wenzhu 发表于 2016-9-16 14:54:59 | 显示全部楼层
马克。没思路...
回复 支持 反对

使用道具 举报

constancelee 发表于 2016-9-16 14:59:26 | 显示全部楼层
马。坐等大牛
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-16 18:20:54 | 显示全部楼层
LZ, do you mind share the details about this 第二次被狗家拒,从上海到美国,可能这辈子都不会去Google了?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-16 19:32:29 | 显示全部楼层
这个题当时要求实现找minimal transaction的算法吗,还是先讲一个naive的,minimal transaction的聊聊就好...
不过纠结于subset sum是NPC就据了,觉得挺过分的啊...
回复 支持 反对

使用道具 举报

zsj2725 发表于 2016-9-16 20:23:51 | 显示全部楼层
siriuswang 发表于 2016-9-16 14:11
请问楼主,这是什么意思?“找到两个不相交的最小子集,使得二者刚好能够结余。” 能举个例子吗?

应该是指能够结清吧
类似(a,b,1) + (b,a,1)
或者 (a,b,2)+(b,c,2)+(c,a,2)
回复 支持 反对

使用道具 举报

lzb700m 发表于 2016-9-16 21:30:10 | 显示全部楼层
是N角债问题吗?N个人有欠钱的,有借钱的,但是总体balance是0。问最少多少次交易可以让所有人不欠钱也不被欠?
如果是这个问题的话,最多N-1次交易(每次交易至少有一个人的balance变成0),最少的交易次数可以用BFS搜一下。
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-9-16 22:13:22 | 显示全部楼层
mark,只会写naive的,坐等大牛代码
回复 支持 反对

使用道具 举报

 楼主| 南慕伦 发表于 2016-9-17 01:48:35 | 显示全部楼层
lzb700m 发表于 2016-9-16 21:30
是N角债问题吗?N个人有欠钱的,有借钱的,但是总体balance是0。问最少多少次交易可以让所有人不欠钱也不被 ...

我不知道你怎么搜……
回复 支持 反对

使用道具 举报

 楼主| 南慕伦 发表于 2016-9-17 01:48:46 | 显示全部楼层
zsj2725 发表于 2016-9-16 20:23
应该是指能够结清吧
类似(a,b,1) + (b,a,1)
或者 (a,b,2)+(b,c,2)+(c,a,2)
. from: 1point3acres.com/bbs
没错 是指能结清
回复 支持 反对

使用道具 举报

 楼主| 南慕伦 发表于 2016-9-17 01:49:59 | 显示全部楼层
hxtang 发表于 2016-9-16 19:32
这个题当时要求实现找minimal transaction的算法吗,还是先讲一个naive的,minimal transaction的聊聊就好. ...

naive的自然讲了,估计是bar高,要是别人能看出来你看不出来不就跪了嘛……而且我看面经这并不是Google面的唯一的NPC问题
. 1point3acres.com/bbs
补充内容 (2016-9-17 01:52):
面试官一直往这方面给我举反例,我只是一步一步写算法解决各种反例,而没有从NPC这个角度来想……
回复 支持 反对

使用道具 举报

 楼主| 南慕伦 发表于 2016-9-17 01:51:22 | 显示全部楼层
leonardcohen 发表于 2016-9-16 18:20
LZ, do you mind share the details about this 第二次被狗家拒,从上海到美国,可能这辈子都不会去Google ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
大三暑假面了一下fulltime,被拒了,然后来美国读了个研究生再面,又被拒了,哈哈……不过大三确实是我当时铁了心出国,刚实习完都在做项目也没怎么针对性地准备coding,傻逼题没bug free.
回复 支持 反对

使用道具 举报

shuiguo 发表于 2016-9-17 02:06:14 | 显示全部楼层
是面试的时候被指出这其实是NPC问题,还是之后lz想到的?
回复 支持 反对

使用道具 举报

 楼主| 南慕伦 发表于 2016-9-17 02:12:22 | 显示全部楼层
shuiguo 发表于 2016-9-17 02:06
是面试的时候被指出这其实是NPC问题,还是之后lz想到的?

我当时没想到,也没指出,后来想到的。后来被拒之后我反反复复回忆,觉得就这一轮问题比较大。

补充内容 (2016-9-17 02:12):
但是当时面试官很明显就往这上面引了,因为不停地构造反例给我
回复 支持 反对

使用道具 举报

jason51122 发表于 2016-9-17 02:23:36 | 显示全部楼层
南慕伦 发表于 2016-9-17 01:56
这题的做法就是,算清各自应得/应付账款之后,分为正数负数两个集合,0扔掉,然后在正数里面找最小的子集, ...

求问楼主能提供一个例子吗 还是没懂啊
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-1 12:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表