文档章节

美团笔试题

SibylY
 SibylY
发布于 2013/10/09 16:18
字数 645
阅读 61
收藏 0

已有一个随机数发生器,生成0的概率为p,生成1的概率为1-p,求如何利用这个随机数发生器制作一个生成1~n的概率都是 1/n 的发生器

制作 1 2 发生概率都是 1 / 2 的发生器,连续发生2次,则发生00,11的概率为p*p,(1-p)(1-p),发生10,01的概率都为p(1-p),在发生10时返回1,发生01时返回2,则发生1,2的概率相等

制作 1 2 3 发生概率都是 1 / 3的发生器,连续发生3次,则发生001,010,100的概率都为p*p*(1-P),或者是110,101,011概率都为p*(1-p)*(1-p),则用001,010,100分别对应1,2,3返回,即可使得发生1,2,3的概率都为1/3

字符串ABCD,可以由字符串BCDA或者CDAB通过循环移位而得到

考虑一下数组A中元素123456循环右移2位到底是怎么个情况!!!可不可以这样实现呢?将数组A分成两个部分:A[0~n-k-1] 和 A[n-k~n-1] ,将这两个部分分别翻转,然后放在一起在翻转(逆序)。具体是这样的:

(1)翻转1234:123456 ---> 432156

(2)翻转56:     432156 ---> 432165

(3)翻转432165:432165 ---> 561234



//逆序
 2 void Reverse(int A[],int b,int e)
 3 {
 4     for(;b < e;b++,e--)
 5     {
 6         int temp = A[b];
 7         A[b] = A[e];
 8         A[e] = temp;
 9     }
10 }
11 //循环右移
12 void RightShift(int A[],int,int n,int k)
13 {
14     Reverse(A,0,n-k-1);
15     Reverse(A,n-k,n-1);
16     Reverse(A,0,n-1);
17 }
复制代码
细心的读者可能就发现,这里的右移并没有说小于n呀,那么一个k>n那就会出现问题,经过简单的分析,我们发现如果A[]={1,2,3,4,5,6},数组长度是6,那么循环右移7位和循环右移1位是一样的,所以只需要把函数RightShift()中的k取值为k=k%n。如此一来问题就解决了。


【列方程】有四个足球队A,B,C,D分入同一个小组进行单循环比赛,争夺出线权,比赛规定:胜一场得3分,平一场得1分,负一场得0分,小组中名列第一的出现。小组赛结束后,如果A队积分为7分。讨论:①这一小组中共进行多少场比赛?②A队的成绩是几胜几平几负?③请你判断A队能否一定出线?

© 著作权归作者所有

共有 人打赏支持
SibylY
粉丝 29
博文 415
码字总数 333103
作品 0
海淀
程序员
90 道名企笔试和算法题 (含答题讨论)

(点击上方公众号,可快速关注) 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问:如何获取题目列表? 答:① 长摁二维码关注「算法爱好者」,② 然后给它发送 名企笔试 或 算法...

Python开发者
01/21
0
0
【干货分享】面试小技巧

纪念一下第一份面试经历 美团面试主要就是分为笔试和面试,笔试以后我恬不知耻地去霸面了(其实也不觉得有什么恬不知耻,权当考察去了)但其实笔试完没多久后我就接到了约面试时间的电话了。...

路过全世界
2017/04/26
0
0
2018年,作为应届生,求职的我

大学四年,转眼即逝。 四年期间,没有拿过一次奖学金,唯有拿过钱的只有贫困补助。 有参加过社团或是部门,有收获友谊,但不争的我,有想过成为某某部或社团的部长或是副部长,但却不怎么行动...

北极星_51ae
2017/10/21
0
0
2018年,作为应届生,求职的我

大学四年,转眼即逝。 四年期间,没有拿过一次奖学金,唯有拿过钱的只有贫困补助。 有参加过社团或是部门,有收获友谊,但不争的我,有想过成为某某部或社团的部长或是副部长,但却不怎么行动...

北极星_51ae
2017/10/21
0
0
机器学习实习生面试总结(阿里 腾讯等)

今年来一直在找暑期实习,现在基本已经确定了,前后历经差不多2个月吧,发现了很多自己的缺点,同时也希望写出来供需要的人参考了解 先说下我自己的情况吧,决定去腾讯TEG的机器学习岗实习了...

Gavin__Zhou
2017/05/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周三乱弹 —— 我居然在 osc 里追剧

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @舆情风控小组 :分享王菲的单曲《笑忘书》 《笑忘书》- 王菲 手机党少年们想听歌,请使劲儿戳(这里) @艾尔库鲁斯:如果给大家一个选择的机...

小小编辑
45分钟前
70
6
rabbitMq的客户端使用笔记

1、channel声明队列的queueDeclare方法的参数解析 durable: 是否持久化, 队列的声明默认是存放到内存中的,如果rabbitmq重启会丢失,如果想重启之后还存在就要使队列持久化,保存到Erlang自...

DemonsI
53分钟前
0
0
“全新” 编程语言 Julia开箱体验

本文共 851字,阅读大约需要 3分钟 ! 概 述 Julia 是一个 “全新”的高性能动态编程语言,前两天迎来了其 1.0 正式版的重大更新。Julia集 Python、C、R、Ruby 之所长,感觉就像一种脚本语言...

CodeSheep
今天
12
0
软件自动化测试初学者忠告

题外话 测试入门 很多受过高等教育的大学生经常问要不要去报测试培训班来入门测试。 答案是否。 高等教育的合格毕业生要具备自学能力,如果你不具备自学能力,要好好地反省一下,为什么自己受...

python测试开发人工智能安全
今天
5
0
java并发备忘

不安全的“先检查后执行”,代码形式如下: if(条件满足){ //这里容易出现线程安全问题//doSomething}else{//doOther} 读取-修改-写入 原子操作:使用CAS技术,即首先从V中读取...

Funcy1122
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部