一亩三分地论坛

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

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

TwoSigma 最新 OA

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

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

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

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

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

输入:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1100
1110
0110-google 1point3acres
0001
输出:
2
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
输入:
1000
0100. 鍥磋鎴戜滑@1point 3 acres
0010. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
0001-google 1point3acres
输出:
4


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

//breath first search

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

int zombieCluster(vector < string > zombies) {

    if( zombies.empty() )
        return 0;
    . 鍥磋鎴戜滑@1point 3 acres
    int clusterNumber = 0;
   
    clusterNumber = bfs(zombies);
   
    return clusterNumber;
}
   
回复 支持 反对

使用道具 举报

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

int calcLength(string &word, unordered_map<string, int> &hashmap, set<string> &dict){
   
    if( !word.size() || word.size() == 1)
        return 0;
   
    int result = 0;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    for( int i = 0; i < word.size(); ++i){
        string newSubStr;// = word.erase(i,1);
        .1point3acres缃
        //create substring
        if( i == 0 ){. 鍥磋鎴戜滑@1point 3 acres
            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);. more info on 1point3acres.com
        }        
        
        . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        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{-google 1point3acres
                result = std::max( result,  calcLength(word, hashmap, dict) + 1 );
            }                 
        }  
            
    }
    return result;
}
int longestChain(vector < string > words) {

    if(words.empty())
        return 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
   
    unordered_map<string, int> hashmap;
    set<string> dict;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    int wordsNum = words.size();
   
    for(int i = 0; i < wordsNum; ++i){
        dict.insert(words[i]);
    }
   
    int longestChain = 0;
   
    for(int i = 0; i < wordsNum; ++i){. from: 1point3acres.com/bbs
        int length = calcLength(words[i], hashmap, dict) + 1;
        hashmap[ words[i] ] = length;
        longestChain = std::max(longestChain, length);. more info on 1point3acres.com
    }   
   
    return longestChain;
}
回复 支持 反对

使用道具 举报

 楼主| hackintoast 发表于 2016-5-4 11:17:57 | 显示全部楼层
friendCircle只过了三个test case,其他的说结果不对,输入输出完全看不见;程序如下,请大神指教
. Waral 鍗氬鏈夋洿澶氭枃绔,
//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();
        
        
        int right = qfront + 1;
        int down = qfront + 1;
        
        if( right < zombies.size() )
. visit 1point3acres.com for more.        {
            if(zombies[qfront][right] == '1' && !visited[right] )-google 1point3acres
            {
                q.push(right);
                visited[right] = true;
            }
        }
                .鏈枃鍘熷垱鑷1point3acres璁哄潧
        if( q.empty() ){. more info on 1point3acres.com
            ++clusterNumber;
            . from: 1point3acres.com/bbs
            for( int i = 1; i < zombies.size(); ++i ){
            if(!visited[i]){. visit 1point3acres.com for more.
                q.push(i);
                visited[i] = true;
-google 1point3acres                break;
                }                            . 鍥磋鎴戜滑@1point 3 acres
            }
        }       . visit 1point3acres.com for more.
        
    }
    . 1point3acres.com/bbs
    return clusterNumber;
}

int zombieCluster(vector < string > zombies) {

    if( zombies.empty() ). 1point3acres.com/bbs
        return 0;
   
    int clusterNumber = 0;. 1point3acres.com/bbs
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
    clusterNumber = bfs(zombies);
   
    return clusterNumber;
}
回复 支持 反对

使用道具 举报

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

//breath first search
. visit 1point3acres.com for more.
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(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        
        
        int right = qfront + 1;
        int down = qfront + 1;
        
.鏈枃鍘熷垱鑷1point3acres璁哄潧        if( right < zombies.size() )
        { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            if(zombies[qfront][right] == '1' && !visited[right] )
            {
                q.push(right);
                visited[right] = true;
            }
        }
               
        if( q.empty() ){
            ++clusterNumber;
            . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            for( int i = 1; i < zombies.size(); ++i ){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            if(!visited[i]){
                q.push(i);
                visited[i] = true;
                break;
                }                           
            }
        }      
        
    }.1point3acres缃
    . from: 1point3acres.com/bbs
    return clusterNumber;. 1point3acres.com/bbs
}
. from: 1point3acres.com/bbs
int zombieCluster(vector < string > zombies) {

    if( zombies.empty() )-google 1point3acres
        return 0;
   
    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
第一题难道不是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
  2.             if( hashmap[newSubStr] != 0 ){ //hasmap has the Key/Value pair
  3.                 result = std::max( result, hashmap[newSubStr] );-google 1point3acres
  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: . visit 1point3acres.com for more.
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,全过了

请问dp是怎样的思路呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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