一亩三分地论坛

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

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

Two sigma oa+ 一轮游...跪求rp....(附面经小结)

    [复制链接] |试试Instant~ |关注本帖
calvinq 发表于 2015-5-31 02:18:07 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@TwoSigma - 内推 - HR筛选 技术电面 在线笔试 |Otherfresh grad应届毕业生

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

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

x
跪求rp......

2sigma 一直听说这公司bar 挺高的...lz好喜欢这公司的...但是估计现在是onsite都没戏了...不废话了...上面经

hr: 就问一堆你对这个感兴趣还是对哪个感兴趣啊..之类的问题。

oa:
1. friend circle.
给你一个string[] friends。 反应每个人的对应关系。 然后要你返回一个有几个friend circle。
例子:
输入: ynyy
           nyyn
           yyyn. From 1point 3acres bbs
           ynny
n表示不是朋友,y表示是朋友。
这个图表示1跟2 不是朋友,跟3.4是朋友。 2 跟1。4不是朋友,跟3是朋友。 3 跟1,2是朋友,跟4 不是朋友; 4跟1 是朋友,跟2.3 不是朋友。
其实这个string[] 可以理解成一个char 的二维数组,表示各个人的关系。 左上到右下的对角线一定全是y。 然后以这条线为轴,的两个元素相同。.鏈枃鍘熷垱鑷1point3acres璁哄潧
即2是3的朋友,3 也是2的朋友。
. 鍥磋鎴戜滑@1point 3 acres
然后怎么算是一个circle, 朋友的朋友也算一个circle, 假如1 和2 是朋友, 2 和4是朋友, 4和7是朋友,那么1,2,3,7是一个circle。
单独一个人也可以是一个朋友。

例子返回1, 因为全部人都是一个circle 里的。

2. lz 之前在zenefit oa上做过的老题了。
longest chain。. from: 1point3acres.com/bbs
http://www.1point3acres.com/bbs/ ... p;page=1#pid1871241
. visit 1point3acres.com for more.
一轮电面:
快速知识问答:
difference between process and thread and how to communicate
hashtable features and implement

反正基本上在我找着的面经小结里都覆盖了。. 1point 3acres 璁哄潧


coding
判断罗马数字是不是valid的,如果valid 就转化成普通数字。
lz蛋疼了....不动罗马数字的规则,只知道leetcode上有转化成数字的,但是不会判断valid 否。

举个例子吧..鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
VI 6,-google 1point3acres
VV invalid.

面完后,我想到一个好蠢的办法,先roman 转化成int 再int 转回roman,看是不是跟input 一样,一样的话就是valid,返回他的值,不一样就返回invalid。. 鍥磋鎴戜滑@1point 3 acres
求各路大神,給最优解.....怎么判断roman valid 否.....

ps: 附上我准备期间找到的2sigma面经小结。

two sigma.pdf

83.54 KB, 下载次数: 1465, 下载积分: 大米 -1 升

two sigma 面经小总结

评分

21

查看全部评分

本帖被以下淘专辑推荐:

