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]、[312] 求一个组合函数。
方法1：依次从字符串中取出一个字符作为最终排列的第一个字符，对剩余字符组成的字符串生成全排列，最终结果为取出的字符和剩余子串全排列的组合。
优点：该方法易于理解，但无法移除重复的排列，如：s=\，会生成两个“AAB”。 方法2：利用交换的思想，具体见实例，但该方法不如方法1容易理解。
我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。
既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。
基于前面的分析，我们可以得到如下的参考代码： 如p([1,2,3])输出：
[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3] 这两问可以用伪代码。
百度笔经2
第一大题：1.extern \含义，应用在什么场景下? 2.经典设计模式写出至少两个，解释一下，最好写出伪代码 3.TCP连接中的wait_time含义，应用场景，好处和坏处 第二大题
1.一个任务处理器吧，N个任务，任务之间会有依赖关系。比如A依赖B，A需要B完成之后才能开始，写出算法，找到合适的任务顺序。说明算法的时间复杂度和空间复杂度。
2.一个英文文本，含有字母，“.\和\和空格。写出函数，这个函数用于找出英文文本中含有的完整句子的个数。含有至少一个字母并且以句号\结尾的视为一个完整的句子。写出完整的代码。 第三大题：系统设计题
1.实时监控系统。有很多记录，记录中含有url,时间段，ip 该系统可以同时实现如下两个查询
查询一：已知时间段（精确到分钟）和某个url，求满足条件的总流量 查询二：已知时间段（精确到分钟）和某个ip,求满足条件的总流量
百度笔经3 一、简答
1、系统又很多任务，任务之间有依赖，比如B依赖于A，则A执行完后B才能执行
（1）不考虑系统并行性，设计一个函数（Task *Ptask,int Task_num）不考虑并行度，最快的方法完成所有任务。
（2）考虑并行度，怎么设计 typedef struct{ int ID; int * child; int child_num;
}Task; 提供的函数:
bool doTask(int taskID);无阻塞的运行一个任务；
int waitTask(int timeout);返回运行完成的任务id，如果没有则返回-1； bool killTask(int taskID);杀死进程
2、堆和栈的生命周期，内存分配性能，不同处，如果一般情况下要求1KB，偶尔需要100MB的缓存空间怎么设计？
二、必答题（各种const）
1、解释下面ptr含义和不同（好像是。。。。题干了大概意思是这样。下面应该没错） double* prt = &value const double* ptr = &value double* const ptr=&value const double* const ptr=&value 2、去掉const属性，例： const double value = 0.0f; double* ptr = NULL; 怎么才能让ptr指向value？ 三、算法设计
1、一个一维数轴上有不同的线段，求重复最长的两个线段。 例：a：1~3 b: 2~7 c：2~8 最长重复是b和c 2、有向带权图最短路径 四、系统设计
大概意思是：百度内部有一个类似cs系统的计算系统，由于大并发计算很耗资源，所有要设计一个缓存系统。c做缓存，配置2.66MHZ,3G内存，大概有1000w个查询，唯一的查询大概有500w。要缓存24小时。设计这个缓存系统的运行机制，算法等等东西。。。。。记不太清了。。。
腾讯笔经1
全卷100分，其中60分选择题，每题3分，40分填空题，每空4分，最后有三题编程附加题，腾讯说附加题仅作参考，不做计分排名用。 选择题第一题考extern的作用； 第二题考strstr函数的作用；
第三题考windows下线程什么优先级最高； 第四题考一个交换x,y值的函数的正确写法； 接下来的不是很记得了，内容大概有 析构函数/构造函数能不能被继承， 虚函数的继承， linux下fork的返回值，
unix下进程间通信最快是采取什么方法； const int* x和int* const x的区别，
int*p[4]的含义；
指针的自加和引用等等。。。
选择题就只记得这些了，下面说填空题； 第一题是问(++x)*(++x)和（x++）*（x++）的值；
第二题是给了一个二维数组a[2][3],然后定义了一个int*p[3],p=a;然后问*（*（p+1）+1）的值； 第三题是一个计算变量x的二进制数里面有多少个1的程序填空题，while循环里面进行的是x=x&(x-1); 第四题问inline的作用 第五题问ifndef的作用
第六题给了一个将链表逆序的程序，填空； 填空题就这些了，下面附加题； 附加题三题：
第一题是将两个已经排好序的链表合并成一个有序的链表；
第二题是用O(n)的时间复杂度和O(1)的空间复杂度对二叉树进行层次遍历；
第三题是一个逻辑推理题；四个人，其中一个是小偷，他们每人说了一句话，其中有三个人说真话，一个人说假话，让写代码判断哪个是小偷；
腾讯笔经2
1、下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是（B）
A、插入排序 B、堆排序 C、冒泡排序 D、快速排序 2、以下关于Cache的叙述中，正确的是（B）
A、CPU中的Cache容量应大于CPU之外的Cache容量 B、Cache的设计思想是在合理成本下提高命中率 C、Cache的设计目标是容量尽可能与主存容量相等
D、在容量确定的情况下，替换算法的时间复杂度是影响Cache命中率的关键因素
3、数据存储在磁盘上的排列方式会影响I/O服务的性能，一个圆环的磁道上有10个物理块，10个数据记录R1------R10存放在这个磁道上，记录的安排顺序如下表所示： 物理块
1 2 3 4 5 6 7 8 9 10 逻辑记录
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
假设磁盘的旋转速度为20ms/周，磁盘当前处在R1的开头处，若系统顺序扫描后将数据放入单缓冲区内，处理数据的时间为4ms（然后再读取下个记录），则处理这10个记录的最长时间为（C） A、180ms B、200ms C、204ms D、220ms 2+4+（（2+4）+2*8）*9=204
4、随着IP网络的发展，为了节省可分配的注册IP地址，有一些地址被拿出来用于私有IP地址，以下不属于私有IP地址范围的是（C）
A、10.6.207.84 B、172.23.30.28 C、172.32.50.80 D、192.168.1.100 私有IP地址共有三个范围段：
A、10.0.0.0~10.255.255.255 /8 B、172.16.0.0~172.31.255.255 /12 C、192.168.0.0~192.168.255.255 /16 5、下列关于一个类的静态成员的描述中，不正确的是（D） A、该类的对象共享其静态成员变量的值 B、静态成员变量可被该类的所有方法访问
C、该类的静态方法只能访问该类的静态成员变量 D、该类的静态数据成员变量的值不可修改
6、已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7计算散列地址，并散列存储在散列表A【0....6】中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（C） A、1.5 B、1.7 C、2.0 D、2.3
7、表达式“X=A+B*（C--D）/E”的后缀表示形式可以为（C）
A、XAB+CDE/-*= B、XA+BC-DE/*= C、XABCD-*E/+= D、XABCDE+*/= 8、（B）设计模式将抽象部分与它的实现部分相分离。
A、Singleton（单例） B、 Bridge（桥接） C、 Composite（组合） D、 Facade（外观） 10、C++将父类的析构函数定义为虚函数，下列正确的是哪个？ A、释放父类指针时能正确释放子类对象 B、释放子类指针时能正确释放父类对象 C、这样做是错误的 D、以上全错
C++的多态肯定是使用父类的指针指向子类的对象，所以肯定是释放子类的对象，如果不使用虚函数的话，父类的指针就只能够释放父类的对象。 11、下列哪一个不属于关系数据库的特点？ A、数据冗余度小 B、数据独立性高 C、数据共享性好 D、多用户访问
13、typedef char *String_t; 和 #define String_d char * 这两句在使用上有什么区别？
答：typedef char *String_t 定义了一个新的类型别名，有类型检查。而#define String_d char * 只是做了个简单的替换，无类型检查，前者在编译的时候处理，后者在预编译的时候处理。
同时定义多个变量的时候有区别，主要区别在于这种使用方式String_t a,b; String_d c,d; a,b ,c都是char*类型，而d为char类型
由于typedef还要做类型检查。。#define没有。。所以typedef比#define安全。。
14、到商店里买200的商品返还100优惠券（可以在本商店代替现金）。请问实际上折扣是多少？ 15、题目：已知rand7() 可以产生 1~7 的7个数（均匀概率），利用rand7() 产生rand10() 1~10（均匀概率）
记住这道题重点是：均匀概率
16、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。
17、对一个正整数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到1时操作停止，求经过9次操作变为1的数有多少个？ 第9次操作：结果1由2产生。1个被操作数 8：结果2只能由4产生。1个被操作数 7：结果4由8、3产生。2个
6：结果8由16、7产生；结果3由6产生。共3个
5：结果16由32、15产生；结果7由14产生；结果6由12、5产生。共5个… 每次操作，偶数（2除外）都由该数减1和该数的2倍得来，奇数只由该数的2倍得来 各次操作的操作对象个数为：1，1，2，3，5，8，13，21，34，…