2019 google summer intern电面

hlckl123456 发表于 2018-10-30 15:14
哈哈哈  太秀了吧。。  大佬大佬

主要是国内逼得。国内有些公司面试的时候说实话跟智障一样。那次去面试人家说你top2连个红黑树40分钟都写不出来？我是很服的，美国我打赌百分之99的程序员40分钟撸不出来红黑树。

hlckl123456 发表于 2018-10-30 14:25
提供一个方法
10000
11000

感谢大佬！！！

foryousee 发表于 2018-10-31 00:38
主要是国内逼得。国内有些公司面试的时候说实话跟智障一样。那次去面试人家说你top2连个红黑树40分钟都写 ...

层主 无意之间 暴露了自己是top2的大佬  摩拜

foryousee 发表于 2018-10-28 01:36
就是说对于一个点，它的row或者col有任意点，就可以被移除。然后求最多可以移除多少个点。之后就是求有多 ...

请问对于两个不直接相连的cluster怎么使用union find？

1. typedef pair<int, int> Pair;
   
2. class Solution {
   
3. public:
   
4.         int row = 0, col = 0, total = 0;
   
5.         void merge(vector<int>& parents, int x, int y) {
   
6.                 while (parents[x] != x) {
   
7.                         x = parents[x] = parents[parents[x]]; // union find speed up
   
8.                         y = parents[y] = parents[parents[y]];
   
9.                 }
   
10.                 if (x != y) total -= 1;
    
11.                 parents[x] = y;
    
12.                 return;
    
13.         }
    
14. 
    
15.         int unionMurble(vector<vector<int>> board) {
    
16.                 row = board.size(); col = board[0].size();
    
17.                 total = row * col;
    
18.                 // record last row/col of murble appreared to speed up
    
19.                 vector<int> rowIdx(row, -1), colIdx(col, -1);
    
20.                 vector<int> parents(row*col); // union find
    
21.                 for (int i=0;i<row;i++)
    
22.                         for (int j = 0; j < col; j++) {
    
23.                                 parents[i*row + j] = i * row + j;
    
24.                                 if (board[i][j] == 0) total -= 1;
    
25.                                 else {
    
26.                                         if (colIdx[j] >= 0) merge(parents, colIdx[j] * row + j, i*row + j);
    
27.                                         if (rowIdx[i] >= 0) merge(parents, i*row + rowIdx[i], i*row + j);
    
28.                                         colIdx[j] = i; rowIdx[i] = j; // update last row and col
    
29.                                 }
    
30.                         }
    
31.                 return total; // return num of murble cluster
    
32.         }
    
33. };

复制代码

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

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