一亩三分地论坛

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

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

two sigma 面经oa

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

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

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

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

x
不久前做了two sigma的online assessment. 一共两道题,三个小时。是在hackerrank上做的。版上以前的题目。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第一道题是friend circle, 题目在这里(抱歉发不了链接,搜一下hackerrank, friend circle)。
. visit 1point3acres.com for more.
一共十个例子,但是我有一个例子怎么也过不了。

第二道题是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删除一个单词不能变成数组的一个单词。所以停止。
. visit 1point3acres.com for more.
在后面的楼层贴代码,希望能帮我看看,为什么这个friend circle 有一个例子过不了。谢谢各位大神。-google 1point3acres
. visit 1point3acres.com for more.
. From 1point 3acres bbs

评分

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.comint longestChain_online(vector<string> &strs){
    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++) {. 鍥磋鎴戜滑@1point 3 acres
        if (strs[i].length() <= 1) {
            longestChain[i] = 1;
        }else{
            for (int k = 0; k<strs[i].length(); k++) {
                string temp = strs[i];
                temp.erase(k, 1);
                if (dict.find(temp) != dict.end()) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                    longestChain[i] = max(longestChain[i], longestChain[dict[temp]]+1);-google 1point3acres
                }-google 1point3acres
            }
        }
    }
    int longest = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    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:
  9.                 #search for new word.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.                 self.search(new_word, words, ans)
  11.             ans[word] = max(ans[new_word] + 1, ans[word])


  12.     def longestChain(self, words):
  13.         if not words:
  14.             return 0
  15.         words  = set(words)
  16.         ans = {}. Waral 鍗氬鏈夋洿澶氭枃绔,
  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?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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