近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

twitter面经

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

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

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

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

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


为电面攒RP~
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

评分

2

查看全部评分

ohmystill 发表于 2014-3-26 06:00:30 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这是 online assessment 不?
回复 支持 反对

使用道具 举报

exuberance 发表于 2014-3-26 06:08:54 | 显示全部楼层
关注一亩三分地微博:
Warald
祝贺楼主,祝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
. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| zxzczvb 发表于 2014-3-26 11:42:50 | 显示全部楼层
exuberance 发表于 2014-3-26 06:08 . from: 1point3acres.com/bbs
祝贺楼主,祝onsite顺利。-google 1point3acres
第二题关于 set 的定义能再解释一下吗,没有看明白。 A[A] 是指什么呢
. 1point 3acres 璁哄潧
并查集可以做到O(n). Waral 鍗氬鏈夋洿澶氭枃绔,
public class UnionFind {
        int[] id; // identify the group that each component belongs to
        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 1point 3acres bbs
       
        public int find (int c){
                while(c != id[c]){
                        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;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        . more info on 1point3acres.com
        public void Union (int p, int q){
                int rootp = find(p);
                int rootq = find(q);
               
                if(rootp == rootq) return;
                . from: 1point3acres.com/bbs
                // merge p to q, use q as parent
                if( size[rootp] < size[rootq]){
                        id[rootp] = rootq;
                        size[rootq] += size[rootp];
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                else{
                        id[rootq] = rootp;. more info on 1point3acres.com
                        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: 1point3acres.com/bbs
  2.         int[] id; // identify the group that each component belongs to
  3.         int[] size; // identify the size of each group. 1point3acres.com/bbs
  4. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  5.         public UnionFind (int N){
  6.                 id = new int[N];
  7.                 size = new int[N];
  8.                
  9.                 for(int i =0 ; i<N; i++){-google 1point3acres
  10.                         size[i] = 1;
  11.                         id[i] = i;
  12.                 }
  13.         }. 1point3acres.com/bbs
  14.         // find the group ID that the given component belongs to, the root will have the parent id points to itself
  15.         public int find (int c){
  16.                 while(c != id[c]){
  17.                         id[c] = id[id[c]];. visit 1point3acres.com for more.
  18.                         c = id[c]; // compress path
  19.                 }
  20.                 return c;
  21.         }
  22.         public void Union (int p, int q){
  23.                 int rootp = find(p);
  24.                 int rootq = find(q);
  25.                 if(rootp == rootq) return;
  26.                 // merge p to q, use q as parent
  27.                 if( size[rootp] < size[rootq]){
  28.                         id[rootp] = rootq;
  29.                         size[rootq] += size[rootp];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30.                 }
  31.                 else{
  32.                         id[rootq] = rootp;
  33.                         size[rootp] += size[rootq];
  34.                 }
    . From 1point 3acres bbs
  35.         }
  36. }
复制代码
最后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
-google 1point3acres最后iterative size[0]~size[A.length-1] return 最大值,复杂度O(n)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
嗯,谢谢楼主
回复 支持 反对

使用道具 举报

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

使用道具 举报

pyemma 发表于 2014-4-1 14:28:32 | 显示全部楼层
exuberance 发表于 2014-3-26 06:08
祝贺楼主,祝onsite顺利。
第二题关于 set 的定义能再解释一下吗,没有看明白。 A[A] 是指什么呢
-google 1point3acres
感觉这个和并查集的实现方式是一样的,并查集中之后根是指向自己的
回复 支持 反对

使用道具 举报

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是数组长度?

哈哈,谢谢LZ,刚过了online test,下周一准备电面~
回复 支持 反对

使用道具 举报

shire1989 发表于 2014-5-20 09:00:15 | 显示全部楼层
zxzczvb 发表于 2014-3-26 16:22
最后iterative size[0]~size[A.length-1] return 最大值,复杂度O(n)
. 鍥磋鎴戜滑@1point 3 acres
没看懂楼主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和这个题目一样吗
. From 1point 3acres bbs
能把题目发一下吗
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-26 06:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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