谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1443|回复: 12
收起左侧

Rubrik 电面面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
luoluoluoyu 发表于 2017-7-16 07:10:47 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

() @ - -   | |

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

您需要 登录 才可以下载或查看,没有帐号?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.

补充内容 (2017-7-16 23:00):
新人一枚  求加点分啊

补充内容 (2017-7-16 23:02):
做的思想放在评论中, 当时代码量很大

评分

参与人数 2大米 +10 收起 理由
luckycat123 + 5 感谢分享!
vegito2002 + 5 感谢分享!

查看全部评分


上一篇:请教dropbox 一道题的follow up
下一篇:Pocket Gems 电面+onsite
我的人缘0
FightForTomo 发表于 2017-7-16 07:16:23 | 显示全部楼层
  此人我要顶:
 
53% (7) 【我投】
  此人我要踩:
 
47% (8) 【我投】
看着就复杂。
. 一亩-三分-地,独家发布
跟问最少用多少步把一个字符串变成另外一个类似吧。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| luoluoluoyu 发表于 2017-7-16 07:17:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
FightForTomo 发表于 2017-7-16 07:16
看着就复杂。

跟问最少用多少步把一个字符串变成另外一个类似吧。
.1point3acres网
当时我用bfs做的
回复 支持 反对

使用道具 举报

我的人缘0
FightForTomo 发表于 2017-7-16 08:15:20 | 显示全部楼层
  此人我要顶:
 
53% (7) 【我投】
  此人我要踩:
 
47% (8) 【我投】
luoluoluoyu 发表于 2017-7-16 07:17.本文原创自1point3acres论坛
当时我用bfs做的
. 1point 3acres 论坛
说下思路和代码?
回复 支持 反对

使用道具 举报

我的人缘0
cawe 发表于 2017-7-16 10:13:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主可以说下具体怎么做的吗
回复 支持 反对

使用道具 举报

我的人缘0
vegito2002 发表于 2017-7-16 11:40:38 | 显示全部楼层
  此人我要顶:
 
49% (13) 【我投】
  此人我要踩:
 
51% (15) 【我投】
同求做法, 这个题目看着好懵.
回复 支持 反对

使用道具 举报

我的人缘0
magicsets 发表于 2017-7-16 12:20:38 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这个问题不知道有没有什么特别的结构或性质可以有贪心策略。
. 围观我们@1point 3 acres
如果没有的话,就是类似于魔方还原的问题,一般用启发式搜索的方法(A*算法).留学论坛-一亩-三分地

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

https://heuristicswiki.wikispaces.com/Rubik%27s+cube

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

使用道具 举报

我的人缘0
f1371342385 发表于 2017-7-16 13:13:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
就是九宫格的算法,A*搜一下就好,但是代码好多
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| luoluoluoyu 发表于 2017-7-16 23:00:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
如果是一样直接返回, 如果不是一样, copy当前数组, 再进行上下左右的dfs
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
枫叶grey 发表于 2017-7-27 04:56:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
所以该不该用BFS呢 有人写出具体代码吗 跪求
回复 支持 反对

使用道具 举报

我的人缘0
hello_ 发表于 2017-10-22 01:48:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
magicsets 发表于 2017-7-16 12:20
这个问题不知道有没有什么特别的结构或性质可以有贪心策略。

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

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-6-24 03:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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