Google 电面+VO 详细behavioral questions

楼主转码，面的Early career

电面：先是设计classes for a custom word string tree (类似trie但是要区分中间node vs leaf node两个不同的class，而且要记录子树里存的string总长度）。然后再实现一个method找从前往后数tree里存的第n个letter。
VO：
第一轮 googliness / BQ:

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
三轮：基本上就是写个splitwise的逻辑。一开始不要求交易数量最小。用了两种方法写，写完后没时间了就没问follow up。但我知道follow up是利口斯溜舞，估计问了我也当场做不出来

第四轮：利口尔伞揪

焦急等待结果中。。。希望能过，求加米

楼主是怎么记得题号的呢 我只记得有这么道题 但是记不住题号

店面可以给个例子吗

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

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

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

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

第三轮请问楼主用哪2种方法做的？

下面我用2个PQ来做的

注意斯溜舞给出的是交易，我们需要返回的是 int[] {a, b, num}也就是a 还给b $num

1. public List<int[]> minTransfers(int[][] transactions) {
   
2. 
   
3.         // Key: person's ID   Value: person's balance after calculation
   
4.         // {1 : -5} means person 1 should get $5
   
5.         // {2 : 10} means person 2 should pay $10
   
6.         Map<Integer, Integer> map = new HashMap<>();
   
7.         for (int[] trans : transactions) {
   
8.             map.put(trans[0], map.getOrDefault(trans[0], 0) - trans[2]);
   
9.             map.put(trans[1], map.getOrDefault(trans[1], 0) + trans[2]);
   
10.         }
    
11. 
    
12.         // Since after we get those amount of balance, person's ID does not affect the final result
    
13.         PriorityQueue<int[]> ownHeap = new  PriorityQueue<>((a, b) -> Integer.compare(b[1], a[1])); // debt owner
    
14.         PriorityQueue<int[]> colHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[1], a[1])); // debt collector
    
15.         int n = map.size(), i = 0;
    
16.         int[] balance = new int[n];
    
17.         for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
    
18.             int id = entry.getKey();
    
19.             int bal = entry.getValue();
    
20.             balance[id] = bal;
    
21.             if (bal > 0) {
    
22.                 ownHeap.offer(new int[]{id, bal});
    
23.             } else if (bal < 0) {
    
24.                 colHeap.offer(new int[]{id, -bal});
    
25.             }
    
26.         }
    
27.         List<int[]> res = new ArrayList<>();
    
28.         while (!ownHeap.isEmpty() && !colHeap.isEmpty()) {
    
29.             int[] curOwner = ownHeap.poll();
    
30.             int curOwnerId = curOwner[0];
    
31.             int curOwnerNum = curOwner[1];
    
32.             int[] curCollector = colHeap.poll();
    
33.             int curCollectorId = curCollector[0];
    
34.             int curCollectorNum = curCollector[1];
    
35.             int sum = curOwnerNum - curCollectorNum;
    
36.             if (sum > 0) {
    
37.                 ownHeap.offer(new int[]{curOwnerId, sum});
    
38.                 res.add(new int[]{curOwnerId, curCollectorId, curCollectorNum});
    
39.             } else if (sum < 0) {
    
40.                 colHeap.offer(new int[]{curCollectorId, -sum});
    
41.                 res.add(new int[]{curOwnerId, curCollectorId, curOwnerNum});
    
42.             } else if (sum == 0) {
    
43.                 res.add(new int[]{curOwnerId, curCollectorId, curOwnerNum});
    
44.             }
    
45.         }
    
46. 
    
47.         return res;
    
48.     }

复制代码

sort后双指针

1. public List<int[]> transfers(int[][] transactions) {
   
2.         // Key: person's ID   Value: person's balance after calculation
   
3.         // {1 : -5} means person 1 should get $5
   
4.         // {2 : 10} means person 2 should pay $10
   
5.         Map<Integer, Integer> map = new HashMap<>();
   
6.         for (int[] trans : transactions) {
   
7.             map.put(trans[0], map.getOrDefault(trans[0], 0) - trans[2]);
   
8.             map.put(trans[1], map.getOrDefault(trans[1], 0) + trans[2]);
   
9.         }
   
10. 
    
11.         List<int[]> balances = new ArrayList<>();
    
12.         for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
    
13.             int id = entry.getKey();
    
14.             int bal = entry.getValue();
    
15.             balances.add(new int[]{id, bal});
    
16.         }
    
17.         Collections.sort(balances,(a, b) -> Integer.compare(a[1], b[1]));
    
18. 
    
19.         List<int[]> res = new ArrayList<>();
    
20.         for (int i = 0, j = balances.size() - 1; i < j; ) {
    
21.             int[] p1 = balances.get(i);
    
22.             int[] p2 = balances.get(j);
    
23.             int p1Id = p1[0];
    
24.             int p1Num = p1[1];
    
25.             int p2Id = p2[0];
    
26.             int p2Num = p2[1];
    
27.             if (p1Num == 0) {
    
28.                 i++;
    
29.                 continue;
    
30.             }
    
31.             if (p1Num == 0) {
    
32.                 j--;
    
33.                 continue;
    
34.             }
    
35.             int sum = p1Num + p2Num; // x < 0, y > 0
    
36.             if (sum == 0) {
    
37.                 res.add(new int[]{p2Id, p1Id, p2Num});
    
38.                 i++;
    
39.                 j--;
    
40.             }else if (sum > 0) {
    
41.                 res.add(new int[]{p2Id, p1Id, -p1Num});
    
42.                 i++;
    
43.             } else {
    
44.                 res.add(new int[]{p2Id, p1Id, p2Num});
    
45.                 j--;
    
46.             }
    
47.         }
    
48. 
    
49.         return res;
    
50.     }

复制代码

Falldawn 发表于 2022-7-11 16:06
第三轮请问楼主用哪2种方法做的？

下面我用2个PQ来做的

请问greedy不能确保是最少的transfer对吧？

cailucun 发表于 2022-7-17 15:39
请问greedy不能确保是最少的transfer对吧？

肯定不能