一亩三分地论坛

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

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

Twiiter 电面

[复制链接] |试试Instant~ |关注本帖
哈哈哈大雄 发表于 2015-10-11 08:31:28 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Twitter - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
Twitter 电面,一个新题目
3 * 3 的一个board,上面有1-8 八个数,0表示一个空格,其他的数可以移到这个位置。
每个状态可以编码成一个string,. visit 1point3acres.com for more.
e.g.
1 2 3
4 5 6
7 8 0 => "123456780" // s0

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后一个函数move, 可以向 left, right, up, down, move . visit 1point3acres.com for more.
比如 move(s0, d) 表示把6移下来. From 1point 3acres bbs
1 2 3
4 5 0. from: 1point3acres.com/bbs
7 8 6 => "123450786" // s1
. Waral 鍗氬鏈夋洿澶氭枃绔,
实现 move(String s, int direction) 函数

follow up, 给任意一个状态s,求最小步数把它reverse 到s0.

评分

1

查看全部评分

nothingtrouble 发表于 2015-10-11 09:00:19 | 显示全部楼层
比较2的办法就是, str转成char[][],完成move回转. 第二问就是bfs用之前的result了. 最好保持zero的position为global的变量,这样不用重复在move函数里面找0.
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-23 07:56:56 | 显示全部楼层
follow up 是用A*吧 怎么面这么难
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-7 09:59:10 | 显示全部楼层
其实只有9个数字,一共9!种可能,所以其实可以就是dfs算到底,具体方法是,开辟一个array A, A记录从这个数到s0需要的步数,然后,每个A可以经过4种可能变换到最多4个数字,所以只需要求出对应4个数字对应的最短步数,取最短+1即可。如果不止9个数字就要麻烦很多了。

补充内容 (2015-12-7 10:01):
开销就是9!。但是我一直在想这道题能不能优化。从s1->s0,s1可以先变化到s2,似乎s2和s0共有的common prefix不能短于s1和s0的common prefix长度。但是一时间不知道怎么证明。
回复 支持 反对

使用道具 举报

serenalin 发表于 2015-12-16 02:23:47 | 显示全部楼层
returning 发表于 2015-12-7 09:59
其实只有9个数字,一共9!种可能,所以其实可以就是dfs算到底,具体方法是,开辟一个array A, A记录从这个数 ...

bfs是不是可以略快一点?因为可以遇到第一个match的就返回search level,不用再继续搜了。
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-19 13:09:20 | 显示全部楼层
BFS, IDDFS, A* 都行 但应该IDA*效果最好
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 02:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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