一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 3049|回复: 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很有耐心又好说话,对他家印象很好,希望最后能有机会拿到。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
大家加油!

评分

1

查看全部评分

ninacc 发表于 2016-4-21 09:27:38 | 显示全部楼层
能用DFS, BFS就也是可以的。
  1.     public void bfs(int[][] matrix, HashSet<Integer> visisted, int k){
  2.         visited.add(k);
  3.         Queue<Integer> q = new LinkedList<>();. 1point 3acres 璁哄潧
  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)){. 1point 3acres 璁哄潧
  11.                     q.offer(i);
  12.                     visited.add(i);
  13.                 }
  14.             }
  15.         }
  16.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

 楼主| u-r-the-one 发表于 2016-4-20 08:26:51 | 显示全部楼层
wangmengcathy 发表于 2016-4-19 18:27. 鍥磋鎴戜滑@1point 3 acres
求问楼主这题和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是朋友,
        // 如果是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;. 1point 3acres 璁哄潧
                for(int i = 0; i < n; i++) {
                        if(root[i] == 0)
                                root[i] = ++count;
                        for(int j = i + 1; j < n; j++) {
. more info on 1point3acres.com                                if(matrix[i][j] == 1) {
                                        root[j] = root[i];
                                }
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
                return count;
        }
回复 支持 1 反对 0

使用道具 举报

BostonYang 发表于 2016-4-15 06:16:37 | 显示全部楼层
如果3和1是朋友,和2不是朋友,该怎么分组呢
回复 支持 反对

使用道具 举报

 楼主| 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不是朋友吗?如果这样的话 他们三个都在一组

懂了,楼主什么思路啊,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. 1point 3acres 璁哄潧
楼主加油啊,我明天面,等你好消息

你也加油啊 我之前也是周五面的 遇上国人大哥
回复 支持 反对

使用道具 举报

谎言之躯 发表于 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
[[1, 0, 1],
[0, 1, 0],
[1, 0, 1]]
这样我觉得用BFS应该就不行吧
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-20 10:14:44 | 显示全部楼层
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));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5.         }
  6.        
  7.         public static int groupFriends(int[][] matrix) {
  8.                 UnionFind uf = new UnionFind(matrix);. visit 1point3acres.com for more.
  9.                 int m = matrix.length;
  10.                 int n = matrix[0].length;. visit 1point3acres.com for more.
  11.                 for(int i = 0; i < m; i++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  12.                         for(int j = 0; j < n; j++) {. from: 1point3acres.com/bbs
  13.                                 if(matrix[i][j] == 1) {
  14.                                         uf.union(i, j);
  15.                                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.                         }
  17.                 }
  18.                 return uf.count;
  19.         }
  20. }

  21. class UnionFind {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.         public int count = 0;
  23.         private int[] id = null;
  24.         public UnionFind(int[][] matrix) {
  25.                 count = matrix.length;
  26.                 id = new int[count];
  27.                 for(int i = 0; i < id.length; i++) id[i] = i;
  28.         }
  29.        
  30.         public int find(int p) {
  31.                 while(p != id[p]) {
  32.                         p = id[p];
  33.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.                 return p;
  35.         }
  36.        
  37.         public boolean union(int p, int q) {
    . From 1point 3acres bbs
  38.                 p = find(p);. Waral 鍗氬鏈夋洿澶氭枃绔,
  39.                 q = find(q);
  40.                 if(p == q) return false;
  41.                 id[p] = q;
  42.                 count--;
  43.                 return true;
  44.         }
  45. }
复制代码
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-4-21 09:25:31 | 显示全部楼层
这题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.     }
复制代码
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-21 09:32:25 | 显示全部楼层
u-r-the-one 发表于 2016-4-20 08:31
比如这种matrix
[[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
楼主您好,我是昨天国人电面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了吧,但思路说的特别多。不知道会不会给个加面的机会。
. more info on 1point3acres.com
这也不好说 我有同学就是被加面了 他们应该还是看中你思路怎么样 他给你提示了的话看你反应快不快 祝你好运!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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