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

别的题太水，懒得写了。
只说一个被大家忽视的题，也可能是我这次挂的原因。

这题是简化债务关系，就是给一堆人的账面交易记录，求最少交易次数使得账面平衡。

这题一般有两个思路，一个是把一

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

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

。

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

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

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

这题的做法就是，算清各自应得/应付账款之后，分为正数负数两个集合，0扔掉，然后在正数里面找最小的子集，负数里面找另一个子集，使得存在两个不等于全集的子集，他们的和是相反数，然后合并这两个集合，这样一定是最优的。而找子集的过程就是subset sum，目前看只能穷举，要是你多项式时间做出来，那就图灵奖了。

lzb700m 发表于 2016-9-16 21:30
是N角债问题吗？N个人有欠钱的，有借钱的，但是总体balance是0。问最少多少次交易可以让所有人不欠钱也不被 ...

写了一个，可以这样搜。

1.         class Balance {
   
2.                 int level;
   
3.                 List<Integer> lender;
   
4.                 List<Integer> borrower;
   
5. 
   
6.                 Balance(int level, List<Integer> posVals, List<Integer> negVals) {
   
7.                         this.level = level;
   
8.                         lender = posVals;
   
9.                         borrower = negVals;
   
10.                 }
    
11. 
    
12.                 public List<Balance> payOnce() {
    
13.                         List<Balance> ans = new ArrayList<>();
    
14.                         for (int i = 0; i < lender.size(); i++)
    
15.                                 for (int j = 0; j < borrower.size(); j++) {
    
16.                                         int pos = lender.get(i);
    
17.                                         int neg = borrower.get(j);
    
18.                                         List<Integer> newLender = new ArrayList<>(lender);
    
19.                                         List<Integer> newBorrower = new ArrayList<>(borrower);
    
20.                                         newLender.remove(i);
    
21.                                         newBorrower.remove(j);
    
22. 
    
23.                                         int diff = pos + neg;
    
24.                                         if (diff > 0)
    
25.                                                 newLender.add(pos + neg);
    
26.                                         else if (diff < 0)
    
27.                                                 newBorrower.add(pos + neg);
    
28. 
    
29.                                         ans.add(new Balance(level + 1, newLender, newBorrower));
    
30.                                 }
    
31.                         return ans;
    
32.                 }
    
33. 
    
34.                 public boolean balanced() {
    
35.                         return lender.isEmpty() && borrower.isEmpty();
    
36.                 }
    
37. 
    
38.                 public String toString() {
    
39.                         return borrower.toString() + ", " + lender.toString()
    
40.                                         + ", # of payments: " + level;
    
41.                 }
    
42.         }
    
43. 
    
44.         public int pay(int[] paid) {
    
45.                 int n = paid.length;
    
46.                 long total = 0;
    
47.                 for (int amount : paid) {
    
48.                         total += amount;
    
49.                 }
    
50.                 if (total % n != 0)
    
51.                         throw new IllegalArgumentException(
    
52.                                         "Total amount can not be evenly divided.");
    
53.                 int avg = (int) total / n;
    
54. 
    
55.                 List<Integer> pos = new ArrayList<>();
    
56.                 List<Integer> neg = new ArrayList<>();
    
57.                 for (int amount : paid) {
    
58.                         int diff = amount - avg;
    
59.                         if (diff > 0)
    
60.                                 pos.add(diff);
    
61.                         else if (diff < 0)
    
62.                                 neg.add(diff);
    
63.                 }
    
64. 
    
65.                 Balance initialBalance = new Balance(0, pos, neg);
    
66.                 Queue<Balance> queue = new LinkedList<>();
    
67.                 queue.offer(initialBalance);
    
68.                 int ans = Integer.MAX_VALUE;
    
69.                 while (true) {
    
70.                         Balance cur = queue.poll();
    
71.                         System.out.println(cur);
    
72.                         if (cur.balanced()) {
    
73.                                 ans = cur.level;
    
74.                                 break;
    
75.                         }
    
76.                         List<Balance> nextLevel = cur.payOnce();
    
77.                         for (Balance newBalance : nextLevel)
    
78.                                 queue.offer(newBalance);
    
79.                 }
    
80. 
    
81.                 return ans;
    
82.         }

复制代码

楼主能具体说说这道题的输入是什么？用什么数据结构表示这些人的交易记录呢？

wtcupup 发表于 2016-9-16 13:06
楼主能具体说说这道题的输入是什么？用什么数据结构表示这些人的交易记录呢？

三元组吧
(a, b, v)
账面交易a需要给b v元

坐等大牛们的code

请问楼主，这是什么意思？“找到两个不相交的最小子集，使得二者刚好能够结余。” 能举个例子吗？

马克。没思路...

马。坐等大牛

LZ, do you mind share the details about this 第二次被狗家拒，从上海到美国，可能这辈子都不会去Google了?

这个题当时要求实现找minimal transaction的算法吗，还是先讲一个naive的，minimal transaction的聊聊就好...
不过纠结于subset sum是NPC就据了，觉得挺过分的啊...

siriuswang 发表于 2016-9-16 14:11
请问楼主，这是什么意思？“找到两个不相交的最小子集，使得二者刚好能够结余。” 能举个例子吗？

应该是指能够结清吧
类似（a,b,1) + (b,a,1)
或者 (a,b,2)+(b,c,2)+(c,a,2)