<
查看: 5955| 回复: 11
收起左侧

[找工就业] Codility的一道题

illuminati | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   107
99%
1%
1

2016(1-3月)-EE硕士+fresh grad 无实习或全职 | 网上海投| 码农类General其他@toptal

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
分享一道面试题,求思路!从(0,0)到(A,B),只能走(2,1)或(1,2)向量,就是只能走“日”. .и
求问能否到达以及能到达的话最少需要多少步?. check 1point3acres for more.

上一篇:Google内推多长时间可以收到消息?
下一篇:有没有小伙伴拿到MathWorks EDG的offer呀?
rayord 2016-1-6 12:13:13 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   65
27%
73%
174
第一题代码:
int searchstep(pair<int,int> dst, queue<int> step, queue<pair<int,int>> position){
    while(!step.empty()){
        int i=position.front().first;. check 1point3acres for more.
        int j=position.front().second;.
        //check curpos
. ----        if(i==dst.first && j==dst.second){. check 1point3acres for more.
            return step.front();
        }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);.1point3acres
            position.push(make_pair(i-1,j-2));    step.push(step.front()+1);
.google  и            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();
.1point3acres        }
    }
    return -1;
}
int main(int argc, char* argv[]){
    queue<pair<int,int>> pos;. 1point 3acres
    queue<int> step;. From 1point 3acres bbs
    pos.push(make_pair(0,0));. 1point3acres.com
    step.push(0);. Waral dи,
   
    cout<<searchstep(make_pair(0,1),step,pos);
    return 0;
}
回复

使用道具 举报

 楼主| illuminati 2016-1-5 13:32:42 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   107
99%
1%
1
bonnachoven 发表于 2016-1-5 13:29
第一题应该bfs或者dfs都可以做吧,感觉bfs会快,因为只用找到最短的一条路径就可以了。
第二题有时间空间 ...

第二题不知为何只有60%的正确率。。。时空都是O(N)吧我记得,感觉没什么问题啊,所以怀疑test case的问题。。。
另外第一题有类似问题代码吗?
回复

使用道具 举报

rayord 2016-1-6 11:54:55 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   65
27%
73%
174
bonnachoven 发表于 2016-1-5 13:29
第一题应该bfs或者dfs都可以做吧,感觉bfs会快,因为只用找到最短的一条路径就可以了。.
第二题有时间空间 ...

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

使用道具 举报

 楼主| illuminati 2016-1-5 13:07:09 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   107
99%
1%
1
另外还有一道题performance只有60%。. ----
题目是这样的:给定序列A,比如[1,2,3,4,5,1],给定target number,比如就是1。 ..
要求对序列切一刀,使得左半部分的target number数量等于右半部分不是target number的数量。
大家有什么好算法吗?能提供edge case吗?谢谢!
回复

使用道具 举报

bonnachoven 2016-1-5 13:29:47 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   18
100%
0%
0
第一题应该bfs或者dfs都可以做吧,感觉bfs会快,因为只用找到最短的一条路径就可以了。
第二题有时间空间复杂度要求么?没有的话感觉brute force用两个数组分别记左边等于target和右边不等于target的然后再比较对应位置就可以了吧。。。
回复

使用道具 举报

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

不要怀疑test case,. 1point 3 acres
. 1point3acres.com
60%明显就是错的离谱了。
回复

使用道具 举报

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

继续查bug吧
回复

使用道具 举报

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

......哥,bfs不是这么玩的。
回复

使用道具 举报

rayord 2016-1-6 12:17:01 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   65
27%
73%
174
163 发表于 2016-1-6 12:10. From 1point 3acres bbs
......哥,bfs不是这么玩的。

求方法。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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