📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2280| 回复: 8
跳转到指定楼层
上一主题 下一主题
收起左侧

洗牌问题变种

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
洗牌问题只允许调用一次 random(), 如果让结果随机呢?

上一篇:如果不知道“leetcode”怎样才能搜到它
下一篇:BT upside down
推荐
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。
回复

使用道具 举报

🔗
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随机数做的, 但他最后下的结论是"你这样做也可以"... 所以我才来发帖问有什么办法么? 给我的感觉是洗牌问题的优化方法, 思维有点跳跃, 不好意思, 谢谢楼主~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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