【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 338|回复: 10
收起左侧

Rubrik 电面面经

[复制链接] |试试Instant~ |关注本帖

() @ - -  |

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
上周刚面完rubrk, 挂啦 。 题目是 给一个matrix such as[[4,6,5],[1,3,7],[2,0,8]], 通过每个element之间的swap 最终要得到一个这样的matrix [[1,2,3],[4,5,6],[7,8,0]]. 问最少交换的次数是多少。每次swap 可以与该element的上下左右 swap. . 鍥磋鎴戜滑@1point 3 acres

补充内容 (2017-7-16 23:00):
新人一枚  求加点分啊
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2017-7-16 23:02):. 1point3acres.com/bbs
做的思想放在评论中, 当时代码量很大

评分

1

查看全部评分

FightForTomo 发表于 6 天前 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
看着就复杂。
. more info on 1point3acres.com
跟问最少用多少步把一个字符串变成另外一个类似吧。
回复 支持 反对

使用道具 举报

 楼主| luoluoluoyu 发表于 6 天前 | 显示全部楼层
关注一亩三分地微博:
Warald
FightForTomo 发表于 2017-7-16 07:16
看着就复杂。-google 1point3acres

跟问最少用多少步把一个字符串变成另外一个类似吧。

当时我用bfs做的
回复 支持 反对

使用道具 举报

FightForTomo 发表于 6 天前 | 显示全部楼层

说下思路和代码?
回复 支持 反对

使用道具 举报

cawe 发表于 6 天前 | 显示全部楼层
楼主可以说下具体怎么做的吗
回复 支持 反对

使用道具 举报

vegito2002 发表于 6 天前 | 显示全部楼层
同求做法, 这个题目看着好懵.
回复 支持 反对

使用道具 举报

magicsets 发表于 6 天前 | 显示全部楼层
这个问题不知道有没有什么特别的结构或性质可以有贪心策略。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果没有的话,就是类似于魔方还原的问题,一般用启发式搜索的方法(A*算法)

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

https://heuristicswiki.wikispaces.com/Rubik%27s+cube
.鐣欏璁哄潧-涓浜-涓夊垎鍦
A*算法本质上是”智能”的BFS算法,虽然worse case下复杂度和BFS一样,但在实践中非常好用(e.g. 游戏里自动寻路,机器人行动规划,寻找魔方还原的最短步数,...)
回复 支持 反对

使用道具 举报

f1371342385 发表于 6 天前 | 显示全部楼层
就是九宫格的算法,A*搜一下就好,但是代码好多
回复 支持 反对

使用道具 举报

 楼主| luoluoluoyu 发表于 6 天前 | 显示全部楼层
我当时 bfs 解的 就像暴力解法 用啦queue<arr[][]> 。 每poll 出来一个 先check 当前的arr[][] 与最终要得到的状态 matrix [[1,2,3],[4,5,6],[7,8,0]] 是不是一样,
回复 支持 反对

使用道具 举报

 楼主| luoluoluoyu 发表于 6 天前 | 显示全部楼层
如果是一样直接返回, 如果不是一样, copy当前数组, 再进行上下左右的dfs
回复 支持 反对

使用道具 举报

2011051305 发表于 5 天前 | 显示全部楼层
我觉得楼主的思想用bfs是正常解法 a*这种要学过AI的课才知道的, 这么看来其实回答的很不错了,为啥会挂掉呢? 对方觉得你剪枝的策略不好?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-22 19:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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