May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

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

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

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

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

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

x
跪求rp......

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

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

oa:
1. friend circle.
给你一个string[] friends。 反应每个人的对应关系。 然后要你返回一个有几个friend circle。
例子:
输入: ynyy
           nyyn. Waral 鍗氬鏈夋洿澶氭枃绔,
           yyyn
           ynny
n表示不是朋友,y表示是朋友。
这个图表示1跟2 不是朋友,跟3.4是朋友。 2 跟1。4不是朋友,跟3是朋友。 3 跟1,2是朋友,跟4 不是朋友; 4跟1 是朋友,跟2.3 不是朋友。
其实这个string[] 可以理解成一个char 的二维数组,表示各个人的关系。 左上到右下的对角线一定全是y。 然后以这条线为轴,的两个元素相同。
即2是3的朋友,3 也是2的朋友。
. more info on 1point3acres.com
然后怎么算是一个circle, 朋友的朋友也算一个circle, 假如1 和2 是朋友, 2 和4是朋友, 4和7是朋友,那么1,2,3,7是一个circle。
单独一个人也可以是一个朋友。

例子返回1, 因为全部人都是一个circle 里的。
. From 1point 3acres bbs
2. lz 之前在zenefit oa上做过的老题了。
longest chain。
http://www.1point3acres.com/bbs/ ... p;page=1#pid1871241
. 1point3acres.com/bbs
一轮电面:
快速知识问答:
difference between process and thread and how to communicate
hashtable features and implement. From 1point 3acres bbs
. visit 1point3acres.com for more.
反正基本上在我找着的面经小结里都覆盖了。


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

举个例子吧.

VI 6,
VV invalid.. from: 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
面完后,我想到一个好蠢的办法,先roman 转化成int 再int 转回roman,看是不是跟input 一样,一样的话就是valid,返回他的值,不一样就返回invalid。. 1point 3acres 璁哄潧
求各路大神,給最优解.....怎么判断roman valid 否.....

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

two sigma.pdf

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

two sigma 面经小总结

评分

23

查看全部评分

本帖被以下淘专辑推荐:

magiceaglelikg 发表于 2015-7-19 09:20:12 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
friend circle那题是数connected components吧
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();.鏈枃鍘熷垱鑷1point3acres璁哄潧
        string currNodeFriends = friends[node];
        for (int i = 0; i < currNodeFriends.size(); i++) {
            if (currNodeFriends[i] == 'y' && node != i && visited[i] == false) {
                que.push(i);
. 1point 3acres 璁哄潧                visited[i] = true;. from: 1point3acres.com/bbs
            }
        }

        if (que.empty()) {
            circles++;. 鍥磋鎴戜滑@1point 3 acres
            for (int i = 1; i < friends.size(); i++) {
                if (visited[i] == false) {
                    que.push(i);. From 1point 3acres bbs
                    visited[i] = true;
                    break;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }. from: 1point3acres.com/bbs
            }

        }
    }

    return circles;
}
回复 支持 5 反对 0

使用道具 举报

seenome 发表于 2016-7-11 08:43:23 | 显示全部楼层
关注一亩三分地微博:
Warald
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))
                    uf.union(i,j);
            }
        }
        return uf.getCount();
    }
    . visit 1point3acres.com for more.
    static class unionfind{
        int[] ids;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        int count;
        
        public unionfind(int num){
            ids = new int[num];
            for(int i=0;i<num;i++)
                ids[i]=i;
            count = num;.1point3acres缃
        }.1point3acres缃
        
        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). more info on 1point3acres.com
                        ids[i]=id1;
                }
                count--;
            }
        }
        
        public boolean isConnected(int i1, int i2){
.鏈枃鍘熷垱鑷1point3acres璁哄潧            return find(i1)==find(i2);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }. From 1point 3acres bbs
        . more info on 1point3acres.com
        public int getCount(){
            return count;. 1point 3acres 璁哄潧
        }-google 1point3acres
    }

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

