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

Google 跪经 10.13

全局:

2018(7-9月) 码农类General 硕士 全职@google - 网上海投 - 技术电面  | | Other | 应届毕业生

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

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

x
十分钟前热扑扑的挂经
第一题:
给你一个rand5() 的function, return 1 ~ 5 with equal proba
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
0-14 02:10):
打错了 rand7()  要return 1 ~ 7

评分

参与人数 3大米 +44 收起 理由
lwill + 3 感谢分享!
qpalzm0827 + 1 感谢分享!
夏虫不知雪花 + 40

查看全部评分


上一篇:求Airbnb coding challenge 4的面经
下一篇:微软会有电话拒信
推荐
epsilon 2017-10-14 03:44:26 | 只看该作者
全局:
monte carlo经典的acceptance-rejection。 这题简单的做法就是call rand5两次,共有25种结果组合,把其中21种平均分给1 ... 7(ls提到的五进制转换是个很好的做法),碰到剩下4种就重新call rand5两次直到遇到前21种为止。

评分

参与人数 2大米 +7 收起 理由
浴火擎灯 + 5 给你点个赞!
lwill + 2 回答的很好!

查看全部评分

回复

使用道具 举报

推荐
edyyy 2017-10-14 03:33:45 | 只看该作者
全局:
  1. #include <iostream>

  2. using namespace std;
  3. int rand7() //random number from 1 - 7
  4. {
  5.     int r = 0;
  6.     do
  7.     {
  8.        int a = rand() % 5; //uniformly at random from 0 to 4
  9.        int b = rand() % 5;  //uniformly at random from 0 to 4
  10.        r = 5*b + a;  //uniformly at random from 0 to 24
  11.     }
  12.     while (r >= 21); // in this event, we have to roll again
  13.    //postcondition of loop: we have a number uniformly at random between 0 and 20

  14.   return r % 7 + 1;
  15.   
  16.   //there are 3 numbers in [0, 20] for each possible return value
  17.   //so each has equal probability.      
  18. }
  19. int main()
  20. {
  21.     int res = 0;
  22.     for (int i = 0; i < 1000000; i++) {
  23.         res += rand7();
  24.     }
  25.     cout << (double)res/1000000.00;
  26. //should return 4.000..
  27.     return 0;
  28. }
复制代码
回复

使用道具 举报

推荐
epsilon 2017-10-14 04:08:15 | 只看该作者
全局:
qlwfby 发表于 2017-10-14 04:00
赞,这个做法是对的,这样生成数概率为3/25 + 3/25 * 4/25 + 3/25 * 4/25 * 4/25.。。。。 = 1/7,就是有 ...

没有。步骤数是个几何分布, 有限步骤内结束的概率为1, 数学期望25/21。
回复

使用道具 举报

🔗
jiongjiongyoush 2017-10-14 02:48:26 | 只看该作者
全局:
第一题可以这样吗
7次rand5()的和然后除以5
回复

使用道具 举报

🔗
 楼主| FI-SIGHT 2017-10-14 02:56:17 | 只看该作者
全局:
jiongjiongyoush 发表于 2017-10-14 02:48
第一题可以这样吗
7次rand5()的和然后除以5

我一开始也是这么说的
好像不太对
回复

使用道具 举报

🔗
jiongjiongyoush 2017-10-14 03:06:07 | 只看该作者
全局:
FI-SIGHT 发表于 2017-10-14 02:56
我一开始也是这么说的
好像不太对

好像是的==比如得到7的概率是(1/5)^7
回复

使用道具 举报

🔗
jiongjiongyoush 2017-10-14 03:09:59 | 只看该作者
全局:
那应该是这样吧
对于7次rand5()的和
1-5是1,
6-10是2,
etc
可以二分做
回复

使用道具 举报

🔗
randrand1 2017-10-14 03:18:08 | 只看该作者
全局:
一种做法是这样, Rand5产生的是1-5,我们当作是0-4, 然后假设每次产生两个拼成一个五进制的数字,那么范围就是在[0,24]之间,每次在0-6之间就返回,其他的reject重新取两个数,应该还可以再改进。
回复

使用道具 举报

🔗
TrustMeBro 2017-10-14 03:20:00 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| FI-SIGHT 2017-10-14 03:36:38 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

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

本版积分规则

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