百度面试笔试题合集~~

1 、进程切换需要注意哪些问题？

保存处理器 PC 寄存器的值到被中止进程的私有堆栈；保存处理器 PSW 寄存器的值到被中止进程的私有堆栈；保存处理器 SP 寄存器的值到被中止进程的进程控制块；

保存处理器其他寄存器的值到被中止进程的私有堆栈；自待运行进程的进程控制块取 SP 值并存入处理器的寄存器 SP ；   自待运行进程的私有堆栈恢复处理器各寄存器的值；

自待运行进程的私有堆栈中弹出 PSW 值并送入处理器的 PSW ；自待运行进程的私有堆栈中弹出 PC 值并送入处理器的 PC 。

2 、输入一个升序数组，然后在数组中快速寻找两个数字，其和等于一个给定的值。

这个编程之美上面有这个题目的，很简单的，用两个指针一个指向数组前面，一个指向数组的后面，遍历一遍就可以了。

3 、有一个名人和很多平民在一块，平民都认识这个名人，但是这个名人不认识任何一个平民，任意两个平民之间是否认识是未知的，请设计一个算法，快速找个这个人中的那个名人。   已知已经实现了一个函数   bool know(int a,int b) 这个函数返回 true 的时候，表明 a 认识 b ，返回 false 的时候表明 a 不认识 b 。

思路：首先将 n 个人分为 n/2 组，每一组有 2 个人，然后每个组的两个人调用这个 know 函数，假设为 know （ a ， b ），返回 true 的时候说明 a 认识 b ，则 a 肯定不是名人， a 可以排除掉了，依次类推，每个组都调用这个函数依次，那么 n 个人中就有 n/2 个人被排除掉了，数据规模将为 n/2 。同理在剩下的 n/2 个人中在使用这个方法，那么规模就会将为 n/4 ，这样所有的遍历次数为 n/2+n/4+n/8+........ 这个一个等比数列，时间复杂度为 o （ n ）。

4 、判断一个自然数是否是某个数的平方。当然不能使用开方运算。

方法 1 ：
遍历从 1 到 N 的数字，求取平方并和 N 进行比较。
如果平方小于 N ，则继续遍历；如果等于 N ，则成功退出；如果大于 N ，则失败退出。
复杂度为 O(n^0.5) 。

方法 2 ：
使用二分查找法，对 1 到 N 之间的数字进行判断。
复杂度为 O(log n) 。

方法 3 ：
由于
(n+1)^2
=n^2 + 2n + 1 ，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)

注意到这些项构成了等差数列（每项之间相差 2 ）。
所以我们可以比较 N-1 ， N - 1 - 3 ， N - 1 - 3 - 5 ... 和 0 的关系。
如果大于 0 ，则继续减；如果等于 0 ，则成功退出；如果小于 0 ，则失败退出。
复杂度为 O(n^0.5) 。不过方法 3 中利用加减法替换掉了方法 1 中的乘法，所以速度会更快些。

例如： 3^2 = 9 = 1 + 2*1+1 + 2*2+1 = 1 + 3 + 5

4^2 = 16 = 1 + 2*1 + 1 + 2*2+1  + 2*3+1

view plain

百度校园招聘会笔试题

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

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

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

思路：如果用户查询的数量小于 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 被抽中的概率是相等的。

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

二、系统设计
正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，设服务器在某一刻收到客户端 A 的一个请求，则 1 分钟内的客户端任何其它请求都需要被过滤，现知每一客户端都有一个 IPv6 地址可作为其 ID ，客户端个数太多，以至于无法全部放到单台服务器的内存 hash 表中，现需简单设计一个系统，使用支持高效的过滤，可使用多台机器，但要求使用的机器越少越好，请将关键的设计和思想用图表和代码表现出来。

三、求一个全排列函数：
如 p([1,2,3]) 输出：
[123] 、 [132] 、 [213] 、 [231] 、 [321] 、 [323]
  求一个组合函数
如 p([1,2,3]) 输出：
[1] 、 [2] 、 [3] 、 [1,2] 、 [2,3] 、 [1,3] 、 [1,2,3]
这两问可以用伪代码。