Snapchat电面面经

wangmengcathy 发表于 2016-4-19 18:27
求问楼主这题和number of islands的区别?

Number of island 1 是必须要连在一起在算一组 但是这个比如1和2，1和5是朋友 这样他们是一组的 我觉得如果你用BFS的话 应该就不行 因为1和2连着 但是中间是0就走不到5 但是如果用union find的话 就是一样的方法了 没什么差别

谎言之躯 发表于 2016-4-15 00:22
通过bfs/dfs是不是也能做出来？ 参考这道题https://leetcode.com/problems/number-of-islands/

比如这种matrix
[[1, 0, 1],
[0, 1, 0],
[1, 0, 1]]
这样我觉得用BFS应该就不行吧

u-r-the-one 发表于 2016-4-20 08:26
Number of island 1 是必须要连在一起在算一组 但是这个比如1和2，1和5是朋友 这样他们是一组的 我觉得如 ...

多谢楼主解释，那这道题确实可用dfs或者union find，bfs的话不够intuitive。自己写了个UF版本的。

1. class Untitled {
   
2.         public static void main (String [] args) {
   
3.                 int[][] friends = {{1,0,1}, {0, 1, 0}, {1, 0, 1}};
   
4.                 System.out.println(groupFriends(friends));
   
5.         }
   
6.        
   
7.         public static int groupFriends(int[][] matrix) {
   
8.                 UnionFind uf = new UnionFind(matrix);
   
9.                 int m = matrix.length;
   
10.                 int n = matrix[0].length;
    
11.                 for(int i = 0; i < m; i++) {
    
12.                         for(int j = 0; j < n; j++) {
    
13.                                 if(matrix[i][j] == 1) {
    
14.                                         uf.union(i, j);
    
15.                                 }
    
16.                         }
    
17.                 }
    
18.                 return uf.count;
    
19.         }
    
20. }
    
21. 
    
22. class UnionFind {
    
23.         public int count = 0;
    
24.         private int[] id = null;
    
25.         public UnionFind(int[][] matrix) {
    
26.                 count = matrix.length;
    
27.                 id = new int[count];
    
28.                 for(int i = 0; i < id.length; i++) id[i] = i;
    
29.         }
    
30.        
    
31.         public int find(int p) {
    
32.                 while(p != id[p]) {
    
33.                         p = id[p];
    
34.                 }
    
35.                 return p;
    
36.         }
    
37.        
    
38.         public boolean union(int p, int q) {
    
39.                 p = find(p);
    
40.                 q = find(q);
    
41.                 if(p == q) return false;
    
42.                 id[p] = q;
    
43.                 count--;
    
44.                 return true;
    
45.         }
    
46. }

复制代码

这题BFS，DFS都可以做，和number of Island 1的区别在于，比如对于friend i, 不是对上下左右四个点做进一步的搜索，而是对i的所在的那一行进行搜索。当然，要加visited set进行判断已经搜过的friend 例如dfs:

1.     public static void dfs(int[][] matrix, HashSet<Integer> visited, int curr){
   
2.         visited.add(curr);
   
3.         int n = matrix.length;
   
4.         for(int i=0;i<n;i++){
   
5.             if(matrix[curr][i]==1 && i!=curr && !visited.contains(i)){
   
6.                 dfs(matrix,visited,i);
   
7.             }
   
8.         }
   
9.     }

复制代码

能用DFS, BFS就也是可以的。

1.     public void bfs(int[][] matrix, HashSet<Integer> visisted, int k){
   
2.         visited.add(k);
   
3.         Queue<Integer> q = new LinkedList<>();
   
4.         q.offer(k);
   
5.         int n = matrix.length;
   
6.         
   
7.         while(!q.isEmpty()){
   
8.             int curr = q.poll();
   
9.             for(int i=0;i<n;i++){
   
10.                 if(int[curr][i]==1 && i!=curr && !visited.contains(i)){
    
11.                     q.offer(i);
    
12.                     visited.add(i);
    
13.                 }
    
14.             }
    
15.         }
    
16.     }

复制代码

u-r-the-one 发表于 2016-4-20 08:31
比如这种matrix
[[1, 0, 1],
[0, 1, 0],

把[n][n]忽略了就ok了....

楼主您好，我是昨天国人电面string compare，但目前还没有收到消息，最后有小bug没跳出来。不知一般要等多久有下一步消息。

kemeng1314 发表于 2016-5-5 23:21
楼主您好，我是昨天国人电面string compare，但目前还没有收到消息，最后有小bug没跳出来。不知一般要等多 ...

我是周五面的 周一给的onsite消息

u-r-the-one 发表于 2016-5-6 12:23
我是周五面的 周一给的onsite消息

有bug的话就很难有next step了吧，但思路说的特别多。不知道会不会给个加面的机会。

kemeng1314 发表于 2016-5-5 23:25
有bug的话就很难有next step了吧，但思路说的特别多。不知道会不会给个加面的机会。

这也不好说 我有同学就是被加面了 他们应该还是看中你思路怎么样 他给你提示了的话看你反应快不快 祝你好运！