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

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

求问楼主能提供一个例子吗 还是没懂啊

南慕伦 发表于 2016-9-17 01:49
naive的自然讲了，估计是bar高，要是别人能看出来你看不出来不就跪了嘛……而且我看面经这并不是Google面 ...

我当时看到这个面经的时候，想到了subset sum，没想到subset sum是NPC...
埋头去看NPC了...

有点像二分图的最佳匹配问题？

不好意思，请问楼主这道题是不是NPC有很大的关系嘛？或者楼主的point是说这道题只能有穷举来解才能得最优？

同求solution，这个题还是挺典型的

楼主 有没有问问 feedback 是不是 因为这道题

不过 这样看应该 就是直接 brute force 解就好了
是interviewer 不让写(如果 是 是不是可以 和 hr argur 下) 还是 ？ 因为 如果 按楼主说的 通常的 两个办法 那应该是 不对的

gg 面试 应该 要写出来 一个 code  没有 code 会不太好

想到一个 n!的解，用递归f(n)=(n-1)f(n-1).

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

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

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.         }

复制代码