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

布满荆棘的人生 2022-07-13 15:14 221阅读 0赞

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

--------------------

**解析1：**思路：如果用户查询的数量小于 m ，那么直接就存起来。如果用户查询的数量大于 m ，假设为 m+i ，那么在 1—–m+i 之间随机产生一个数，如果选择的是前面 m 条查询进行存取，那么概率为 m/ （ m+i ），如果选择的是后面 i 条记录中的查询，那么用这个记录来替换前面 m 条查询记录的概率为 m/ （ m+i ） \* （ 1-1/m ） =(m-1)/(m+i) ，当查询记录量很大的时候， m/ （ m+i ） == (m-1)/(m+i) ，所以每个 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所以用这种方法，概率是相同的。

--------------------

**2、设 rand （ s ， t ）返回 \[s,t\] 之间的随机小数，利用该函数在一个半径为 R 的圆内找随机 n 个点，并给出时间复杂度分析。**

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

--------------------

**3 、 C++ STL 中 vector 的相关问题：**   
**（ 1 ）、调用 push\_back 时，其内部的内存分配是如何进行的？**  
**（ 2 ）、调用 clear 时，内部是如何具体实现的？若想将其内存释放，该如何操作？**

--------------------

vector 的工作原理是系统预先分配一块 CAPACITY 大小的空间，当插入的数据超过这个空间的时候，这块空间会让某种方式扩展，但是你删除数据的时候，它却不会缩小。

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