一亩三分地论坛

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

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

Amazon OA题Find path in maze解法,复杂度,Followup集中讨论

[复制链接] |试试Instant~ |关注本帖
luckyjessica 发表于 2015-11-28 07:01:55 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Amazon - Other - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
最近在准备video,发现地里关于Maze这道题的讨论不是很多,于是就想开个帖子,大家可以一起来讨论解法,复杂度和优化方法,video过的小伙伴也欢迎来说说当时面试官问了什么follow up~~
题目大概是这样的:输入一个2D array, m*n(0代表墙,1代表路),一只老鼠站在(0,0)处,在迷宫的某处有cheese的(标记为9),问是否存在路径通向吃的。return的1为能达到,0为不能。
我的解法:用的DFS,在某个方向一直找直到遇到了墙,然后再从当前位置开始继续找。
复杂度:因为每个位置都会走到,所以感觉时间复杂度是O(M*N),空间复杂度的话,因为用了栈,所以是递归栈的大小?如果不对请大神指出
优化:我改了maze的值,优化的话可以另建一个boolean[][]来标记走过的node,其他我想不出还能怎么优化了,或者可以把代码改成iteration的,iteration不需要用栈,这算是种优化吗?


关于这道题什么解法才是最优的呢?另外不知道面试官对于这题还会问啥follow up,欢迎大家一起来讨论. Waral 鍗氬鏈夋洿澶氭枃绔,




补充内容 (2015-11-28 07:40):
好像这个复杂度不对,似乎跟最大深度有关,我已经晕了,求大神解答 T T
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-11-29 13:36):
如何记录path?

评分

1

查看全部评分

本帖被以下淘专辑推荐:

lbjmj23 发表于 2015-11-29 11:53:21 | 显示全部楼层
chongzi159 发表于 2015-11-29 02:03
访问过的点直接改maze值就没有用额外空间了啊,怎么会是o(mn),除非用额外的visit[][]来保存访问过的点

. 1point3acres.com/bbs但是BFS的queue或者是DFS的stack都是需要空间的。。worst case是O(mn)吧

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

tnonec 发表于 2015-11-28 14:32:42 | 显示全部楼层
改不改input是你coding pattern的问题,一般来说input还是不动的好,当然这题动了结果也不会出问题,video一提也就完了,不改的话可以用boolean[][],新建了wrapper class可以用hashset,再有就是对这个branch factor最多为3的matrix来说,感觉bfs适合找有没有path,dfs适合找出一条path,另复杂度应该就是o(mm),我video的时候大概说了这些,当然也有可能有错,大家加油!

评分

3

查看全部评分

回复 支持 1 反对 0

使用道具 举报

kaleidoscope719 发表于 2015-11-28 07:07:45 | 显示全部楼层
改了maze的值再改回去呗。。感觉不需要用多的空间来标记
回复 支持 反对

使用道具 举报

melodyfeelings 发表于 2015-11-28 07:15:49 | 显示全部楼层
求问这题BFS和DFS的优劣
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-11-28 08:36:00 | 显示全部楼层
求问为什么需要再用一个 矩阵存是否被修改过?为什么这算是优化?
多谢
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-11-28 08:36:54 | 显示全部楼层
kaleidoscope719 发表于 2015-11-28 07:07
改了maze的值再改回去呗。。感觉不需要用多的空间来标记

为什么改了maze的值还要再改回去? 不改回去有什么问题么?为什么个人觉得用dfs/bfs不用改回去啊
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-11-28 08:38:26 | 显示全部楼层
melodyfeelings 发表于 2015-11-28 07:15
求问这题BFS和DFS的优劣
. Waral 鍗氬鏈夋洿澶氭枃绔,
同求问,我个人觉得是不是差不多,只不过dfs一般用于找是否两点之间有path,bfs一般是找最短距离吧,个人觉得差不多
回复 支持 反对

使用道具 举报

howeverme 发表于 2015-11-28 09:08:00 | 显示全部楼层
请问bfs 的空间复杂度是不是 O(m + n)??????
回复 支持 反对

使用道具 举报

rosalind324 发表于 2015-11-28 09:31:38 | 显示全部楼层
我是BFS 做的,可以不用boolean[][]  直接改visited 的maze 为 -1, 后面看只要>0 就符合,看我写的,来传送门 》》》》》》》》http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154566&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
回复 支持 反对

使用道具 举报

 楼主| luckyjessica 发表于 2015-11-28 09:43:34 | 显示全部楼层
