Snapchat电面

Snapchat 第一个电面，面试官应该是一个中国人，还是挺友好的。先是问了问简历里面的项目，然后就直接做题了。因为面试之前看了地里面的

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

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

ollow up:要求分别输出每个group
BFS解决的这道题。

超分 发表于 2016-9-28 13:27
楼主，输出为什么是2？1认识0，1认识2 —> 0,1,2算一个group？那输出不就应该是1了吗？

一共有三个人啊：0，1，2，3.最后一个人谁也不认识，所以自己独立算一个group～～

补充内容 (2016-9-29 00:40):
一共是四个人哈。最后一个自己一个group

1. public class Solution {
   
2.     public List<List<Integer>> groupOfFriend(int[][] matrix) {
   
3.         if(matrix == null || matrix.length == 0) return new ArrayList<>();
   
4. 
   
5.         List<List<Integer>> res = new ArrayList<>();
   
6.         int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
   
7. 
   
8.         for(int i = 0; i < matrix.length; i++) {
   
9.             for(int j = i; j < matrix[0].length; j++) {
   
10.                 Set<Integer> tmpRes = new HashSet<>();
    
11.                 if(j >= i && matrix[i][j] == 1) {
    
12.                     tmpRes.add(i);
    
13.                     matrix[i][j] = 0;
    
14.                     dfs(matrix, i, j, tmpRes, dirs);
    
15.                     res.add(new ArrayList<>(tmpRes));
    
16.                 }
    
17.             }
    
18.         }
    
19.         return res;
    
20.     }
    
21. 
    
22.     private void dfs(int[][] matrix, int i, int j, Set<Integer> tmpRes, int[][] dirs) {
    
23.         tmpRes.add(j);
    
24.         matrix[i][j] = 0;
    
25.         for(int[] dir: dirs) {
    
26.             int newRow = i + dir[0], newCol = j + dir[1];
    
27.             if(newRow >= 0 && newCol >= 0 && newCol < matrix[0].length && newRow < matrix.length &&
    
28.                     newCol >= newRow && matrix[newRow][newCol] == 1) {
    
29.                 dfs(matrix, newRow, newCol, tmpRes, dirs);
    
30.             }
    
31.         }
    
32.     }
    
33. }

复制代码

是不是把explore改一下就行了？

1. public int numIslands(char[][] grid) {
   
2.         if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
   
3.         int island = 0;
   
4.         for (int i = 0; i < grid.length; i++) {
   
5.             for (int j = 0; j < grid[0].length; j++) {
   
6.                 if (grid[i][j] == '1') {
   
7.                     explore(grid, i, j);
   
8.                     island++;
   
9.                 }
   
10.             }
    
11.         }
    
12.         return island;
    
13.     }
    
14.    
    
15.     private void explore (char[][] grid, int i, int j) {
    
16.         grid[i][j] = '0';
    
17.         for (int k = j+1; k < grid[i].length; k++) {
    
18.                 if (grid[i][k] == '1') explore(grid, i, k);
    
19.         }
    
20.         
    
21.         for (int k = i+1; k < grid.length; k++) {
    
22.                 if (grid[k][j] == '1') explore(grid, k, j);
    
23.         }
    
24.     }

复制代码

Union and Find?

超分 发表于 2016-9-22 03:41
Union and Find?

可以union and find, 但是更简单的是dfs，每遇到一个1都flip成0，在外层count++，最后返回count。参考leetcode island I这题，island II是union and find

超分 发表于 2016-9-22 03:41
Union and Find?

Union and Find可以，但是个人觉得直接DFS或者BFS稍微方便一些吧～～

number of Islands 吗不是。

JunlinZhu 发表于 2016-9-22 04:10
number of Islands 吗不是。

变形吧，下一个node的走向不是上下左右了，而是对应的那一列/行

这题是不是可以理解为 求matrix里面有多少个正方形

超分 发表于 2016-9-22 04:13
变形吧，下一个node的走向不是上下左右了，而是对应的那一列/行

谢谢楼主分享。

谢谢楼主分享