yuranrobin 发表于 2016-9-8 11:59:46 | 显示全部楼层
2016/09/06 刚做完OA friends circles和longest chain
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我的解法:
friends circles用的union find
longest chain先根据string的长度sort,把所有word存到hashset,再从短到长看每个word去掉每一位字母能不能在hashset中找到,如果能,就在去掉后生成的word的count基础上+1,存入hashmap,记录最大的
回复 支持 2 反对 0

使用道具 举报

yuranrobin 发表于 2017-2-16 02:25:05 | 显示全部楼层
kamibear 发表于 2017-2-13 12:13
为什么是从短到厂?

从长到短可能也可以
回复 支持 1 反对 0

使用道具 举报

 楼主| calvinq 发表于 2015-5-31 02:18:44 | 显示全部楼层
static int longest_chain(String[] w) {
        HashSet<String> dict = new HashSet<String>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
        
        // remeber the word and its relative longest chain.
        HashMap<String, Integer> map = new HashMap<String, Integer>();. Waral 鍗氬鏈夋洿澶氭枃绔,
        
        for (int i = 1; i < w.length; i++) {. more info on 1point3acres.com
            dict.add(w);
        }
         鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        int longest = 0;. From 1point 3acres bbs
        .鐣欏璁哄潧-涓浜-涓夊垎鍦
        for (int i = 1; i < w.length; i++) {
            int len = helper(w, dict, map) + 1;
            map.put(w, len);
            longest = Math.max(longest, len);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            
        }
        
        return longest;

    }. more info on 1point3acres.com
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鍥磋鎴戜滑@1point 3 acres
    static int helper(String word, HashSet<String> dict, HashMap<String, Integer> map) {
        
        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)) {. from: 1point3acres.com/bbs
                if (map.containsKey(newWord))
                    return map.get(newWord);
                return helper(newWord, dict, map) + 1;
            }
            
            
        }
        return 0;
    }

补充内容 (2015-6-1 03:45):
感谢10楼同学....
用res = max(res,map.get())和res = max(res, helper()+1)代替return, 直接就return了,有可能return的不是最好的答案...
回复 支持 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 {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         
  11.         // initialize the connected array
  12.         int[] connectArr = new int[lineNum];
  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 .1point3acres缃
  17.         // to that with smaller array index. From 1point 3acres bbs
  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());
    . more info on 1point3acres.com

  28.     }
  29. }
复制代码

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

补充内容 (2015-6-18 21:23):.鏈枃鍘熷垱鑷1point3acres璁哄潧
....应该吧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;.1point3acres缃
import java.util.HashMap;
import java.util.HashSet;


public class FriendCircle {
        /*
         * Complete the function below..鏈枃鍘熷垱鑷1point3acres璁哄潧
         */

            static int friendCircles(String[] friends) {
                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>>();
. visit 1point3acres.com for more.                
                for (int i = 0; i < friends.length; i++) {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                   
                    for (int j = i + 1; j < friends[i].length(); j++) {. visit 1point3acres.com for more.
                        if ('Y' == friends[i].charAt(j)) {
                            list.add(j);    . more info on 1point3acres.com
                        }
                            
                    }
                    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);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        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));. 1point3acres.com/bbs
                                list.addAll(connect.get(list.get(0)));
                                circle.add(list.get(0));
                                list.remove(0);
                            }else
                                list.remove(0);
                        }
                        
                        circles.add(circle);
                    }
                }
                
                return circles.size();
             
            }-google 1point3acres
            
            public static void main(String[] args) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                    FriendCircle sol = new FriendCircle();
                    String[] friends = {"YYY", "YYY", "YYY"};
                    System.out.println(sol.friendCircles(friends));
                   
            }
. 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
有道理有道理....我误解大家了

总之多谢楼主的面经,希望你能拿到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-google 1point3acres
想问问...这是什么算法?

本质是计算联通性。初始化数组每个元素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 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
如果输入是
yny. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
nyy
yyy
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. From 1point 3acres bbs
是给三个小时的OA么

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-22 23:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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