Google youtube team (web solution engineer)

上周电面的，当时想不出好的算法，我的interviewer在我电面时，爱理不理的样子，要hint也不给啊，后来我挂了。
大家都有啥可行的算法。不吝赐教

A group of persons goes on the trip, after the trip, they want to evenly split the money.

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

umber of persons
Output who pays who how much?

蠡口司柳武
紫薯紫薯

tinylic 发表于 2018-8-8 09:07
蠡口司柳武
紫薯紫薯

多谢。
查了，这题是hard。电面给我上hard，interviewer会不会玩太大了。

感谢分享！祝好运！
貌似找到平均值之后，可以先把通过一次交易能够抵消两人不均衡的情况找出来。剩下的人是不能通过一次交易抵消两人的情况，如果每次交易都能抵消一个人就已经是最优解了。抵消一个人的方式，可以把均值两边的人分别排序（按照离均值的距离），之后扫一遍，每次交易必能抵消一个人。

np hard问题，必须靠搜索解决。你做不出来不是你的问题，出题人的问题。

有点像Leet Code 小船过河的问题

楼主 建议向hr申诉试试 这种不愿意合作的面试官摆明了想挂人 电面给个hard还不交流 他们是招不到人的。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

garfield175 发表于 2018-8-8 23:25
你的最终目的是找的最多的能抵消的小圈子。如果能够两两抵消，这个是可以直接去掉的。然后就必须找到所有 ...

你说的对。我漏掉多人组成小圈子的情况了。谢谢指出！

这题电面真是相当难，可以转换为找最多的subset sum的问题的。。。