stl,,面试重点

1、stl,面试重点篇一：有点难度的C+面试题篇二：各大IT公司笔试面试题目20XX 各大IT公司笔试面试题目分类： C+ 语法知识20XX-02-12 11:05 563人阅读 评论 收藏 举报百度面试题1、进程切换需要注意哪些问题？保存处理器PC寄存器的值到被中止进程的私有堆栈；保存处理器PSW寄存器的值到被中止进程的私有堆栈； 保存处理器SP寄存器的值到被中止进程的进程控制块；保存处理器其他寄存器的值到被中止进程的私有堆栈； 自侍运行进程的进程控制块取SP值并存入处理器的寄存器SP； 自侍运行进程的私有堆栈恢复处理器各寄存器的值；自侍运行进程的私有堆栈中弹出PSW值并送入处理器的PSW； 自侍运行进程的私有堆栈中弹出PC值并送入处理器的PC。2、输入一个升序数组，然后在数组中快速寻找两个数字，其和等于一个给定的值。这个编程之美上面有这个题目的，很简单的，用两个指针一个指向数组前面，一个指向数组的后面，遍历一遍就可以了。3、有一个名人和很多平民在一块，平民都认识这个名人，但是这个名人不认识任何一个平民，任意两个平民之间是否认识是未知的，请设计一个算法，快速找出这些人中的那个名人。 已知

2、已经实现了一个函数 bool know 这个函数返回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。方法2：使用二分查找法，对1到N之间的数字进行判断。复杂度为O。方法3：由于2=n2 + 2n + 1。= .= 1 + + + . +注意到这些项构成了等差数列（每项之间相差2）。所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 -

3、5 . 和0的关系。如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。复杂度为O。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。例如：32 = 9 = 1 + 2*1+1 + 2*2+1 = 1 + 3 + 542 = 16 = 1 + 2*1 + 1 + 2*2+1 + 2*3+1view plain1.2.3.4.5.6.7.8.9. int square int i = 1; n = n - i; while i += 2; n -= i; 10. if /是某个数的平方 1;12. else /不是某个数的平方 0;14. 百度校园招聘会笔试题一、算法设计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，但

4、因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/（m+i）= /，所以每个query被抽中的概率是相等的。3、C+ STL中vector的相关问题：（1）、调用push_back时，其内部的内存分配是如何进行的？（2）、调用clear时，内部是如何具体实现的？若想将其内存释放，该如何操作？vector的工作原理是系统预先分配一块CAPACITY大小的空间，当插入的数据超过这个空间的时候，这块空间会让某种方式扩展，但是你删除数据的时候，它却不会缩小。vector为了防止大量分配连续内存的开销，

5、保持一块默认的尺寸的内存，clear只是清数据了，未清内存，因为vector的capacity容量未变化，系统维护一个的默认值。有什么方法可以释放掉vector中占用的全部内存呢标准的解决方法如下templatevoid ClearVectorvector vtTemp;事实上，vector根本就不管内存，它只是负责向内存管理框架acquire/release内存，内存管理框架如果发现内存不够了，就malloc，但是当vector释放资源的时候, stl根本就不调用free以减少内存，因为内存分配在stl的底层：stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源，所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off一般的STL内存管理器allocator都是用内存池来管理内存的，所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量，而不是真的把内存归还给系统。这样做一是为了避免内存碎片，二是提高了内存申请和释放的效率不用每次都在系统内存里寻找一番。二、系统设计正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过

6、滤系统，设服务器在某一刻收到客户端A的一个请求，则1分钟内的客户端任何其它请求都需要被过滤，现知每一客户端都有一个IPv6地址可作为其ID，客户端个数太多，以至于无法全部放到单台服务器的内存hash表中，现需简单设计一个系统，使用支持高效的过滤，可使用多台机器，但要求使用的机器越少越好，请将关键的设计和思想用图表和代码表现出来。三、求一个全排列函数：如p输出：123、132、213、231、321、323求一个组合函数如p输出：1、2、3、1,2、2,3、1,3、1,2,3这两问可以用伪代码。网易游戏校园招聘会笔试题1、对于一个内存地址是32位、内存页是8KB的系统。0X0005F123这个地址的页号与页内偏移分别是多少。2、如果X大于0并小于65536，用移位法计算X乘以255的值为： -XX; p1+; p = static_cast; printf;8、在一冒险游戏里，你见到一个宝箱，身上有N把钥匙，其中一把可以打开宝箱，假如没有任何提示，随机尝试，问：（1）恰好第K次（1=using namespace std;class Apublic: A cout篇三：面试题目手机分配短

7、讯id的面试题目 20XX-09-03 01:37 by Milo Yip, 10926 阅读, 18 评论, 收藏, 编辑 看过上回厘清需求篇，读者想到多少个解呢？本篇首先谈及一些基本分析，之后会按两种API设计，分别描述多个解。虽然面试时或许不能进行实际测试，但本文还是给出PC上的效能测试结果。最后分析比较各解之优劣作为总结。 问题分析原来的问题是要从一个无序ids数组里分配一个id。我们可以用数学方式去更清楚地说明这个问题。设m = 256 为所有id的个数，集合合，为所有id的集合。那么，给定一个已分配id的集，本题目可表示为，求一个，符合条件: 减号是补集的意思，即x属于U但不属于A。上回的对答已确定在。此外，这个条件又可以写成: ，即必然存以上两种表达式可说明此问题的两种解法，一种编程方向是查找U集里有没有不属于A的id，而另种是计算A的补集再取出其中一个id。纯函数API的解实现程序之前，如果可以，应先写测试函数。笔者认为，若面试者在情况容许下，也可在解答题目之前，写下测试程序。如果有多个面试者能同样解题，或许同时写下测试程序的面试者能脱颖而出。测试函数为了简单起见，笔者

8、使用了assert 来检测正确性，只于Debug版本有效。而Release版本则用来测试效能。由于U集合的子集合很多。所以，只能够举出随机的集合以作测试。 ，不可能穷举所有可能集合。以下是一些常数及类型声明，TEST_COUNT是测试次数，而TEST_REPEATCOUNT是为了测试效能时，重覆测试的次数: 1 #define M 256 / ID的数2 目，且所有ID在0, M)的区3 间内45 #define TEST_COUNT 100006 #ifdef NDEBUG7 #define TEST_REPEATCOUNT8 1009 #else10 #define TEST_REPEATCOUNT11 112 #endif13typedef unsignedchar byte;typedef unsignedlong dword;typedef byte;首先，写一个帮助函数测试某id是否在ids集合之内:笔者首先写了一个测试平均情况的测试平台函数:1 / 测试平均情况2 void test_average 4 assert;56 byte idsM;78 for9idsi = i;1011 srand; / 使每次测试的伪随机数相12 同1314 size_t n = 0;15 for 17random_shuffle; /18 把整个数组洗牌1920for 22 byte id = idalloc;23 id;24 assert);2627 / 测试是否最小的id28 forasserti);n = % M;简单解释。首先，把ids数组填入所有id值。利用random_shuffle 把把整个ids数组洗牌，而n则是在0, M)区间里循环递增。由于笔者给出的解，都能传回最小的id，所以也会测试这条件。而最坏情况，就是ids含无序的

《stl,,面试重点》由会员F****n分享，可在线阅读，更多相关《stl,,面试重点》请在金锄头文库上搜索。