【阿里巴巴校招】4.2日阿里在线笔试精华集锦再现

问题一：

计算机使用的随机数生成器往往是伪随机的，为了达到统计意义上的真随机数，可以需要引入系统
外的变量等作为随机种子（如 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 （这里理解构造了一个新的等概率生成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主要保存连续的头尾数字就可以了