数据研发/分析/开发面试题目汇总_数据开发工程师题目

题目1：醉汉坐座位

飞机乘客有对应的1号到100号的座位，这些乘客会按号码顺序登机并应当对号入座，如果他们发现对应号座位被别人坐了，就会在剩下空的座位随便挑一个坐。
现在假设1号乘客疯了（其他人没疯），他会在100个座位中随便选一个座位坐下，问：第100人正确坐到自己坐位的概率是多少？（也可推广到n名乘客n个座位的情况）

这里我们可以用递归的思想去计算。
首先假设第一位乘客成功坐到了一号位，那么剩下的乘客都会坐在自己的位置上，于是乎100号乘客坐到自己位置的概率即为 $\frac{1}{100}$
假设第二位乘客坐在了二号位，此时还剩下一号位和三号以上的位置，此时我们可以将一号位作为二号位，如果二号成功坐到了一号位，那么100号乘客坐到自己位置的概率即为 $\frac{1}{99}$，这个过程是不是很相似。我们可以将二号乘客作为醉汉，那么可以看做有99个乘客，第一位乘客疯了的问题。

假设一共有N位乘客和N位座位，可以得到：
$P_N=\frac{1}{N}+\frac{1}{N}(P_{N-1}+P_{N-2}+......+P_2)$
$P_2=\frac{1}{2}$
$P_3=\frac{1}{3}+\frac{1}{3}\ast \frac{1}{2}=\frac{1}{2}$
…
$P_N=\frac{1}{2}$
那么无论乘客有多少人，最后一位乘客坐在自己位置的概率都为1/2。

题目2: 如何在10亿个数中找到前1000大的数

分治基数排序法：随机选择一个数t，然后对于整个数组进行partition。大的在左侧，小的在右侧。
如果左边数量大于N，在前一部分进行partition。
如果左边数量小于N，就在后一部分进行partition。
分布式思想 数据读写，将数据切分，在多台机器上计算前1000大的数，然后再进行汇总。
堆排序 在内存中维护一个1000个数的小顶堆(左右节点都要比根节点大)，如果比堆顶小，丢弃，如果比堆顶大，替换头结点，继续维持为小根堆。