一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 4888|回复: 26
收起左侧

Snapchat电面面经

[复制链接] |试试Instant~ |关注本帖
u-r-the-one 发表于 2016-4-15 06:00:27 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
给一个int的matrix,里面只有0和1,matrix[i][j]表示i和j是朋友,如果是0表示两人不是朋友,是朋友的分成一个组,问能分几组。比如1和2是朋友,3和他们都不是朋友,那么就是2组,return 2就可以。自己写test自己测,面试官很niceSnapchat这个公司真的很nice,他家hr很有耐心又好说话,对他家印象很好,希望最后能有机会拿到。

大家加油!
. 鍥磋鎴戜滑@1point 3 acres

评分

1

查看全部评分

ninacc 发表于 2016-4-21 09:27:38 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
能用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()){. From 1point 3acres bbs
  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.         }
    . 1point 3acres 璁哄潧
  16.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-20 08:26:51 | 显示全部楼层
关注一亩三分地微博:
Warald
wangmengcathy 发表于 2016-4-19 18:27
求问楼主这题和number of islands的区别?

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

使用道具 举报

motn 发表于 2016-4-18 15:09:07 | 显示全部楼层
        自己写了一个,不知道对不对

        // 给一个int的matrix,里面只有0和1,matrix[i][j]表示i和j是朋友,
. 1point3acres.com/bbs        // 如果是0表示两人不是朋友,是朋友的分成一个组,问能分几组。比如1和2是朋友,
        // 3和他们都不是朋友,那么就是2组,return 2就可以。
        // 思路:只要关注三角形就行,如果1和2认识,1和3认识,2和3不认识,也算一个组
        public static int getGroups(int[][] matrix) {
                if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
                        return 0;
                int n = matrix.length;. 1point3acres.com/bbs
                int[] root = new int[n];
                int count = 0;
                for(int i = 0; i < n; i++) {. 1point3acres.com/bbs
                        if(root[i] == 0)
                                root[i] = ++count;
                        for(int j = i + 1; j < n; j++) {
                                if(matrix[i][j] == 1) {
                                        root[j] = root[i];
                                }
                        }
                }
                return count;
        }
回复 支持 1 反对 0

使用道具 举报

BostonYang 发表于 2016-4-15 06:16:37 | 显示全部楼层
如果3和1是朋友,和2不是朋友,该怎么分组呢
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-15 06:19:46 | 显示全部楼层
BostonYang 发表于 2016-4-14 17:16
如果3和1是朋友,和2不是朋友,该怎么分组呢

你是说1和3是朋友 1和2是朋友 2和3不是朋友吗?如果这样的话 他们三个都在一组
回复 支持 反对

使用道具 举报

BostonYang 发表于 2016-4-15 06:46:16 | 显示全部楼层
u-r-the-one 发表于 2016-4-15 06:19
你是说1和3是朋友 1和2是朋友 2和3不是朋友吗?如果这样的话 他们三个都在一组
. visit 1point3acres.com for more.
懂了,楼主什么思路啊,union find么。。。面完多久了给了onsite
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-15 06:54:42 | 显示全部楼层
BostonYang 发表于 2016-4-14 17:46
懂了,楼主什么思路啊,union find么。。。面完多久了给了onsite

对 我用的union find 当时没多想还有什么别的解法 面完2天给的消息
回复 支持 反对

使用道具 举报

BostonYang 发表于 2016-4-15 07:03:39 | 显示全部楼层
u-r-the-one 发表于 2016-4-15 06:54
对 我用的union find 当时没多想还有什么别的解法 面完2天给的消息

楼主加油啊,我明天面,等你好消息
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-15 07:22:28 | 显示全部楼层
BostonYang 发表于 2016-4-14 18:03
楼主加油啊,我明天面,等你好消息
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你也加油啊 我之前也是周五面的 遇上国人大哥
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-4-15 13:22:30 | 显示全部楼层
u-r-the-one 发表于 2016-4-15 06:54
对 我用的union find 当时没多想还有什么别的解法 面完2天给的消息

通过bfs/dfs是不是也能做出来? 参考这道题https://leetcode.com/problems/number-of-islands/
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-20 07:27:50 | 显示全部楼层
求问楼主这题和number of islands的区别?
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-20 08:31:01 | 显示全部楼层
谎言之躯 发表于 2016-4-15 00:22. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
通过bfs/dfs是不是也能做出来? 参考这道题https://leetcode.com/problems/number-of-islands/

比如这种matrix. 1point 3acres 璁哄潧
[[1, 0, 1],
[0, 1, 0],
[1, 0, 1]].鏈枃鍘熷垱鑷1point3acres璁哄潧
这样我觉得用BFS应该就不行吧
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-20 10:14:44 | 显示全部楼层
u-r-the-one 发表于 2016-4-20 08:26. From 1point 3acres bbs
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;. visit 1point3acres.com for more.
  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;.1point3acres缃
  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.         }.1point3acres缃
  37.        
  38.         public boolean union(int p, int q) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  39.                 p = find(p);
  40.                 q = find(q);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  41.                 if(p == q) return false;.1point3acres缃
  42.                 id[p] = q;
  43.                 count--;
  44.                 return true;
  45.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  46. }
复制代码
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-4-21 09:25:31 | 显示全部楼层
这题BFS,DFS都可以做,和number of Island 1的区别在于,比如对于friend i, 不是对上下左右四个点做进一步的搜索,而是对i的所在的那一行进行搜索。当然,要加visited set进行判断已经搜过的friend 例如dfs:. more info on 1point3acres.com

  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)){-google 1point3acres
  6.                 dfs(matrix,visited,i);
  7.             }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.         }
  9.     }
复制代码
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-21 09:32:25 | 显示全部楼层
u-r-the-one 发表于 2016-4-20 08:31
. 鍥磋鎴戜滑@1point 3 acres比如这种matrix. 1point 3acres 璁哄潧
[[1, 0, 1],
[0, 1, 0],

把[n][n]忽略了就ok了....
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-5-6 12:21:25 | 显示全部楼层
楼主您好,我是昨天国人电面string compare,但目前还没有收到消息,最后有小bug没跳出来。不知一般要等多久有下一步消息。
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-5-6 12:23:54 | 显示全部楼层
kemeng1314 发表于 2016-5-5 23:21. from: 1point3acres.com/bbs
楼主您好,我是昨天国人电面string compare,但目前还没有收到消息,最后有小bug没跳出来。不知一般要等多 ...

我是周五面的 周一给的onsite消息
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-5-6 12:25:47 | 显示全部楼层
u-r-the-one 发表于 2016-5-6 12:23
我是周五面的 周一给的onsite消息

有bug的话就很难有next step了吧,但思路说的特别多。不知道会不会给个加面的机会。
回复 支持 反对

使用道具 举报

 楼主| u-r-the-one 发表于 2016-5-6 12:38:16 | 显示全部楼层
kemeng1314 发表于 2016-5-5 23:25
有bug的话就很难有next step了吧,但思路说的特别多。不知道会不会给个加面的机会。

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-4-24 16:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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