阿里笔试没做啊, 感谢同学过来分享讨论.

感觉其中的概率题还是挺有意思的, 赶紧记录一下。思路不一定对… (汗…


第一道.

给一个矩形, 再给一堆矩形里的线段, 问是否存在一条路线可以从左下角走到右上角(要求不穿过线段).

思路: 用并查集把两条相交的线段作为一个集合, 然后对每个集合求上下左右边界, 判断这个子矩阵是否截断了从左下角走到右上角的路径.


第二道.

小伙纸要去跟 n 个妹纸相亲, 每次随机见一个妹纸(可能是之前已经见过的). 问至少相亲几次使得这 n 个妹纸都见过.

思路: 得益于之前做的微软第一题, 感觉有点像, 但也不知道是不是最优解法…

假如当前已经见了 k 个妹纸, 要见第 k+1个妹纸时, 相亲次数的期望值为: ∑∞i=1i(kn)i−1n−kn. (这个公式怎么来? 参考之前微软那张树的图就能推出来)

另 p=k/n, 则上式为

$(1-p)\sum_{i=1}^\infty i*p^{i-1}=(1-p)(\sum_{i=1}^\infty p^i)’=(1-p)(\lim_{n \rightarrow \infty}p\frac{1-p^n}{1-p})’=(1-p)(\frac{p}{1-p})’=1-p$


可以看出都想复杂了…

假如当前已经见了 k 个妹纸, 则能见到第 k+1个妹纸的概率为$\frac{n-k}{n}$, 即仅相亲一次见到妹纸的个数的期望为 $1\times \frac{n-k}{n}+0 \times \frac{k}{n}=\frac{n-k}{n}$.

故要见 n 个妹纸, 相亲次数至少为: $\sum_{i=0}^{n-1}\frac{n}{n-k}$