2015百度校招笔试真题以及解析（一）

1、为分析用户行为，系统常需存储用户的一些 query ，但因 query 非常多，故系统不能全存，设系统每天只存 m 个 query ，现设计一个算法，对用户请求的 query 进行随机选择 m 个，请给一个方案，使得每个 query 被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。

解析2：

大致伪代码如下：
int count = 1;
string query[m+1]; //为了方便理解，从1开始存
while(scanf("%s",&cur_query)!=EOF) {
      count++;
      if(count <= m) {  // 如果输入小于m，直接存。
         query[count] = cur_query;
      } else {  // 剩余的，就随机一个数，并交换。具体为何，在下述证明可见
         int M = random(1, count);
         if( M < m) {
             query[M] = cur_query;
         }
}

证明每个query被抽中的概率相等：（假设总请求量为N）

1、如果N<=m，每个query都被存下来，那么query被抽中保存下来的概率均为1。

2、N > m， 将query分成前m个和后m个来看（其实也就对应伪码中if/else 两种处理方式）：

对于第i个数(i < m)，在前m步被选中的概率仍是1.但是从第m+1步，i就有可能被替换掉，被替换掉的概率是
1/count。第m+1步，count = m+1,所以不被替换的概率为m/m+1。接下来的也就是m+1/m+2、m+2/m+3 。
那么读到第N个数时， 显然第i个数被选中的概率 = 每一步都不替换的概率,即 m/m+1 * m+1/m+2 … n-1/n =
m/n。

对于第i个数(i >= m)时。要想被选中的概率为，首先，在它出现的那一次,M的取值要小于k，这个概率就是m/count.
接下来每一步都不被替换的计算过程跟上面一样。所以此时第i个数被选中的概率 = m/count * count /count+1
*…*n-1/n = m/n所以用这种方法，概率是相同的。

思路：这个使用数学中的极坐标来解决，先调用 [s1 ， t1] 随机产生一个数 r ，归一化后乘以半径，得到 R* （ r-s1 ） / （t1-s1 ），然后在调用 [s2 ， t2] 随机产生一个数 a ，归一化后得到角度： 360* （ a-s2 ） / （ t2-s2> ）。

vector 为了防止大量分配连续内存的开销，保持一块默认的尺寸的内存， clear 只是清数据了，未清内存，因为 vector 的 capacity 容量未变化，系统维护一个的默认值。

有什么方法可以释放掉 vector 中占用的全部内存呢 ?

标准的解决方法如下：

template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
veTemp.swap( vt );
}

事实上， vector 根本就不管内存，它只是负责向内存管理框架 acquire/release 内存，内存管理框架如果发现内存不够了，就 malloc ，但是当 vector 释放资源的时候 ( 比如 destruct), stl 根本就不调用 free 以减少内存，因为内存分配在 stl 的底层： stl 假定如果你需要更多的资源就代表你以后也可能需要这么多资源 ( 你的 list, hashmap 也是用这些内存 ) ，所以就没必要不停地 malloc/free 。如果是这个逻辑的话这可能是个 trade-off。

一般的 STL 内存管理器 allocator 都是用内存池来管理内存的，所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量，而不是真的把内存归还给系统。这样做一是为了避免内存碎片，二是提高了内存申请和释放的效率 —— 不用每次都在系统内存里寻找一番。