一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1462|回复: 20
收起左侧

twitter面经

[复制链接] |试试Instant~ |关注本帖
zxzczvb 发表于 2014-3-26 05:24:13 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@twitter - 内推 - 在线笔试 |Pass

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

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

x
游客,本帖隐藏的内容需要积分高于 50 才可浏览,您当前积分为 0。 查看如何攒积分


为电面攒RP~


补充内容 (2014-3-26 05:28):
第二个例子有点问题,应该返回2.

评分

2

查看全部评分

ohmystill 发表于 2014-3-26 06:00:30 | 显示全部楼层
这是 online assessment 不?
回复 支持 反对

使用道具 举报

exuberance 发表于 2014-3-26 06:08:54 | 显示全部楼层
祝贺楼主,祝onsite顺利。
第二题关于 set 的定义能再解释一下吗,没有看明白。 A[A] 是指什么呢 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2014-3-26 07:49):
那个这个和first missing value很像,是O(n^2) 解出来的吗,请教有没有比暴力更好的方法
回复 支持 反对

使用道具 举报

blactangeri 发表于 2014-3-26 07:05:20 | 显示全部楼层
thanks for sharing

回复 支持 反对

使用道具 举报

marstorm08 发表于 2014-3-26 07:38:03 | 显示全部楼层
LZ投的是什么职位呢? 我投的是Entry-level都被简历拒了。。太忧桑了
回复 支持 反对

使用道具 举报

 楼主| zxzczvb 发表于 2014-3-26 11:42:50 | 显示全部楼层

并查集可以做到O(n). more info on 1point3acres.com
public class UnionFind {
        int[] id; // identify the group that each component belongs to
-google 1point3acres        int[] size; // identify the size of each group
       
        public UnionFind (int N){
                id = new int[N];.鏈枃鍘熷垱鑷1point3acres璁哄潧
                size = new int[N];
               
                for(int i =0 ; i<N; i++){
                        size = 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        id = i;. from: 1point3acres.com/bbs
                }
        }
       
        public int find (int c){. 鍥磋鎴戜滑@1point 3 acres
                while(c != id[c]){. 1point 3acres 璁哄潧
                        id[c] = id[id[c]]; // compress the path, make each component that located to the path to root same ID
                        c = id[c];
                }
                return c;
        }
       
        public void Union (int p, int q){
                int rootp = find(p);
                int rootq = find(q);
               
                if(rootp == rootq) return;
               
                // merge p to q, use q as parent
                if( size[rootp] < size[rootq]){
                        id[rootp] = rootq;. more info on 1point3acres.com
                        size[rootq] += size[rootp];. visit 1point3acres.com for more.
                }
                else{
                        id[rootq] = rootp;
                        size[rootp] += size[rootq];
                }
        }
}

然后iterate size[1~i]找到max的数 return即可
回复 支持 反对

使用道具 举报

 楼主| zxzczvb 发表于 2014-3-26 16:22:54 | 显示全部楼层
exuberance 发表于 2014-3-26 06:08
祝贺楼主,祝onsite顺利。
第二题关于 set 的定义能再解释一下吗,没有看明白。 A[A] 是指什么呢
  1. public class UnionFind {. From 1point 3acres bbs
  2.         int[] id; // identify the group that each component belongs to
  3.         int[] size; // identify the size of each group

  4.         public UnionFind (int N){. visit 1point3acres.com for more.
  5.                 id = new int[N];
  6.                 size = new int[N];
  7.                
  8.                 for(int i =0 ; i<N; i++){-google 1point3acres
  9.                         size[i] = 1;
  10.                         id[i] = i;
  11.                 }.1point3acres缃
  12.         }
  13.         // find the group ID that the given component belongs to, the root will have the parent id points to itself
  14.         public int find (int c){
  15.                 while(c != id[c]){. visit 1point3acres.com for more.
  16.                         id[c] = id[id[c]];
  17.                         c = id[c]; // compress path
  18.                 }
  19.                 return c;
  20.         }
  21.         public void Union (int p, int q){
  22.                 int rootp = find(p);
  23.                 int rootq = find(q);
  24.                 if(rootp == rootq) return;
  25.                 // merge p to q, use q as parent
  26.                 if( size[rootp] < size[rootq]){. From 1point 3acres bbs
  27.                         id[rootp] = rootq;
  28.                         size[rootq] += size[rootp];
  29.                 }
  30.                 else{
  31.                         id[rootq] = rootp;
  32.                         size[rootp] += size[rootq];
  33.                 }
  34.         }
  35. }
