一亩三分地论坛

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

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

[找工就业] Codility的一道题

[复制链接] |试试Instant~ |关注本帖
illuminati 发表于 2016-1-5 12:42:50 | 显示全部楼层 |阅读模式

2016(1-3月)-[]EE硕士+fresh grad 无实习/全职 - 网上海投| 码农类其他@Toptalfresh grad应届毕业生

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

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

x
分享一道面试题,求思路!从(0,0)到(A,B),只能走(2,1)或(1,2)向量,就是只能走“日”.鏈枃鍘熷垱鑷1point3acres璁哄潧
求问能否到达以及能到达的话最少需要多少步?
 楼主| illuminati 发表于 2016-1-5 13:07:09 | 显示全部楼层
另外还有一道题performance只有60%。.鏈枃鍘熷垱鑷1point3acres璁哄潧
题目是这样的:给定序列A,比如[1,2,3,4,5,1],给定target number,比如就是1。
要求对序列切一刀,使得左半部分的target number数量等于右半部分不是target number的数量。
大家有什么好算法吗?能提供edge case吗?谢谢!
回复 支持 反对

使用道具 举报

bonnachoven 发表于 2016-1-5 13:29:47 | 显示全部楼层
第一题应该bfs或者dfs都可以做吧,感觉bfs会快,因为只用找到最短的一条路径就可以了。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二题有时间空间复杂度要求么?没有的话感觉brute force用两个数组分别记左边等于target和右边不等于target的然后再比较对应位置就可以了吧。。。
回复 支持 反对

使用道具 举报

 楼主| illuminati 发表于 2016-1-5 13:32:42 | 显示全部楼层
bonnachoven 发表于 2016-1-5 13:29
第一题应该bfs或者dfs都可以做吧,感觉bfs会快,因为只用找到最短的一条路径就可以了。
第二题有时间空间 ...
.1point3acres缃
第二题不知为何只有60%的正确率。。。时空都是O(N)吧我记得,感觉没什么问题啊,所以怀疑test case的问题。。。
另外第一题有类似问题代码吗?
回复 支持 反对

使用道具 举报

163 发表于 2016-1-5 14:01:38 | 显示全部楼层
illuminati 发表于 2016-1-5 13:32
第二题不知为何只有60%的正确率。。。时空都是O(N)吧我记得,感觉没什么问题啊,所以怀疑test case的问 ...

不要怀疑test case,. from: 1point3acres.com/bbs

60%明显就是错的离谱了。
回复 支持 反对

使用道具 举报

163 发表于 2016-1-5 14:01:53 | 显示全部楼层
illuminati 发表于 2016-1-5 13:32
第二题不知为何只有60%的正确率。。。时空都是O(N)吧我记得,感觉没什么问题啊,所以怀疑test case的问 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
继续查bug吧
回复 支持 反对

使用道具 举报

rayord 发表于 2016-1-6 11:54:55 | 显示全部楼层
bonnachoven 发表于 2016-1-5 13:29
第一题应该bfs或者dfs都可以做吧,感觉bfs会快,因为只用找到最短的一条路径就可以了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二题有时间空间 ...

BFS是从中心开始,每个位置衍生出来8个新位置,直到到达终点么?问题的规模是8^k, k是最终步数。有更好的解法吗?
回复 支持 反对

使用道具 举报

163 发表于 2016-1-6 12:10:45 | 显示全部楼层
rayord 发表于 2016-1-6 11:54
BFS是从中心开始,每个位置衍生出来8个新位置,直到到达终点么?问题的规模是8^k, k是最终步数。有更好的 ...

......哥,bfs不是这么玩的。
回复 支持 反对

使用道具 举报

rayord 发表于 2016-1-6 12:13:13 | 显示全部楼层
第一题代码:
int searchstep(pair<int,int> dst, queue<int> step, queue<pair<int,int>> position){
    while(!step.empty()){
        int i=position.front().first;
        int j=position.front().second;
        //check curpos
        if(i==dst.first && j==dst.second){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            return step.front();. more info on 1point3acres.com
        }else{
            position.push(make_pair(i+2,j+1));    step.push(step.front()+1);
            position.push(make_pair(i+1,j+2));    step.push(step.front()+1);
            position.push(make_pair(i-1,j+2));    step.push(step.front()+1);
            position.push(make_pair(i-2,j+1));    step.push(step.front()+1);
            position.push(make_pair(i-2,j-1));    step.push(step.front()+1);
            position.push(make_pair(i-1,j-2));    step.push(step.front()+1);
            position.push(make_pair(i+1,j-2));    step.push(step.front()+1);
            position.push(make_pair(i+2,j-1));    step.push(step.front()+1);
            position.pop();    step.pop();
        }
    }
    return -1;
}
int main(int argc, char* argv[]){
    queue<pair<int,int>> pos;
    queue<int> step;
    pos.push(make_pair(0,0));
    step.push(0);. more info on 1point3acres.com
   
    cout<<searchstep(make_pair(0,1),step,pos);
    return 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
回复 支持 反对

使用道具 举报

rayord 发表于 2016-1-6 12:17:01 | 显示全部楼层
163 发表于 2016-1-6 12:10
......哥,bfs不是这么玩的。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
求方法。。
回复 支持 反对

使用道具 举报

163 发表于 2016-1-6 17:13:27 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
BFS要把visit过的顶点都标记出来,防止重复访问。在这个题里,最大运算量是不会超过O(点的个数)的。

你需要找一本基础算法书看看最基本的bfs,dfs是怎么操作的。
回复 支持 反对

使用道具 举报

rayord 发表于 2016-1-7 09:03:44 | 显示全部楼层
163 发表于 2016-1-6 17:13
BFS要把visit过的顶点都标记出来,防止重复访问。在这个题里,最大运算量是不会超过O(点的个数)的。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
...

额。。。忘标记了,哈哈,多谢多谢~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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