magiceaglelikg 发表于 2015-7-19 09:20:12 | 显示全部楼层
friend circle那题是数connected components吧.1point3acres缃
dfs或者bfs都可以
上个bfs:
int bfs(vector<string> & friends) {
    vector<bool> visited(friends.size(), false);
    queue<int> que;
    que.push(0);
    visited[0] = true;
    int circles = 0;
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    while (!que.empty()) {
        int node = que.front();
        que.pop();
        string currNodeFriends = friends[node];
        for (int i = 0; i < currNodeFriends.size(); i++) {
            if (currNodeFriends[i] == 'y' && node != i && visited[i] == false) {. 1point3acres.com/bbs
                que.push(i);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                visited[i] = true;
            }
        }. more info on 1point3acres.com

        if (que.empty()) {
            circles++;
            for (int i = 1; i < friends.size(); i++) {
                if (visited[i] == false) {
                    que.push(i);
                    visited[i] = true;
                    break;
                }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴            }

        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    return circles; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
回复 支持 5 反对 0

使用道具 举报

seenome 发表于 2016-7-11 08:43:23 | 显示全部楼层
just finished QA today, same problems. to pay back this board, post an unionfind code, passed all tests.

static int friendCircles(String[] friends) {
        if(friends==null||friends.length==0) return 0;
        int n = friends.length;
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        unionfind uf = new unionfind(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(friends[i].charAt(j)=='Y'&&!uf.isConnected(i,j)).1point3acres缃
                    uf.union(i,j);
            }
        }
        return uf.getCount();
    }
   
    static class unionfind{. more info on 1point3acres.com
        int[] ids;
        int count;
        
        public unionfind(int num){. more info on 1point3acres.com
            ids = new int[num];. visit 1point3acres.com for more.
            for(int i=0;i<num;i++)
                ids[i]=i;
            count = num;
        }
        
        public int find(int i){
            return ids[i];
        }
        
        public void union(int i1, int i2){
            int id1 = ids[i1];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            int id2 = ids[i2];
            if(id1!=id2){
                for(int i=0;i<ids.length;i++){
                    if(ids[i]==id2)
                        ids[i]=id1;
                }. 1point 3acres 璁哄潧
                count--;
            }
        }
        
        public boolean isConnected(int i1, int i2){
            return find(i1)==find(i2);
        }
        
        public int getCount(){
            return count;-google 1point3acres
        }
    }

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

 楼主| calvinq 发表于 2015-5-31 02:18:44 | 显示全部楼层
static int longest_chain(String[] w) {
        HashSet<String> dict = new HashSet<String>();
        
. visit 1point3acres.com for more.        // remeber the word and its relative longest chain.
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        
        for (int i = 1; i < w.length; i++) {
            dict.add(w);. from: 1point3acres.com/bbs
        }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷        
        int longest = 0;
        
        for (int i = 1; i < w.length; i++) {
            int len = helper(w, dict, map) + 1;
            map.put(w, len);
            longest = Math.max(longest, len);
            
        }. from: 1point3acres.com/bbs
        
        return longest;
.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }


    static int helper(String word, HashSet<String> dict, HashMap<String, Integer> map) {. 1point 3acres 璁哄潧
        . From 1point 3acres bbs
        for (int i = 0; i < word.length(); i++) {
            StringBuilder s = new StringBuilder(word);
            s = s.deleteCharAt(i);
            String newWord = s.toString();
            if (dict.contains(newWord)) {
                if (map.containsKey(newWord))
                    return map.get(newWord);
                return helper(newWord, dict, map) + 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            }
            
            
        }
        return 0;
    }

补充内容 (2015-6-1 03:45):
感谢10楼同学....-google 1point3acres
用res = max(res,map.get())和res = max(res, helper()+1)代替return, 直接就return了,有可能return的不是最好的答案...
. 鍥磋鎴戜滑@1point 3 acres
回复 支持 1 反对 0

使用道具 举报

yuranrobin 发表于 2016-9-8 11:59:46 | 显示全部楼层
2016/09/06 刚做完OA friends circles和longest chain

. visit 1point3acres.com for more.我的解法:
friends circles用的union find
longest chain先根据string的长度sort,把所有word存到hashset,再从短到长看每个word去掉每一位字母能不能在hashset中找到,如果能,就在去掉后生成的word的count基础上+1,存入hashmap,记录最大的
回复 支持 1 反对 0

使用道具 举报

hami33 发表于 2015-6-1 10:53:53 | 显示全部楼层
下午刚做了oa,不过没看到你的题。。。

祝楼主好运
回复 支持 1 反对 0

使用道具 举报

 楼主| calvinq 发表于 2015-6-1 03:30:11 | 显示全部楼层
readman 发表于 2015-5-31 03:39
楼主, two sig 是内推才有电面么?

不知道哦..我是内推的.然后过了两天就hr 面.然后一个oa..然后电面..... 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 1 反对 0

使用道具 举报

luochenhuan 发表于 2015-6-5 02:45:55 | 显示全部楼层
贴一个friendCirlce solution. 主要用到princeton Alogorithms I week 1的算法(shame on me, 每次只看week 1就弃坑了)

  1. public class friendCircle {
  2.     public static void main(String[] args) {
  3.         // read the char array
  4.         Scanner stdin = new Scanner(System.in);
  5.         int lineNum = Integer.parseInt(stdin.nextLine());
  6.         char[][] array = new char[lineNum][lineNum];
  7.         for (int i=0; i<lineNum; ++i){
  8.                 array[i] = stdin.nextLine().toCharArray();
  9.         }
  10.         . 1point 3acres 璁哄潧
  11.         // initialize the connected array
  12.         int[] connectArr = new int[lineNum];. 1point3acres.com/bbs
  13.         for (int i=0; i<lineNum; ++i)
  14.                 connectArr[i] = i;
  15.         // update connected array, the rule is: if two are friends,
  16.         // then the one with larger index change its array value
  17.         // to that with smaller array index
  18.         for (int i=0; i<lineNum; ++i){
  19.                 for (int j=i+1; j<lineNum; ++j){
  20.                         if (array[i][j] == 'Y')
  21.                                 connectArr[j] = connectArr[i];
  22.                 }
  23.         }
  24.         Set<Integer> uniqueInd = new HashSet<Integer>();
  25.         for (int index : connectArr)
  26.                 uniqueInd.add(index);
  27.         System.out.println(uniqueInd.size());
  28. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.     }
  30. }
复制代码

补充内容 (2015-6-18 21:23):
应该吧connectArr[j] = connectArr;改成connectArr = connectArr[j];

补充内容 (2015-6-18 21:23):.鐣欏璁哄潧-涓浜-涓夊垎鍦
....应该吧connectArr[j] = connectArr;改成connectArr = connectArr[j];

补充内容 (2015-6-18 21:24):
....no idea为什么补充内容显示的不正确...

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-5-31 03:39:41 | 显示全部楼层
楼主, two sig 是内推才有电面么?
回复 支持 1 反对 0

使用道具 举报

 楼主| calvinq 发表于 2015-5-31 02:18:28 | 显示全部楼层
import java.util.ArrayList;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
import java.util.HashMap;
import java.util.HashSet;


public class FriendCircle {
        /*
         * Complete the function below.. visit 1point3acres.com for more.
         */
. visit 1point3acres.com for more.
            static int friendCircles(String[] friends) {. visit 1point3acres.com for more.
                if (null == friends || 0 == friends.length)
                    return 0;
                HashSet<Integer> all = new HashSet<Integer>();
                for (int i = 0; i < friends.length; i++) {
                    all.add(i);
                }
                
                HashMap<Integer, ArrayList<Integer>> connect = new HashMap<Integer, ArrayList<Integer>>();
                
                for (int i = 0; i < friends.length; i++) {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                   
                    for (int j = i + 1; j < friends[i].length(); j++) {
                        if ('Y' == friends[i].charAt(j)) {
                            list.add(j);   
                        }
                            
                    }
                    connect.put(i, list);
                }
                
                ArrayList<HashSet<Integer>> circles = new ArrayList<HashSet<Integer>>();
                for (int i = 0; i < friends.length; i ++) {
                    if (all.contains(i)) {
                        all.remove(i);
                        HashSet<Integer> circle = new HashSet<Integer>();
                        circle.add(i);
                        ArrayList<Integer> list = connect.get(i);
                        while (!list.isEmpty()) {
                            if (all.contains(list.get(0))) {
                                all.remove(list.get(0));
                                list.addAll(connect.get(list.get(0)));
                                circle.add(list.get(0));
                                list.remove(0);-google 1point3acres
                            }else
                                list.remove(0);
                        }
                        
                        circles.add(circle);
                    }
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                
                return circles.size();. more info on 1point3acres.com
             
            }
            
            public static void main(String[] args) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                    FriendCircle sol = new FriendCircle();
                    String[] friends = {"YYY", "YYY", "YYY"};
                    System.out.println(sol.friendCircles(friends));
                   
            }. From 1point 3acres bbs
. 1point3acres.com/bbs

}
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-5-31 02:19:18 | 显示全部楼层
把oa code 贴上吧....大家参考一下吧...test case是都过了
回复 支持 反对

使用道具 举报

enicloom 发表于 2015-5-31 03:24:23 | 显示全部楼层
我觉得罗马数字那道题目有失公平 我们本来就不太熟悉规则啊 其实稍微看看wiki也就明白了 无非就是5开头的不能够连起来 然后其他的数字最多四个连一起
我还是头一次听说还会有公司出关于罗马数字的题目呢

楼主加油
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-6-1 03:29:34 | 显示全部楼层
enicloom 发表于 2015-5-31 03:24
我觉得罗马数字那道题目有失公平 我们本来就不太熟悉规则啊 其实稍微看看wiki也就明白了 无非就是5开头的不 ...

主要是我有点笨了...我想应该可以叫他列一个rule 给我的吧....
还有一个规则..high order go first...感觉.也不太好判断...
回复 支持 反对

使用道具 举报

yangzeyao 发表于 2015-6-1 03:34:55 | 显示全部楼层
多谢楼主的面经,尤其是代码部分!
回复 支持 反对

使用道具 举报

yangzeyao 发表于 2015-6-1 03:39:49 | 显示全部楼层
对了,刚刚想起来。longest chain那道题,感觉helper函数里应该用res = max(res,map.get())和res = max(res, helper()+1)代替return吧。如果直接return的话,选择移除字母的时候,找到第一次移除之后还在字典里的单词就return了,可能不是正确答案,不过test cases好像没有考虑这个问题。
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-6-1 03:44:56 | 显示全部楼层
yangzeyao 发表于 2015-6-1 03:39
对了,刚刚想起来。longest chain那道题,感觉helper函数里应该用res = max(res,map.get())和res = max(res ...

有道理有道理....我误解大家了
回复 支持 反对

使用道具 举报

yangzeyao 发表于 2015-6-1 06:53:37 | 显示全部楼层
calvinq 发表于 2015-6-1 03:44
有道理有道理....我误解大家了
. From 1point 3acres bbs
总之多谢楼主的面经,希望你能拿到onsite!
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-6-5 02:55:09 | 显示全部楼层
luochenhuan 发表于 2015-6-5 02:45
贴一个friendCirlce solution. 主要用到princeton Alogorithms I week 1的算法(shame on me, 每次只看week ...

想问问...这是什么算法?
回复 支持 反对

使用道具 举报

luochenhuan 发表于 2015-6-6 10:32:08 | 显示全部楼层
calvinq 发表于 2015-6-5 02:55
想问问...这是什么算法?

本质是计算联通性。初始化数组每个元素value为index,然后从第一个元素开始两两比较,如果是朋友的话,就把index在后的value更新成index在前的value,最后count数组中unique的元素个数~
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-6-6 12:39:45 | 显示全部楼层
luochenhuan 发表于 2015-6-5 02:45
贴一个friendCirlce solution. 主要用到princeton Alogorithms I week 1的算法(shame on me, 每次只看week ...
. 1point3acres.com/bbs
如果输入是
yny
nyy
yyy. more info on 1point3acres.com
1和3是朋友,2和3是朋友,3和1,2都是朋友
你贴的这个程序输出好像是2,不是1
回复 支持 反对

使用道具 举报

syduan2015 发表于 2015-6-9 09:38:29 | 显示全部楼层
thanks. it's helpful
回复 支持 反对

使用道具 举报

1geu3gh3r4 发表于 2015-6-13 10:53:40 | 显示全部楼层
是给三个小时的OA么
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-6-13 12:56:37 | 显示全部楼层
1geu3gh3r4 发表于 2015-6-13 10:53
是给三个小时的OA么

好像没这么久...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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