复制代码
最后iterative size[0]~size[A.length-1] return 最大值,复杂度O(n)
回复 支持 反对

使用道具 举报

ssgjs 发表于 2014-3-26 17:20:00 | 显示全部楼层

祝贺楼主,祝onsite顺利。
回复 支持 反对

使用道具 举报

exuberance 发表于 2014-3-26 23:06:30 | 显示全部楼层
zxzczvb 发表于 2014-3-26 16:22
最后iterative size[0]~size[A.length-1] return 最大值,复杂度O(n)

嗯,谢谢楼主
回复 支持 反对

使用道具 举报

呵呵君 发表于 2014-4-1 12:23:53 | 显示全部楼层
学长onsite加油哈!
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-4-1 14:28:32 | 显示全部楼层
exuberance 发表于 2014-3-26 06:08
祝贺楼主,祝onsite顺利。. from: 1point3acres.com/bbs
第二题关于 set 的定义能再解释一下吗,没有看明白。 A[A] 是指什么呢

感觉这个和并查集的实现方式是一样的,并查集中之后根是指向自己的
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-4-1 14:29:38 | 显示全部楼层
zxzczvb 发表于 2014-3-26 16:22
最后iterative size[0]~size[A.length-1] return 最大值,复杂度O(n)

这个看上去好像普利斯顿的算法里面的Week1的实现
回复 支持 反对

使用道具 举报

joytostuffratio 发表于 2014-4-6 12:34:29 | 显示全部楼层
赞LZ!  请问第二题数组中的值是否限定在 [0, n-1] 内, n是数组长度?
回复 支持 反对

使用道具 举报

joytostuffratio 发表于 2014-4-13 02:59:57 | 显示全部楼层
joytostuffratio 发表于 2014-4-6 12:34
赞LZ!  请问第二题数组中的值是否限定在 [0, n-1] 内, n是数组长度?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
哈哈,谢谢LZ,刚过了online test,下周一准备电面~
回复 支持 反对

使用道具 举报

shire1989 发表于 2014-5-20 09:00:15 | 显示全部楼层
zxzczvb 发表于 2014-3-26 16:22. from: 1point3acres.com/bbs
最后iterative size[0]~size[A.length-1] return 最大值,复杂度O(n)

没看懂楼主code。从哪里传入这个array?
回复 支持 反对

使用道具 举报

shire1989 发表于 2014-5-20 09:42:34 | 显示全部楼层
zxzczvb 发表于 2014-3-26 16:22 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最后iterative size[0]~size[A.length-1] return 最大值,复杂度O(n)

看了princeton那个解法,这个算法是N+N*lgM复杂度,不是N啊
回复 支持 反对

使用道具 举报

shire1989 发表于 2014-5-20 10:03:26 | 显示全部楼层
joytostuffratio 发表于 2014-4-6 12:34
赞LZ!  请问第二题数组中的值是否限定在 [0, n-1] 内, n是数组长度?

你做的online test和这个题目一样吗
回复 支持 反对

使用道具 举报

sevenfrost 发表于 2014-9-28 22:44:38 | 显示全部楼层
看不到呀 看不到 桑心
回复 支持 反对

使用道具 举报

sevenfrost 发表于 2014-9-28 22:45:29 | 显示全部楼层
shire1989 发表于 2014-5-20 10:03
你做的online test和这个题目一样吗

能把题目发一下吗
回复 支持 反对

使用道具 举报

davidwh 发表于 2014-10-29 09:27:51 | 显示全部楼层
这么感觉ls把问题想复杂了,直接按照逻辑来可以么?O(n)的时间
public static int largestSet(int[] input){
                if(input == null || input.length == 0){
                        return 0;
                }
               
                int max = 0;
                for(int i = 0; i < input.length; i++){
                        if(input[i] != -1){
                                HashSet<Integer> set = new HashSet<Integer>();
                                int index = i;. From 1point 3acres bbs
                                while(input[index] != -1){
                                        int value = input[index];
                                        set.add(value);
                                        input[index] = -1;
                                        index = value;
                                }
                                max = Math.max(max, set.size());
                        }
                }
                -google 1point3acres
                return max;
        }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 16:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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