在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5560|回复: 24
收起左侧

Snapchat电面

[复制链接] |试试Instant~ |关注本帖
Lynnklj 发表于 2016-9-22 03:31:29 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类General 硕士 全职@Snapchat - 内推 - 技术电面  | Other | fresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
Snapchat 第一个电面,面试官应该是一个中国人,还是挺友好的。先是问了问简历里面的项目,然后就直接做题了。因为面试之前看了地里面的面经,感觉帮助还是挺大的,题目就是Group of Friends.给一个matrix:. From 1point 3acres bbs
如果 matrix[i][j]=1说明 i knows j,然后问有多少个group. 比如:
{1,1,0,0}
{1,1,1,0}
{0,1,1,0}
{0,0,0,1}
输出就是2
follow up:要求分别输出每个group
BFS解决的这道题。

评分

2

查看全部评分

 楼主| Lynnklj 发表于 2016-9-29 00:38:08 | 显示全部楼层
超分 发表于 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 反对 0

使用道具 举报

超分 发表于 2016-9-22 03:41:24 | 显示全部楼层
Union and Find?
回复 支持 反对

使用道具 举报

xietao0221 发表于 2016-9-22 03:47:11 | 显示全部楼层

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

使用道具 举报

 楼主| Lynnklj 发表于 2016-9-22 04:00:36 | 显示全部楼层

Union and Find可以,但是个人觉得直接DFS或者BFS稍微方便一些吧~~
回复 支持 反对

使用道具 举报

JunlinZhu 发表于 2016-9-22 04:10:17 | 显示全部楼层
number of Islands 吗不是。
回复 支持 反对

使用道具 举报

超分 发表于 2016-9-22 04:13:57 | 显示全部楼层
JunlinZhu 发表于 2016-9-22 04:10
number of Islands 吗不是。

变形吧,下一个node的走向不是上下左右了,而是对应的那一列/行
回复 支持 反对

使用道具 举报

frouds 发表于 2016-9-22 04:40:04 | 显示全部楼层
这题是不是可以理解为 求matrix里面有多少个正方形
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

cheeroh 发表于 2016-9-22 04:50:15 | 显示全部楼层
是不是把explore改一下就行了?. more info on 1point3acres
. from: 1point3acres
  1. public int numIslands(char[][] grid) {
  2.         if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;.1point3acres网
  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.     }
复制代码
回复 支持 反对

使用道具 举报

JunlinZhu 发表于 2016-9-22 07:45:55 | 显示全部楼层
超分 发表于 2016-9-22 04:13-google 1point3acres
变形吧,下一个node的走向不是上下左右了,而是对应的那一列/行

谢谢楼主分享。
回复 支持 反对

使用道具 举报

warmland 发表于 2016-9-23 03:35:07 | 显示全部楼层
谢谢楼主分享
回复 支持 反对

使用道具 举报

xietao0221 发表于 2016-9-28 12:18:16 | 显示全部楼层
  1. public class Solution {
  2.     public List<List<Integer>> groupOfFriend(int[][] matrix) {
  3.         if(matrix == null || matrix.length == 0) return new ArrayList<>();

  4.         List<List<Integer>> res = new ArrayList<>();-google 1point3acres
  5.         int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};

  6.         for(int i = 0; i < matrix.length; i++) {
  7.             for(int j = i; j < matrix[0].length; j++) {
  8.                 Set<Integer> tmpRes = new HashSet<>();
  9.                 if(j >= i && matrix[i][j] == 1) {
  10.                     tmpRes.add(i);
  11.                     matrix[i][j] = 0;
  12.                     dfs(matrix, i, j, tmpRes, dirs);
  13.                     res.add(new ArrayList<>(tmpRes));
  14.                 }
  15.             }
  16.         }
  17.         return res;
  18.     }
  19. . more info on 1point3acres
  20.     private void dfs(int[][] matrix, int i, int j, Set<Integer> tmpRes, int[][] dirs) {
  21.         tmpRes.add(j);
  22.         matrix[i][j] = 0;
  23.         for(int[] dir: dirs) {
  24.             int newRow = i + dir[0], newCol = j + dir[1];
  25.             if(newRow >= 0 && newCol >= 0 && newCol < matrix[0].length && newRow < matrix.length &&
  26.                     newCol >= newRow && matrix[newRow][newCol] == 1) {
  27.                 dfs(matrix, newRow, newCol, tmpRes, dirs);. 1point 3acres 论坛
  28.             }
  29.         }
  30.     }
  31. }
复制代码
回复 支持 反对

使用道具 举报

超分 发表于 2016-9-28 13:27:51 | 显示全部楼层
楼主,输出为什么是2?1认识0,1认识2 —> 0,1,2算一个group?那输出不就应该是1了吗?
回复 支持 反对

使用道具 举报

 楼主| Lynnklj 发表于 2016-9-29 00:39:26 | 显示全部楼层
不对,一共四个人~~。然后最后一个人谁也不认识,所以自己成一个group。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-29 00:49:06 | 显示全部楼层

这个应该不是上下左右搜吧? 当遇到一个1以后,应该一整行,一整列得去搜吧?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-29 00:50:38 | 显示全部楼层
Lynnklj 发表于 2016-9-29 00:39
不对,一共四个人~~。然后最后一个人谁也不认识,所以自己成一个group。

. 牛人云集,一亩三分地多谢楼主分享。 请问应该就是八楼分享的代码那样的吧?
回复 支持 反对

使用道具 举报

 楼主| Lynnklj 发表于 2016-9-29 01:34:58 | 显示全部楼层
小A要当码农 发表于 2016-9-29 00:50
多谢楼主分享。 请问应该就是八楼分享的代码那样的吧?

嗯,其实BFS或者DFS都可以~
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-9-29 06:55:09 | 显示全部楼层
Lynnklj 发表于 2016-9-29 01:34
嗯,其实BFS或者DFS都可以~

所以肯定是symmetric matrix吗?

. from: 1point3acres 一个group of friends的定义就是 这个group里的任何人必须被至少一个group里的人认识吗?
回复 支持 反对

使用道具 举报

 楼主| Lynnklj 发表于 2016-9-29 07:18:01 | 显示全部楼层
linweihua0 发表于 2016-9-29 06:55
所以肯定是symmetric matrix吗?

一个group of friends的定义就是 这个group里的任何人必须被至少一个 ...

嗯,是的是的。一定是对称的~~
回复 支持 反对

使用道具 举报

hjx447297354 发表于 2016-10-19 10:01:15 | 显示全部楼层

这道题好像和number of island不太一样把,他不是算所有1连成的区域,每个1代表的是i knows j。比如:. 1point 3acres 论坛
{1,1,0,1}
{1,1,1,0}
{0,1,1,0}
{1,0,0,1}.1point3acres网
返回的应该是1,按照你的代码,返回的是4了
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 06:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表