面试常见场景题智力题概率题

面试常见场景题智力题概率题

场景题

1. 搜索引擎:

会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询长度不超过 255 字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
答：一千万个记录，除去重复后，实际上只有300万个不同的记录，每个记录假定为最大长度255Byte，则最多占用内存为：3M*1K/4=0.75G<1G，完全可以将所以查询记录存放在内存中进行处理。相较于第一道题目，这题还更简单了，直接HashMap（或前缀树）+堆取topk即可。
具体做法如下：

1.   遍历一遍左右的Query串，利用HashMap（或前缀树）统计频率，时间复杂度为O(N)，N=1000万； 
   

2. 建立并维护一个大小为10的最小堆，然后遍历300万Query的频率，分别和根元素（最小值）进行对比，最后找到Top K，时间复杂度为N‘logK，N‘=300万，K=10。
   

2. 返回频数最高的100个词:

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频率最高的100个词
具体做法如下：

1. 分而治之、hash映射：遍历一遍文件，对于每个词x，取hash(x)并模5000，这样可以将文件里的所有词分别存到5000个小文件中，如果哈希函数设计得合理的话，每个文件大概是200k左右。就算其中有些文件超过了1M大小，还可以按照同样的方法继续往下分，直到分解得到的小文件的大小都不超过1M；
2. HashMap（或前缀树）统计频率：对于每个小文件，利用HashMap（或前缀树）统计词频；

智力题：

3. 先手后手问题：

一共n张牌，两人轮流抽排，每人每次需抽取1至m张（不可不抽），谁先抽完牌谁赢（无牌可抽的算输）。给定输入n,m。请问先手的玩家能赢吗？（注：两人都会做出对自己最优的策略）
答：
（并非严格意义的编程，更像是智力题）
if n % (m + 1) == 0:
后手胜
else:
先手胜

4. 分金条问题：

5. rand（0-3）怎么变成rand（0-6）：

0，1，2，3四个数等概率要变成0，1，2，3，4，5，6，7等概率的话
因此，用rand（0-3）*4=0，4，8，12等概率
加上rand（0-3）得到0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15等概率
去掉14，15两种状态，剩下0-13对7求模归类就好，0-13等概率出现，1415丢掉就好、
因此答案是rand（0-3）*4+rand（0-3）&&不等于14 or 15

6.rand（0-1）怎么变成rand（0-3）：

rand(0-1)到rand(0-3)的话，直接rand(0-1)*2+rand(0-1)就好，正好生成0123等概率

7. 抛硬币：

算抛硬币连续两次正面的期望：

8。 一个单链表无环，长度未知，只能遍历一次，求怎么平等概率采样到k个元素

蓄水池算法：
1、申请一个长度为K的数组A保存抽样，数组A相当于容量为K的蓄水池。
2、保存首先接收到的K个元素
3、继续向后遍历，当接收到第i个新元素t时，以k/i的概率随机替换A中的元素(即生成[1,i]间随机数j，若j<=k，则以t替换A[j])