rosalind324 发表于 2015-11-28 09:31
我是BFS 做的,可以不用boolean[][]  直接改visited 的maze 为 -1, 后面看只要>0 就符合,看我写的,来传 ...
. 1point3acres.com/bbs
谢谢~我有看到你的代码来着,我是觉得改maze不太好,所以才说可以建个boolean[][]来标visited
回复 支持 反对

使用道具 举报

Hello_Jiaming 发表于 2015-11-28 10:50:22 | 显示全部楼层
inkhay 发表于 2015-11-28 08:36
为什么改了maze的值还要再改回去? 不改回去有什么问题么?为什么个人觉得用dfs/bfs不用改回去啊

@inkhay 你觉得为什么不用改回去啊?我做的时候也没改,但不知道怎么表达为什么不用改回去,如果video的时候问到了
回复 支持 反对

使用道具 举报

乳大未必有奶 发表于 2015-11-28 10:54:00 | 显示全部楼层
我也在研究这道题,为什么我觉得bfs和dfs是一样的呢?没有本质区别吧
回复 支持 反对

使用道具 举报

 楼主| luckyjessica 发表于 2015-11-28 12:08:44 | 显示全部楼层
乳大未必有奶 发表于 2015-11-28 10:54
我也在研究这道题,为什么我觉得bfs和dfs是一样的呢?没有本质区别吧

因为这题只要回答能不能走到,所以感觉上DFS和BFS都差不多,不过这两种时间复杂度各是啥,晕了已经。。
回复 支持 反对

使用道具 举报

乳大未必有奶 发表于 2015-11-28 12:37:34 | 显示全部楼层
luckyjessica 发表于 2015-11-28 12:08
因为这题只要回答能不能走到,所以感觉上DFS和BFS都差不多,不过这两种时间复杂度各是啥,晕了已经。。

本渣以为就是m*n,最差情况就是所有的点都遍历一遍
回复 支持 反对

使用道具 举报

inkhay 发表于 2015-11-28 14:03:30 | 显示全部楼层
Hello_Jiaming 发表于 2015-11-28 10:50
@inkhay 你觉得为什么不用改回去啊?我做的时候也没改,但不知道怎么表达为什么不用改回去,如果video的 ...

本来bfs/dfs都要标记是否已经visit过吧, 觉得正常的图搜索中 bfs/dfs都是查neighbor是否被visit 过,被visit过一次就不会再被visit 了吧。。。不过问了同学大家意见好像不太一致,不过不改回来对maze的结果肯定没问题
回复 支持 反对

使用道具 举报

chongzi159 发表于 2015-11-28 22:14:40 | 显示全部楼层
tnonec 发表于 2015-11-28 14:32
改不改input是你coding pattern的问题,一般来说input还是不动的好,当然这题动了结果也不会出问题,video ...

多谢分享,hashset用来干什么的?
回复 支持 反对

使用道具 举报

 楼主| luckyjessica 发表于 2015-11-29 01:03:34 | 显示全部楼层
chongzi159 发表于 2015-11-28 22:14. 1point3acres.com/bbs
多谢分享,hashset用来干什么的?

应该是用来存走过的位置(i,j)
回复 支持 反对

使用道具 举报

 楼主| luckyjessica 发表于 2015-11-29 01:04:37 | 显示全部楼层
tnonec 发表于 2015-11-28 14:32
改不改input是你coding pattern的问题,一般来说input还是不动的好,当然这题动了结果也不会出问题,video ...

谢谢回复!请问空间复杂度是多少呢?我觉得也是O(mn)
回复 支持 反对

使用道具 举报

 楼主| luckyjessica 发表于 2015-11-29 01:06:55 | 显示全部楼层
tnonec 发表于 2015-11-28 14:32
改不改input是你coding pattern的问题,一般来说input还是不动的好,当然这题动了结果也不会出问题,video ...

另外我还想问一下这道题最efficient的解法是哪种呢?还是DFS和BFS一样?我感觉BFS空间用的少,可能比DFS更优一些?
回复 支持 反对

使用道具 举报

chongzi159 发表于 2015-11-29 02:03:36 | 显示全部楼层
luckyjessica 发表于 2015-11-29 01:04
谢谢回复!请问空间复杂度是多少呢?我觉得也是O(mn)

访问过的点直接改maze值就没有用额外空间了啊,怎么会是o(mn),除非用额外的visit[][]来保存访问过的点
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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