阿里笔试两道编程题

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

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


第一道.

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

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


第二道.

小伙纸要去跟 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$

Read More

水塘抽样

先看几个问题:

  • 从一个很大的源代码中随机选取一行。
  • 对一个长度未知的链表随机选取其中的k个节点。

水塘抽样(Reservoir sampling) 是随机算法的一种。其目的在于从包含n个项目的集合S中选取k个样本,其中n为一很大或未知的数量,尤其适用于不能把所有n个项目都存放到主内存的情况。

考虑k=1的情况。算法如下:

  • Keep the first item in memory.
  • When the i-th item arrives (for i>1):with probability 1/i, keep the new item (discard the old one)with probability 1-1/i, keep the old item (ignore the new one)

So:

  • when there is only one item, it is kept with probability 1;
  • when there are 2 items, each of them is kept with probability 1/2;
  • when there are 3 items, the third item is kept with probability 1/3, and each of the previous 2 items is also kept with probability (1/2)(1-1/3) = (1/2)(2/3) = 1/3;
  • by induction, it is easy to prove that when there are n items, each item is kept with probability 1/n.

考虑一般情况,Algorithm R by Jeffrey Vitter

Read More

KMP

复习一下KMP.

失配时:

  • i 不变,j 退回到 next[j] 位置;
  • 当 j 退到模式串第一个位置时,i、j 同时 +1. 表示s[i]和t[0]不匹配时,从s[i+1]重新匹配。

get_next :

1) 下标从0开始:

2) 下标从1开始:

Read More

爬取微信公众号历史文章

想要获取微信公众号的历史文章,需要三个参数:__bizuinkey

这里困难的是key参数不是固定不变的,存在有效期(大概几十分钟)。那么就有两个问题:

1)如何获取这三个参数?

2)如何实时更新文章列表?(更新key)

目前找到的方法都是手动获取的,不知道传送门是如何做到实时更新?

参数获取

1)间接爬 搜狗微信搜索平台

这个方式我没试过,据说不稳定,而且搜狗貌似做了隐藏。

2)通过手机微信客户端或mac微信客户端,进入某个公众号,点击“查看历史消息”,获取链接。这里又有两种方式:

(a) 利用微信客户端自带的分享功能,通过邮件或QQ分享出链接(直接复制链接不行)。

(b) 让手机和电脑处于同一局域网,通过手机抓包获取链接,工具如fiddler(可参见 《Fiddler手机抓包》)。

url一般为如下形式:

Read More

^