推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

two sigma 面经oa

[复制链接] |试试Instant~ |关注本帖
cupidjjj 发表于 2016-4-5 06:00:31 | 显示全部楼层 |阅读模式

2016(1-3月) 金工类 博士 全职@TwoSigma - 猎头 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
不久前做了two sigma的online assessment. 一共两道题,三个小时。是在hackerrank上做的。版上以前的题目。
. more info on 1point3acres.com
第一道题是friend circle, 题目在这里(抱歉发不了链接,搜一下hackerrank, friend circle)。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
一共十个例子,但是我有一个例子怎么也过不了。

第二道题是longest chain, 比较简单就全部通过。题目这里有。(仍然发不了链接,搜索yuancrachcode 加 longest chain)

给一个字符串数组, 以任意一个单词开始,删除一个字母 ,如果形成的新字符串还在数组的单词堆里面,则是合法的, chain长度增加1.然后继续往下删,每删一个则长度增加1. 举些例子吧:(a, abcd, bcd, abd, cd, c):abcd 删除一个字母可以变成 bcd , abd, acd,abc。但是只有bcd, acd 可以往下走,所以下面只要考虑这两个。 bcd 可以变成cd 再变成c。 但是abd删除一个单词不能变成数组的一个单词。所以停止。
. From 1point 3acres bbs
在后面的楼层贴代码,希望能帮我看看,为什么这个friend circle 有一个例子过不了。谢谢各位大神。


评分

3

查看全部评分

 楼主| cupidjjj 发表于 2016-4-5 06:02:46 | 显示全部楼层
代码在这里,请指正


int friendcycle_mine() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n;
    cin>>n;
    int i,j;
    char **isfriend=new char*[n];
    for(i=0;i<n;i++){
        isfriend=new char[n];
        for(j=0;j<n;j++){
            cin>>isfriend[j];
        }
    }
    int **cycle=new int*[n];
    for(i=0;i<n;i++){
        cycle=new int(i);
    }
    //    for(i=0;i<n;i++){
    //        cout<<cycle[0]<<endl;
    //    }
    //complexity: n^2
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            //only search for the upper triangular part
            if(isfriend[j]=='Y'){
                //i and j connected
                if(cycle[j][0]>cycle[0]){
                    // j is not connected with 0,1,...,i-1
                    // j does not have its cycle
                    cycle[j]=cycle;
                }else{
                    //j is connected with 0,1,...,i-1
                    //update the index of i's cycle
                    cycle[0]=cycle[j][0];
                }
            }
        }
    }
    //count how many different cycles are there
    set<int> cyl;
    for(i=0;i<n;i++){
        cyl.insert(cycle[0]);
    }
    cout<<cyl.size()<<endl;
    return cyl.size();
}


回复 支持 反对

使用道具 举报

 楼主| cupidjjj 发表于 2016-4-15 04:08:41 | 显示全部楼层
longest chain, 有人问起,我就贴下代码. more info on 1point3acres.com


int longestChain_online(vector<string> &strs){. visit 1point3acres.com for more.
    vector<int> longestChain(strs.size(), 0);
    unordered_map<string, int> dict;
    sort(strs.begin(), strs.end(), [](string a, string b){return a.length()<b.length();});
    for (int i = 0; i<strs.size(); i++) {
        dict[strs[i]] = i;
    }
    for (int i = 0; i<strs.size(); i++) {-google 1point3acres
        if (strs[i].length() <= 1) {
            longestChain[i] = 1;.1point3acres缃
        }else{
            for (int k = 0; k<strs[i].length(); k++) {
                string temp = strs[i];. more info on 1point3acres.com
                temp.erase(k, 1);
                if (dict.find(temp) != dict.end()) {
. From 1point 3acres bbs                    longestChain[i] = max(longestChain[i], longestChain[dict[temp]]+1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
            }. 1point3acres.com/bbs
        }
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    int longest = 0;.1point3acres缃
    for (int i:longestChain) {
        //cout<<i<<endl;
        longest = max(i, longest);
    }
    cout<<longest<<endl;
    return longest;
}
回复 支持 反对

使用道具 举报

boyshone 发表于 2016-4-15 04:11:44 | 显示全部楼层
楼主拿到Onsite了吗?
回复 支持 反对

使用道具 举报

jess88 发表于 2016-4-21 00:34:26 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

qiuqiyuan 发表于 2016-5-8 05:15:12 | 显示全部楼层
我也贴个Python的代码吧: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  1. class Solution:
  2.     def search(self, word, words, ans):
  3.         ans[word] = 1
  4.         for i in range(len(word)):
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.             new_word = word[0:i] + word[i+1:]
  6.             if new_word not in words:
  7.                 continue
  8.             if new_word not in ans:. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.                 #search for new word
  10.                 self.search(new_word, words, ans)
  11.             ans[word] = max(ans[new_word] + 1, ans[word]). more info on 1point3acres.com


  12.     def longestChain(self, words):
  13.         if not words:
  14.             return 0
  15.         words  = set(words)
  16.         ans = {}
  17.         for word in words:
  18.             self.search(word, words, ans)

  19.         return max(ans.values())
复制代码
回复 支持 反对

使用道具 举报

lunyang1985 发表于 2016-5-18 04:21:20 | 显示全部楼层
请问楼主申请的是quant researcher之类的职位还是software developer?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-21 18:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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