一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
电商初创公司Good Days
招聘SDE/UI/TPM等职位实习生
把贵司招聘信息放这里
查看: 1037|回复: 12
收起左侧

Rubrik 电面面经

[复制链接] |试试Instant~ |关注本帖
luoluoluoyu 发表于 2017-7-16 07:10:47 | 显示全部楼层 |阅读模式

() @ - -  |

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

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

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. .鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2017-7-16 23:00):
新人一枚  求加点分啊
-google 1point3acres
补充内容 (2017-7-16 23:02):
做的思想放在评论中, 当时代码量很大

评分

2

查看全部评分

FightForTomo 发表于 2017-7-16 07:16:23 | 显示全部楼层
看着就复杂。
. 1point3acres.com/bbs
跟问最少用多少步把一个字符串变成另外一个类似吧。
回复 支持 反对

使用道具 举报

 楼主| luoluoluoyu 发表于 2017-7-16 07:17:49 | 显示全部楼层
FightForTomo 发表于 2017-7-16 07:16
看着就复杂。

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

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

使用道具 举报

FightForTomo 发表于 2017-7-16 08:15:20 | 显示全部楼层

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

使用道具 举报

cawe 发表于 2017-7-16 10:13:25 | 显示全部楼层
楼主可以说下具体怎么做的吗
回复 支持 反对

使用道具 举报

vegito2002 发表于 2017-7-16 11:40:38 | 显示全部楼层
同求做法, 这个题目看着好懵.
回复 支持 反对

使用道具 举报

magicsets 发表于 2017-7-16 12:20:38 | 显示全部楼层
这个问题不知道有没有什么特别的结构或性质可以有贪心策略。. more info on 1point3acres.com

如果没有的话,就是类似于魔方还原的问题,一般用启发式搜索的方法(A*算法). more info on 1point3acres.com
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html.鏈枃鍘熷垱鑷1point3acres璁哄潧
.鐣欏璁哄潧-涓浜-涓夊垎鍦
https://heuristicswiki.wikispaces.com/Rubik%27s+cube

A*算法本质上是”智能”的BFS算法,虽然worse case下复杂度和BFS一样,但在实践中非常好用(e.g. 游戏里自动寻路,机器人行动规划,寻找魔方还原的最短步数,...)
回复 支持 反对

使用道具 举报

f1371342385 发表于 2017-7-16 13:13:44 | 显示全部楼层
就是九宫格的算法,A*搜一下就好,但是代码好多
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

枫叶grey 发表于 2017-7-27 04:56:26 | 显示全部楼层
所以该不该用BFS呢 有人写出具体代码吗 跪求
回复 支持 反对

使用道具 举报

hello_ 发表于 2017-10-22 01:48:25 | 显示全部楼层
magicsets 发表于 2017-7-16 12:20
这个问题不知道有没有什么特别的结构或性质可以有贪心策略。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

如果没有的话,就是类似于魔方还原的问题, ...

A* 在这里应该是行不通的,必须BFS了。A*只是求出一个解法,但是这个题目要求最少的步数。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-19 02:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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