一亩三分地论坛

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

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

[算法题] 洗牌问题变种

[复制链接] |试试Instant~ |关注本帖
lrn0304 发表于 2015-10-29 05:34:34 | 显示全部楼层 |阅读模式

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

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

x
洗牌问题只允许调用一次 random(), 如果让结果随机呢?
stellari 发表于 2015-11-3 16:40:33 | 显示全部楼层
lrn0304 发表于 2015-11-3 10:05
面试时候题目不是54这个数, size 只有 5 所以我才会用那种方法, 至于为什么我会提到洗牌问题, 这道题前置 ...


果然是情况3……

5和54是有决定性的不同的啊,为什么原帖中不说明呢?而且我在2、4楼的假设明明不正确,为什么不指出呢?咱们本来一句话就能说明白的事情,结果来回用了3天,我还写程序去算log(54!)到底是多少。这就是交流失败的一个典型例子。说真的,别抱怨,如果你在面试时也是用类似的交流方式,挂你真的不冤。

只有5张牌的话,就只有log(5!)=log(120)=7bit信息量,调用一次能产生一个0~1之间的double型的random函数,再将其映射到0~119上就够了。那这道题的考点就非常明显,

1. 你是不是知道如何得到120这个数字(这就是他为什么问你“你想想有几种情况”,这是关键hint。如果这点都不能得到的话,第二步的提示给了你也没有意义,所以他才不说话)。
2. 产生出一个0~119的随机数后,如何将其映射到120种牌堆的情况中的一种?

所以综合看来,这个follow up出得并无问题,你应该多从自身找找原因。

抱歉话重了些,不过总之还是希望你能拿到满意的offer。
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-10-30 23:41:49 | 显示全部楼层
你要说得再清楚一点,random()函数的返回是什么?0~1之间的double型浮点数吗?还有“洗牌问题”指的是“将54张牌按照随机顺序排列”么?
回复 支持 反对

使用道具 举报

readman 发表于 2015-10-31 00:34:39 | 显示全部楼层
stellari 发表于 2015-10-30 23:41
你要说得再清楚一点,random()函数的返回是什么?0~1之间的double型浮点数吗?还有“洗牌问题”指的是“将5 ...

是哒...怎么做啊
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-31 11:12:33 | 显示全部楼层

如果题目是像我2楼的假设那样,那就不可能做到,除非自己编程再实现一个类似一个random函数的东西。理由是:random产生的是一个0~1的64位浮点小数。由于指数位和符号位都不会变,所以实际能用到的只有52位,从信息论的角度看,即是random产生的数字的信息量仅有52bit;而54张牌就有54!种排列方式,如果要求每种排列方式都等概率出现,那么就需要log(54!) ~ 232bit信息才能完整编码。因此理论上来说,要实现54张牌的等概率随机排列,那么random被调用不能少于5次。
回复 支持 反对

使用道具 举报

 楼主| lrn0304 发表于 2015-11-3 00:53:18 | 显示全部楼层
stellari 发表于 2015-10-31 11:12
如果题目是像我2楼的假设那样,那就不可能做到,除非自己编程再实现一个类似一个random函数的东西。理由 ...

onsite 问到的, 我也觉得很奇特. 我最后强行写个 random 生成 [0,54!) 范围的函数, 来获取排列位置, 但是明显是挂了, 反馈是编程能力有问题. 所以不知道这道题考得是什么?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-11-3 08:13:58 | 显示全部楼层
lrn0304 发表于 2015-11-3 00:53
onsite 问到的, 我也觉得很奇特. 我最后强行写个 random 生成 [0,54!) 范围的函数, 来获取排列位置, 但是 ...

54!是个很大很大的数字,你要用什么数据类型存放它呢?如果你用一个内建类型(比如long long之类的)来表示这个数字,我是面试官的话也必然挂你啊。

我想有这么几种可能:

1. 面试官明知此题不可能,就是想等你说出不可能这个结论;
2. 面试官自己也没想清楚这个问题。他自己的备用答案其实是错的;
3. 你没有完全理解面试官的意思,这道题其实还有其他的限制条件。你应该详细和面试官彻底沟通后再作答。恕我直言,从你原帖的描述清晰度来看,我觉得这种情况的概率很高。
回复 支持 反对

使用道具 举报

 楼主| lrn0304 发表于 2015-11-3 10:05:47 | 显示全部楼层
stellari 发表于 2015-11-3 08:13
54!是个很大很大的数字,你要用什么数据类型存放它呢?如果你用一个内建类型(比如long long之类的)来表 ...

面试时候题目不是54这个数, size 只有 5 所以我才会用那种方法, 至于为什么我会提到洗牌问题, 这道题前置题目就是 size = 5 的 shuffle , 我就用洗牌来做的, 然后他才给我了 follow up 说 random 很 costful, 能不能只调用一次. 而且面试官不太反馈我, 只给了一个 hint 说 "你想想有几种情况", 然后就没有了... 我一直积极询问和反馈, 但是面试官一直不说话....
回复 支持 反对

使用道具 举报

 楼主| lrn0304 发表于 2015-11-3 23:53:17 | 显示全部楼层
stellari 发表于 2015-11-3 16:40
果然是情况3……

5和54是有决定性的不同的啊,为什么原帖中不说明呢?而且我在2、4楼的假设明明不正 ...

谢谢, 看来确实是交流的问题啊, 惭愧惭愧, 我也发现了比如120这种一眼就看得出来的问题我经常就略过了, 虽然我最后确实是生成120随机数做的, 但他最后下的结论是"你这样做也可以"... 所以我才来发帖问有什么办法么? 给我的感觉是洗牌问题的优化方法, 思维有点跳跃, 不好意思, 谢谢楼主~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 18:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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