《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 40622|回复: 134
收起左侧

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

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

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

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

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

x
跪求rp......

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

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

oa:
1. friend circle.
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


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

2. lz 之前在zenefit oa上做过的老题了。
longest chain。.1point3acres缃
游客,本帖隐藏的内容需要积分高于 133 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

一轮电面:
快速知识问答:
difference between process and thread and how to communicate
hashtable features and implement

反正基本上在我找着的面经小结里都覆盖了。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


coding.鏈枃鍘熷垱鑷1point3acres璁哄潧
判断罗马数字是不是valid的,如果valid 就转化成普通数字。
lz蛋疼了....不动罗马数字的规则,只知道leetcode上有转化成数字的,但是不会判断valid 否。

举个例子吧.. visit 1point3acres.com for more.

VI 6,
VV invalid.

面完后,我想到一个好蠢的办法,先roman 转化成int 再int 转回roman,看是不是跟input 一样,一样的话就是valid,返回他的值,不一样就返回invalid。
求各路大神,給最优解.....怎么判断roman valid 否...... 1point3acres.com/bbs
. From 1point 3acres bbs
ps: 附上我准备期间找到的2sigma面经小结。

two sigma.pdf

83.54 KB, 阅读权限: 80, 下载次数: 1812, 下载积分: 大米 -1 升

two sigma 面经小总结

评分

25

查看全部评分

本帖被以下淘专辑推荐:

magiceaglelikg 发表于 2015-7-19 09:20:12 | 显示全部楼层
friend circle那题是数connected components吧.鐣欏璁哄潧-涓浜-涓夊垎鍦
dfs或者bfs都可以
上个bfs:-google 1point3acres
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();.鏈枃鍘熷垱鑷1point3acres璁哄潧
        que.pop();
        string currNodeFriends = friends[node];
        for (int i = 0; i < currNodeFriends.size(); i++) {
            if (currNodeFriends[i] == 'y' && node != i && visited[i] == false) {
                que.push(i);
                visited[i] = true;
            }. 1point3acres.com/bbs
        }
-google 1point3acres
        if (que.empty()) {. 鍥磋鎴戜滑@1point 3 acres
            circles++;
            for (int i = 1; i < friends.size(); i++) {
                if (visited[i] == false) {. 1point 3acres 璁哄潧
                    que.push(i);
                    visited[i] = true;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                    break; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                }-google 1point3acres
            }.1point3acres缃

        }
    }

    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..1point3acres缃

static int friendCircles(String[] friends) {
        if(friends==null||friends.length==0) return 0;. visit 1point3acres.com for more.
        int n = friends.length;
        
        unionfind uf = new unionfind(n);. 1point3acres.com/bbs
        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);
            }
        }-google 1point3acres
        return uf.getCount();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }
   
    static class unionfind{.1point3acres缃
        int[] ids;
        int count;
        
        public unionfind(int num){
            ids = new int[num];
            for(int i=0;i<num;i++)
                ids[i]=i;
            count = num;
        }
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        public int find(int i){. more info on 1point3acres.com
            return ids[i];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
. from: 1point3acres.com/bbs         
        public void union(int i1, int i2){
            int id1 = ids[i1];
            int id2 = ids[i2];
            if(id1!=id2){. from: 1point3acres.com/bbs
                for(int i=0;i<ids.length;i++){
                    if(ids[i]==id2)
                        ids[i]=id1;. From 1point 3acres bbs
                }
                count--;. From 1point 3acres bbs
            }
        }
        
        public boolean isConnected(int i1, int i2){. visit 1point3acres.com for more.
            return find(i1)==find(i2);.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
        
        public int getCount(){
            return count;
        }
    }

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

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

我的解法:
friends circles用的union find-google 1point3acres
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>();
        
        // remeber the word and its relative longest chain.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        HashMap<String, Integer> map = new HashMap<String, Integer>();
. 1point3acres.com/bbs        
        for (int i = 1; i < w.length; i++) {
            dict.add(w);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
        
        int longest = 0;
        .鐣欏璁哄潧-涓浜-涓夊垎鍦
        for (int i = 1; i < w.length; i++) {
            int len = helper(w, dict, map) + 1;
            map.put(w, len);. from: 1point3acres.com/bbs
            longest = Math.max(longest, len);
            
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        
        return longest;
. Waral 鍗氬鏈夋洿澶氭枃绔, . Waral 鍗氬鏈夋洿澶氭枃绔,
    }
.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    static int helper(String word, HashSet<String> dict, HashMap<String, Integer> map) {. 1point 3acres 璁哄潧
        .1point3acres缃
        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楼同学....
用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. 1point3acres.com/bbs
楼主, 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. -google 1point3acres
  2. public class friendCircle {
  3.     public static void main(String[] args) {
  4.         // read the char array
  5.         Scanner stdin = new Scanner(System.in);
  6.         int lineNum = Integer.parseInt(stdin.nextLine());
  7.         char[][] array = new char[lineNum][lineNum];
  8.         for (int i=0; i<lineNum; ++i){
  9.                 array[i] = stdin.nextLine().toCharArray();
  10.         }
  11.         
  12.         // initialize the connected array
  13.         int[] connectArr = new int[lineNum];
  14.         for (int i=0; i<lineNum; ++i)
  15.                 connectArr[i] = i;
  16.         // update connected array, the rule is: if two are friends,. 1point 3acres 璁哄潧
  17.         // then the one with larger index change its array value
  18.         // to that with smaller array index
  19.         for (int i=0; i<lineNum; ++i){
  20.                 for (int j=i+1; j<lineNum; ++j){
  21.                         if (array[i][j] == 'Y')
  22.                                 connectArr[j] = connectArr[i];
  23.                 }
  24.         }
  25.         Set<Integer> uniqueInd = new HashSet<Integer>();
  26.         for (int index : connectArr)
  27.                 uniqueInd.add(index);. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.         System.out.println(uniqueInd.size());

  29.     }
  30. }
复制代码
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2015-6-18 21:23):
应该吧connectArr[j] = connectArr;改成connectArr = connectArr[j];. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (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;. From 1point 3acres bbs


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>>();
                
                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)) {. 1point 3acres 璁哄潧
                        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);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                            }else . from: 1point3acres.com/bbs
                                list.remove(0);
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        
                        circles.add(circle);
                    }
                }
                
                return circles.size();
.1point3acres缃             
            }
            
            public static void main(String[] args) {
                    FriendCircle sol = new FriendCircle();
                    String[] friends = {"YYY", "YYY", "YYY"};
                    System.out.println(sol.friendCircles(friends));
                   
            }


}
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

楼主加油
回复 支持 反对

使用道具 举报

 楼主| 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-google 1point3acres
贴一个friendCirlce solution. 主要用到princeton Alogorithms I week 1的算法(shame on me, 每次只看week ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
想问问...这是什么算法?
回复 支持 反对

使用道具 举报

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 ...

如果输入是
yny. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
nyy. 1point3acres.com/bbs
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
是给三个小时的OA么

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-19 13:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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