UDN-企业互联网技术人气社区

板块导航

浏览  : 1561
回复  : 5

[面试经历] 【阿里巴巴校招】4.2日阿里在线笔试精华集锦再现

[复制链接]
笑微的头像 楼主
发表于 2015-9-15 18:25:36 | 显示全部楼层 |阅读模式
问题一:

        计算机使用的随机数生成器往往是伪随机的,为了达到统计意义上的真随机数,可以需要引入系统
外的变量等作为随机种子(如 UNIX 系统中熵池)。假设有一天出现了上帝的投硬币函数 : int G();   
由于这里用到的上帝硬币可能不均匀。但可以保证是 G() 可以 x 概率返回 11-x 的概率返回 0 ,其中 x 为未知常数(且 x 不等于 01 )。
请实现目标函数 : int F(double p);   
要求
  1. F 函数以概率 p 返回 1 ,以 1-p 返回 0
  2. 除了 G 之外,不使用的任何库函数。 PS :定义宏 UINT_MAX=0xffffffff   
基于前述类似思路,请构造函数求下述无理数近似值:
  1. double pi(); // 圆周率 π   
  2. double e(); // 自然对数函数的底数 e

        提示:作为模拟过程,可引入最高重复试验次数,请简述思路并完成代码。

       


        解答:

        利用G()生成01和10概率是相同的

       


        1.接下来假设01的概率生成1,10的概率生成0 (这里理解构造了一个新的等概率生成0,1的随机器)

        2.那么假设p为3/7,那通过上面的假设构造出等概率的000
    001 010 011 100 101 110   111八种概率结果(利用上一步新构造的等概率随机器构造)

        3.去掉其中一个,取三个为1,得到3/7概率为1的函数。

        总结:每个有理数P可以构造为分数a/b,然后构造2^m>b的m位数字,去掉多余的2^m-b个数,制定其中a个数字为1,其他的为0.

       


        至于无理数的求解有一些数学知识,利用下面公式加上群主的第一个方法就可以啦。

       


        问题二:

        分布式系统中的 RPC 请求经常出现乱序的情况。
写一个算法来将一个乱序的序列保序输出。例如 , 假设起始序号是 1 ,对于 (1,  2,  5,  8,  10,  4,  3,  6,  9,  7) 这个序列,输出是 :
1
2
3,  4,  5
6
7,  8,  9,  10
上述例子中, 3 到来的时候会发现 4,5 已经在了。因此将已经满足顺序的整个序列( 3,  4,  5 )输出为一行。
要求:
1.   写一个高效的算法完成上述功能,实现要尽可能的健壮、易于维护
2.   为该算法设计并实现单元测试

        解答:

        题目的意思大概是有一个缓冲区存储收到的数字,如果收到的数字与缓冲区的数字连续了,并且已经于输出的数字连续,就输出~

        思路:

        1.记录当前的数字比如3  

        2.进来4,4放起来  

        3.进来6,先判断6-1是否存在,存在就连在一起,否在就6自己放着  

        4.进来5,判断5-1是否存在,存在,所以45连起来,然后5+1=6也存在,也连起来  

        5.进来3,4存在,然后就把上面连起来的都输出

        整体是一个类似点连成集合,集合再连成集合的概念

        总结:

        1,  2,  5,  8,  10,  4,  3,  6,  9,  7
cur  =
  1,  
1  进来输出1,cur  =  cur+1
2  进来输出2  cur  =  cur  +  1
5  进来,
  5!=cur,  记录{5}
8
   进来,8!=cur,记录{5},{8}
10 进来,10!=cur,记录{5},{8}{10}
4
   进来,4!=cur,记录{4,5},{8}{10}
3
   进来,3=cur,  输出3,4,5,剩余记录
  {8}{10}  cur  =  6
6  进来,6  =
  cur,输出6,cur=7
9
   进来  9!=  cur,剩余{8,9,10}
7
   进来,7=cur,输出7,8,9,10

        优化:

        提高效率可以用hash表    进来的数+1    在哈希表里存不存在  不存在就输出,存在就连着输出

        每次进来数字要把连续的整合到一块

        可以提高效率,  hash的value主要保存连续的头尾数字就可以了

       


发表于 2015-9-15 19:32:41 | 显示全部楼层

题目:       计算机使用的随机数生成器往往是伪随机的,为了达到统计意义上的真随机数,可以需要引入系统    外的变量等作为随机种子(如UNIX系统中熵池)。假设有一天出现了上帝的投硬币函数: int G();    由于这里用到的上帝硬币可能不均匀。但可以保证是G()可以x概率返回1,1-x的概率返回0,其中x为未知常数(且x不等于0或1)。    请实现目标函数: int F(double p); 要求 1. F函数以概率p返回1,以1-p返回0。    2. 除了G之外,不使用的任何库函数。 PS:定义宏UINT_MAX=0xffffffff    基于前述类似思路,请构造函数求下述无理数近似值: 1. double pi(); //圆周率π    2. double e(); // 自然对数函数的底数e。 提示:作为模拟过程,可引入最高重复试验次数,请简述思路并完成代码。                   群主解答:   利用G()生成01和10概率是相同的     1.接下来假设01的概率生成1,10的概率生成0   2.那么假设p为3/7,那通过上面的假设构造出等概率的000 001 010 011 100 101 110 111八种概率结果   3.去掉其中一个,取三个为1,得到3/7概率为1的函数。     总结:每个有理数P可以构造为分数a/b,然后构造2^m>b的m位数字,去掉多余的2^m-b个数,制定其中a个数字为1,其他的为0.       至于无理数的求解有一些数学知识,利用下面公式加上群主的第一个方法就可以啦。
使用道具 举报

回复

发表于 2015-9-15 20:33:53 | 显示全部楼层

第二题我的思路:   [1,  2,  5,  8,  10,  4,  3,  6,  9,  7]    1,读到1,2,输出1,2。这时期望读到3。   2,读到的第一个不是3的数,记住下标start = 2。   3,终于读到3,记住下标end = 6。   4,对[start,end]范围内做一下快排,[3,4,5,8,10],输出3,4,5。这时将start改成8的下标 ,start  = 5。   5,从end开始继续读,期望读到6。记住end = 7。对这个范围做快排,[6,8,10],输出6。改变start 为8的下标。   ......   如此重复。
使用道具 举报

回复

发表于 2015-9-15 23:15:51 | 显示全部楼层

有问题二的代码吗?
使用道具 举报

回复

发表于 2015-9-16 01:10:05 | 显示全部楼层

问题一不是很明白,有人可以解释一下吗
使用道具 举报

回复

发表于 2015-9-16 02:52:02 | 显示全部楼层

问题二维护一个最小堆是不是就方便很多了
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部