一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 42509|回复: 138
收起左侧

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: 就问一堆你对这个感兴趣还是对哪个感兴趣啊..之类的问题。. 鍥磋鎴戜滑@1point 3 acres

oa:
1. friend circle.
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

2. lz 之前在zenefit oa上做过的老题了。. Waral 鍗氬鏈夋洿澶氭枃绔,
longest chain。
游客,本帖隐藏的内容需要积分高于 133 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
. 1point3acres.com/bbs
一轮电面:
快速知识问答:
difference between process and thread and how to communicate
hashtable features and implement

反正基本上在我找着的面经小结里都覆盖了。


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

VI 6,
VV invalid.

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

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

two sigma.pdf

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

two sigma 面经小总结

评分

25

查看全部评分

本帖被以下淘专辑推荐:

magiceaglelikg 发表于 2015-7-19 09:20:12 | 显示全部楼层
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();
        string currNodeFriends = friends[node];
        for (int i = 0; i < currNodeFriends.size(); i++) {
            if (currNodeFriends[i] == 'y' && node != i && visited[i] == false) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                que.push(i);
                visited[i] = true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            }
        }

        if (que.empty()) {
            circles++;
            for (int i = 1; i < friends.size(); i++) {
                if (visited[i] == false) {
                    que.push(i);.1point3acres缃
                    visited[i] = true;
                    break;
                }. from: 1point3acres.com/bbs
            }

        }
    }

    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)).鐣欏璁哄潧-涓浜-涓夊垎鍦
                    uf.union(i,j);
            }
        }
        return uf.getCount();
    }. 鍥磋鎴戜滑@1point 3 acres
   
    static class unionfind{
        int[] ids;
        int count;
        
        public unionfind(int num){
            ids = new int[num];. from: 1point3acres.com/bbs
            for(int i=0;i<num;i++)
                ids[i]=i;
            count = num;
        }
        . 1point3acres.com/bbs
        public int find(int i){.1point3acres缃
            return ids[i];
. Waral 鍗氬鏈夋洿澶氭枃绔,        }
        
        public void union(int i1, int i2){
            int id1 = ids[i1];
            int id2 = ids[i2];. Waral 鍗氬鏈夋洿澶氭枃绔,
            if(id1!=id2){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                for(int i=0;i<ids.length;i++){
                    if(ids[i]==id2)
                        ids[i]=id1;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                count--; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            }.1point3acres缃
        }
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        public boolean isConnected(int i1, int i2){-google 1point3acres
            return find(i1)==find(i2);.1point3acres缃
        }. more info on 1point3acres.com
        
        public int getCount(){
            return count;
        }
    }. more info on 1point3acres.com

评分

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

使用道具 举报

kamibear 发表于 2017-2-14 03:11:05 | 显示全部楼层
calvinq 发表于 2015-5-31 02:18
static int longest_chain(String[] w) {
        HashSet dict = new HashSet();
        

你这代码贴出来就是坑人的
回复 支持 0 反对 1

使用道具 举报

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>();. from: 1point3acres.com/bbs
        
        for (int i = 1; i < w.length; i++) {
            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;

    }


    static int helper(String word, HashSet<String> dict, HashMap<String, Integer> map) {
        . Waral 鍗氬鏈夋洿澶氭枃绔,
        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的不是最好的答案.... From 1point 3acres bbs
回复 支持 1 反对 0

使用道具 举报

hami33 发表于 2015-6-1 10:53:53 | 显示全部楼层
下午刚做了oa,不过没看到你的题。。。
. From 1point 3acres bbs
祝楼主好运
回复 支持 1 反对 0

使用道具 举报

 楼主| calvinq 发表于 2015-6-1 03:30:11 | 显示全部楼层
readman 发表于 2015-5-31 03:39
楼主, two sig 是内推才有电面么?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
不知道哦..我是内推的.然后过了两天就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) {. 1point 3acres 璁哄潧
  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];.1point3acres缃
  7.         for (int i=0; i<lineNum; ++i){
  8.                 array[i] = stdin.nextLine().toCharArray();
  9.         }
  10.         
  11.         // initialize the connected array-google 1point3acres
  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
  17.         // to that with smaller array index
  18.         for (int i=0; i<lineNum; ++i){. from: 1point3acres.com/bbs
  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. }
复制代码
. From 1point 3acres bbs
补充内容 (2015-6-18 21:23):
应该吧connectArr[j] = connectArr;改成connectArr = connectArr[j];.鏈枃鍘熷垱鑷1point3acres璁哄潧

. 鍥磋鎴戜滑@1point 3 acres补充内容 (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;
. 1point 3acres 璁哄潧

public class FriendCircle {
        /*
         * Complete the function below.. From 1point 3acres bbs
         */

            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);   
                        }
                            .鏈枃鍘熷垱鑷1point3acres璁哄潧
                    }
                    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);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                            }else .1point3acres缃
                                list.remove(0);. Waral 鍗氬鏈夋洿澶氭枃绔,
                        }
                        
                        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));
                   
            }
. Waral 鍗氬鏈夋洿澶氭枃绔,

}
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

楼主加油
回复 支持 反对

使用道具 举报

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

主要是我有点笨了...我想应该可以叫他列一个rule 给我的吧..... visit 1point3acres.com for more.
还有一个规则..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
想问问...这是什么算法?

本质是计算联通性。初始化数组每个元素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
是给三个小时的OA么
. 1point 3acres 璁哄潧
好像没这么久...
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-23 06:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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