一亩三分地论坛

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

TwoSigma 最新 OA

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

2016(4-6月) 码农类 硕士 全职@TwoSigma - 猎头 - 技术电面 |Other在职跳槽

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

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

x
还是friendcircle 和 longestChain这两道题,不过friendCircle 略微变化,变成了connectedComponent. 如:

输入:
1100. From 1point 3acres bbs
1110
0110.1point3acres缃
0001
输出:.1point3acres缃
2

输入:
1000
0100. 鍥磋鎴戜滑@1point 3 acres
0010
0001
输出:
4
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

只是,只是,我程序friendCircle只过了三个test case,其他的说结果不对,输入输出完全看不见; longestChain 过了一半,另一半说segmentation fault. 程序如下,请大神指教。
 楼主| hackintoast 发表于 2016-5-4 11:16:03 | 显示全部楼层
friendcircle 的程序, 只过了三个test case,其他的说结果不对,输入输出完全看不见. 请大家给看看为什么

//breath first search

int bfs( vector < string > &zombies ). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
{
    vector<bool> visited (zombies.size(), false);
    queue<int> q;   
    q.push(0);
    visited[0] = true;
    int clusterNumber = 0;
   
    while(!q.empty()){
        int qfront = q.front();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        q.pop();. Waral 鍗氬鏈夋洿澶氭枃绔,
        
. From 1point 3acres bbs        
        int right = qfront + 1;
        int down = qfront + 1;
        . 鍥磋鎴戜滑@1point 3 acres
        if( right < zombies.size() )
        {. 鍥磋鎴戜滑@1point 3 acres
            if(zombies[qfront][right] == '1' && !visited[right] )
            {
                q.push(right);. visit 1point3acres.com for more.
                visited[right] = true;
            }
        }
               
        if( q.empty() ){
            ++clusterNumber;. more info on 1point3acres.com
            
            for( int i = 1; i < zombies.size(); ++i ){
            if(!visited[i]){
                q.push(i);
                visited[i] = true;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                break;
                }                           
            }
        }       . 1point3acres.com/bbs
        
    }
   
    return clusterNumber;
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
int zombieCluster(vector < string > zombies) {. more info on 1point3acres.com
.鐣欏璁哄潧-涓浜-涓夊垎鍦
    if( zombies.empty() )
        return 0;
   
    int clusterNumber = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   
    clusterNumber = bfs(zombies); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
   
    return clusterNumber;
}
   
回复 支持 反对

使用道具 举报

 楼主| hackintoast 发表于 2016-5-4 11:17:07 | 显示全部楼层
longestChain 过了一半test case,另一半说segmentation fault. 程序如下,请大神指教。
. 1point3acres.com/bbs
int calcLength(string &word, unordered_map<string, int> &hashmap, set<string> &dict){
   
    if( !word.size() || word.size() == 1)
        return 0;
    -google 1point3acres
    int result = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   
    for( int i = 0; i < word.size(); ++i){
        string newSubStr;// = word.erase(i,1);
        
        //create substring. 1point3acres.com/bbs
        if( i == 0 ){
            newSubStr = word.substr(1);
        }
        else if( i == word.size() - 1){
            newSubStr = word.substr(0, i);
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
        else{
            newSubStr= word.substr(0,i) + word.substr(i+1);
        }        . Waral 鍗氬鏈夋洿澶氭枃绔,
        
        
        if( dict.find(newSubStr) != dict.end() ){//word is in the dictionary
            if( hashmap[newSubStr] != 0 ){ //hasmap has the Key/Value pair
                result = std::max( result, hashmap[newSubStr] );.鐣欏璁哄潧-涓浜-涓夊垎鍦
            }
            else{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                result = std::max( result,  calcLength(word, hashmap, dict) + 1 );
            }                 
        }  
            
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    return result;
}
int longestChain(vector < string > words) {

    if(words.empty())
        return 0;
   
    unordered_map<string, int> hashmap;
    set<string> dict;
   
    int wordsNum = words.size();
    . 鍥磋鎴戜滑@1point 3 acres
    for(int i = 0; i < wordsNum; ++i){
        dict.insert(words[i]);
    }
   
    int longestChain = 0;. From 1point 3acres bbs
   
. 鍥磋鎴戜滑@1point 3 acres    for(int i = 0; i < wordsNum; ++i){
        int length = calcLength(words[i], hashmap, dict) + 1;
. 鍥磋鎴戜滑@1point 3 acres        hashmap[ words[i] ] = length;
        longestChain = std::max(longestChain, length);
    }   
   
    return longestChain;
}
回复 支持 反对

使用道具 举报

 楼主| hackintoast 发表于 2016-5-4 11:17:57 | 显示全部楼层
friendCircle只过了三个test case,其他的说结果不对,输入输出完全看不见;程序如下,请大神指教

//breath first search
-google 1point3acres
int bfs( vector < string > &zombies )
{
    vector<bool> visited (zombies.size(), false);
    queue<int> q;   
    q.push(0);
    visited[0] = true;
    int clusterNumber = 0;
   
-google 1point3acres    while(!q.empty()){
        int qfront = q.front();
        q.pop();
        
        
        int right = qfront + 1;
        int down = qfront + 1;
        
        if( right < zombies.size() )
        {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            if(zombies[qfront][right] == '1' && !visited[right] )
            {
                q.push(right);
                visited[right] = true;
            }. visit 1point3acres.com for more.
        }
               
        if( q.empty() ){
            ++clusterNumber;
            
            for( int i = 1; i < zombies.size(); ++i ){
            if(!visited[i]){
                q.push(i);
                visited[i] = true;
                break;
                }                           
            }
        }      
        
    }
    . more info on 1point3acres.com
    return clusterNumber;
}

int zombieCluster(vector < string > zombies) {

    if( zombies.empty() )
        return 0;
   
    int clusterNumber = 0;
   
    clusterNumber = bfs(zombies);
   
    return clusterNumber;
}
回复 支持 反对

使用道具 举报

 楼主| hackintoast 发表于 2016-5-4 11:18:56 | 显示全部楼层
friendCircle只过了三个test case,其他的说结果不对,输入输出完全看不见; 程序如下,请大神指教。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
//breath first search

int bfs( vector < string > &zombies )
-google 1point3acres{
    vector<bool> visited (zombies.size(), false);
    queue<int> q;   
    q.push(0);
    visited[0] = true;
    int clusterNumber = 0;-google 1point3acres
    -google 1point3acres
    while(!q.empty()){
        int qfront = q.front();
        q.pop();. Waral 鍗氬鏈夋洿澶氭枃绔,
        
        
        int right = qfront + 1;
        int down = qfront + 1;. 1point3acres.com/bbs
        
        if( right < zombies.size() )
-google 1point3acres        {
            if(zombies[qfront][right] == '1' && !visited[right] )
            {. From 1point 3acres bbs
                q.push(right);
                visited[right] = true;
. 鍥磋鎴戜滑@1point 3 acres            }
        }
               
        if( q.empty() ){
            ++clusterNumber;
            
            for( int i = 1; i < zombies.size(); ++i ){
            if(!visited[i]){
                q.push(i);
                visited[i] = true;
                break;
                }                           
            }
        }      
        
    }
    -google 1point3acres
    return clusterNumber;
}

int zombieCluster(vector < string > zombies) {

    if( zombies.empty() )
        return 0;. visit 1point3acres.com for more.
   
    int clusterNumber = 0;
   
    clusterNumber = bfs(zombies);
   
    return clusterNumber;
}
回复 支持 反对

使用道具 举报

jamesyin 发表于 2016-5-4 11:41:08 | 显示全部楼层
请问楼主是在哪里投的职位啊,我感觉官网上投没有回应啊。
回复 支持 反对

使用道具 举报

 楼主| hackintoast 发表于 2016-5-5 00:02:21 | 显示全部楼层
jamesyin 发表于 2016-5-4 11:41
请问楼主是在哪里投的职位啊,我感觉官网上投没有回应啊。

我是猎头推荐的。
回复 支持 反对

使用道具 举报

mallow123 发表于 2016-5-9 11:23:26 | 显示全部楼层
第一题难道不是leetcode上面那个数island一样?
回复 支持 反对

使用道具 举报

atlas1017 发表于 2016-8-25 02:03:20 | 显示全部楼层
mallow123 发表于 2016-5-9 11:23. visit 1point3acres.com for more.
第一题难道不是leetcode上面那个数island一样?

并不是~
回复 支持 反对

使用道具 举报

Lilian1109 发表于 2016-8-26 23:25:24 | 显示全部楼层
hackintoast 发表于 2016-5-4 11:17
longestChain 过了一半test case,另一半说segmentation fault. 程序如下,请大神指教。

int calcLength ...
  1. if( dict.find(newSubStr) != dict.end() ){//word is in the dictionary. more info on 1point3acres.com
  2.             if( hashmap[newSubStr] != 0 ){ //hasmap has the Key/Value pair
  3.                 result = std::max( result, hashmap[newSubStr] );
  4. }else{
  5.                 result = std::max( result,  calcLength(word, hashmap, dict) + 1 );
  6.             }                 . 1point3acres.com/bbs
  7.         }  
复制代码
你这段有点令人迷惑, 不应该是 result = max(result, 1+ hashmap[newSubStr]) ?
and also:
else{ result = max(result, calcLength(newSubStr, hashmap, dict) + 1)?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

Lilian1109 发表于 2016-8-27 01:33:39 | 显示全部楼层
friend circle 应该也是union find吧, similar to Number of Islands II
回复 支持 反对

使用道具 举报

woliside 发表于 2016-8-30 07:38:39 | 显示全部楼层
刚做了OA,longestChain我先用了论坛上大家讨论的方法,后面5个cases全fail...后来自己写了个DP,全过了
回复 支持 反对

使用道具 举报

TianlYY 发表于 2016-10-4 01:18:58 | 显示全部楼层
woliside 发表于 2016-8-30 07:38
刚做了OA,longestChain我先用了论坛上大家讨论的方法,后面5个cases全fail...后来自己写了个DP,全过了
.1point3acres缃
请问dp是怎样的思路呢
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-14 06:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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