九月十月百度，迅雷，华为，阿里巴巴，最新校招笔试面试五十题

题记

    本博客自2010年10月11日开通以来，已经帮助了一大批人找到工作，特别是连续三年在每一年的9、10月份陪伴了至少三届毕业生找工作的旅程，包括校招中的笔试面试，今年也不会例外，我会在本博客开通3周年之际一如既往的陪伴大家一起成长。

    本文所整理的全部笔试面试题要么来源于我群内群友们的分享，要么摘自论坛或博客，所有原题均来自网络。虽然本文中整理的绝大部分笔试面试题偏算法（自己特意为之之故），但不论是哪一年的校招，一般说来，笔试偏基础（尤其是选择题部分，涵盖语言，计算机组成原理、操作系统、网络协议、数据库、概率期望等知识），而面试则偏算法（且极具针对性的根据简历提问），且无论是笔试还是面试，两者都很看重你的实际编程能力，希望大家知晓。

   OK， 本文会尽量保持每天更新一道新的笔试或面试题，直到10月底（更欢迎各位通过微博私信http://weibo.com/julyweibo，或邮箱zhoulei97@aliyun.com提供题目，亦可直接评论于本文下），如果大家对以下任何一题中有任何思路，包括参考题解中有任何错误，欢迎随时评论于本文之下，或show me your code！谢谢。

九月迅雷，华为，阿里巴巴，最新笔试面试十题

1. 8月15日，百度2道面试题： 1、来自《编程之美》的概率题：一个桶里面有白球、黑球各100个，现在按下述规则取球：的     i 、每次从通里面拿出来两个球；     ii、如果取出的是两个同色的求，就再放入一个黑球；     ii、如果取出的是两个异色的求，就再放入一个白球。 问：最后桶里面只剩下一个黑球的概率是多少？ 2、算法题：给你一个自然数N，求[6,N]之内的所有素数中，两两之和为偶数的那些偶数。
2. 9月5日，华为2014校园招聘的机试题目 通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。 压缩规则：     1、仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。     2、压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。 要求实现函数：       void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);     输入pInputStr：  输入字符串lInputLen：  输入字符串长度     输出 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长； 注意：只需要完成该函数功能算法，中间不需要有任何IO的输入输出 示例      输入：“cccddecc”   输出：“3c2de2c”     输入：“adef”     输出：“adef”     输入：“pppppppp” 输出：“8p”
3. 9月6日，网新恒天2014校园招聘笔试编程题 已知memcpy的函数为： void* memcpy(void *dest , const void* src , size_t count)其中dest是目的指针，src是源指针。不调用c++/c的memcpy库函数，请编写memcpy。 点评：老题，参考答案如下
   1. //copyright@July 2013/9/24  
   2. void* memcpy(void *dst, const void *src, size_t count)      
   3. {      
   4.     //安全检查  
   5.     assert( (dst != NULL) && (src != NULL) );      
   6.   
   7.     unsigned char *pdst = (unsigned char *)dst;      
   8.     const unsigned char *psrc = (const unsigned char *)src;      
   9.   
   10.     //防止内存重复  
   11.     assert(!(psrc4->5 输出：1->2->3->4->5 2、编写程序，在原字符串中把尾部m个字符移动到字符串的头部，要求：长度为n字符串操作时间复杂度为O(n),时间复杂度为O(1)。 如：原字符串为”Ilovebaofeng”，m=7，输出结果：”baofengIlove”。 点评：还是类似编程艺术第1章左旋字符串：http://blog.csdn.net/v_JULY_v/article/details/6322882。 3、暴风影音的片源服务器上保存着两个文件a和b，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出a,b文件共同的URL。要求：算法设计。 点评：上述第3题等海量数据处理面试题，请参见此文第第一部分第6题：http://blog.csdn.net/v_july_v/article/details/7382693。
   12. 关于linux内核的几个面试问题： 1、Linux中主要有哪几种内核锁？ 2、Linux中的用户模式和内核模式是什么含意？ 3、用户进程间通信主要哪几种方式？ 4、有哪几种内存分配函数？
   13.  微软一面：输入两个数，相加求和，二进制输出。
   14. 阿里巴巴面试： 阿里的log文件如下，有三个字段：time（登陆或登出时间点）+uid+login或logout，每条记录按时间顺序排列。问题如下：给定一个时间点T，统计在线人数。  点评：参考分析请见http://blog.csdn.net/tnndye/article/details/12784237。
   15. 10月8日，百度移动开发-上海站笔试/面试题 1、三色球排序的问题，相同的球放到一起，让你按顺序输出红白蓝三种颜色的球，可以用012来表示，要求只能扫描一次数组。 点评：荷兰国旗问题，参见此文第8小节：http://blog.csdn.net/v_july_v/article/details/6211155。 2、实现C的strstr 点评：手写字符串处理相关函数是面试中极为常见的一类题型。 功能：从字符串str1中查找是否有字符串str2， -如果有，从str1中的str2位置起，返回str1中str2起始位置的指针，如果没有，返回null。 给两份参考代码，一份是C代码：
       1. char *mystrstr(char *s1 , char *s2)  
       2. {  
       3.     if(*s1==0)  
       4.     {  
       5.         if(*s2)   
       6.             return(char*)NULL;  
       7.         return (char*)s1;  
       8.     }  
       9.     while(*s1)  
       10.     {  
       11.         int i=0;  
       12.         while(1)  
       13.         {  
       14.             if(s2[i]==0)   
       15.                 return s1;  
       16.             if(s2[i]!=s1[i])   
       17.                 break;  
       18.             i++;  
       19.         }  
       20.         s1++;  
       21.     }  
       22.     return (char*)NULL;  
       23. }  
       一份是C++代码：
       1. //copyright@caopengcs 2013/10月  
       2. class Solution {  
       3. public:  
       4.     char *strStr(char *haystack, char *needle) {  
       5.         // Start typing your C/C++ solution below  
       6.         // DO NOT write int main() function  
       7.         int i,j;  
       8.         for (i = j = 0; haystack[i] && needle[j];) {  
       9.             if (haystack[i] == needle[j]) {  
       10.                 ++i;  
       11.                 ++j;  
       12.             }  
       13.             else {  
       14.                 i = i - j + 1;  
       15.                 j = 0;  
       16.             }  
       17.         }  
       18.         return needle[j]?0:(haystack + i - j);  
       19.     }  
       20. };  
       3、写一个memmove的函数 点评：手写常见字符串处理函数是面试官很喜欢考的一类题型。
   16. 10月9日，暴风影音校招研发笔试 1、给定字符串A和B，输出A和B中的第一个最长公共子串，比如A=“wepiabc B=“pabcni”，则输出“abc”。 2、TCP建立连接的3次握手过程？若最后一次握手失败，会怎样处理？
   17. 蜻蜓FM2014校招研发笔试
   18. 10月11日，腾讯web前端面试 一个数组 var arr = ['abc','ddadbc','adbdcd','abcqew'.......] 长度一万，  用最有效率的方法计算出包含被元素出现最多的。
   19. 单机5G内存，磁盘200T的数据，分别为字符串，然后给定一个字符串，判断这200T数据里面有没有这个字符串，怎么做？ 如果查询次数会非常的多, 怎么预处理？ 点评：如果数据是200g且允许少许误差的话，可以考虑用布隆过滤器Bloom Filter：http://blog.csdn.net/v_july_v/article/details/6685894。但本题是200T，得另寻良策。 OK，以下是@cy 提供的题解（暴露出的一个问题是题意不是特别明确，因为题解中有不少自己的假设，所以日后各位面试时一定要跟面试官彻底弄清题意再作答，包括各种使用条件）： “①. 内存和数据比是 5GB / 200TB, 约为 1 比 4w, 所以trie啥的就不用想了, 唯一的就是hash. ②. 简单的假设每个字符串是相对短的(只要不会超过5GB)     1. 几MB, 甚至百MB的字符串也能处理, 但是确实对最终的效果有很大影响, 如果只是部分case特别大,可以特殊处理下. ③. 一个字符串块 在内存中需要一个 条目 来标识     1. value 需要 8 字节, key约为4字节         1. 200TB总共有 200 * 2^40 位, 地址空间至少为48个bit, 存储长度用16bit则一个条目的value 需要8个字节     1. 这里的长度是用来存一个 字符串块 的长度, 单位可以优化为KB, 甚至MB, 16bit肯定是够的     1. key用4个字节有些紧张, 可以考虑占用部分长度的位     1. 长度也可以不在条目中出现, 而是在块头出现, 但这样取块的时候有可能浪费, 也有可能要取多次.     2. 所谓一个 字符串块 就是hash值相同的字符串挨个存在一起, 从而得到的字符串块. ④. 这样的话, 5GB 可以存放最多 5GB / 8 约为 4亿个条目. ⑤. 把原来的200TB字符串挨个的hash, 并按hash排序后, 存起来, 建立索引.      1. hash值可以用md5之类的散列到足够开, 然后 mod 4亿值来求 ⑥. 根据重排后的文件, 建立索引, key为hash值, value为前面说到的, 该hash对应字符串块在文件中的偏移, 和 块的长度. ⑦查询时, 根据hash值, 找到该字符串可能在的字符串, 然后将整个字符串读出来, 用kmp比较即可.  200TB的数据, 被划到 4亿 个字符块当中, 平均一块应该在 800KB 附近, 考虑到hash不均衡, 一般也就是几MB的样子,  比较起来应该还OK.  ⑧其他的小优化点:      1. 不是一个文件, 而是若干个文件, 但是不影响偏移的编号     1. 为什么做hash再分块? 避免通用前缀过多,导致分块极不均匀     1. 大长的字符串容易导致 字符串块 暴大, 可以考虑分为若干小串, 同时记录原来的位置, 知道是否是一个整串     1. 压缩...留一些空间做常用查询串的缓存... ⑨再说怎么优化这个预处理的排序过程. 每次读5GB的数据进来, 算好hash分好桶, 这种OK吧, 然后按桶回写到下去, 这里也是批量写的. 处理完继续处理下一个5GB, 全部处理完后, 再做归并, 搞几轮后, 就OK了嘛. 当然, 为了把内存中排序时浪费的IO补回来, 可以 并行做, 一个在算的时候,另一个在读....”。
   20. 10月12日，百度一面 JAVA里面的线程同步机制、异常处理机制、集合类、简单的设计模式、hashmap和hashtable的区别，及HashMap和ConcurrentHashMap的区别。 点评：关于hashmap和hashtable的区别，请看上文第13题，其余请自己查阅相关书籍。
   21. stat、SDE、PM、DS等相关职位的面试题 1、有一组数据，很长，有ID，经纬度，时间4个变量。 怎么找出两人是否有一面之缘。怎么找出所有relationship（定义是在100米范围内一起度过1小时以上）。 2、怎么找出竞争对手购买了哪些搜索关键词。 3、怎么判断两个TB级别的文本是否雷同，是否近似。 4、怎么用C实现SQL的join功能。 5、怎么最快的在一个大文本里面搜索字符串。 6、coding计算斐波那契数列。 更多请参看：http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000300&itemidx=1&sign=173a62e0db86cb4c76a0bb1e9c22f3e5。
   22. 10月12日，网易游戏专业一面   1、怎么判断单链表有没有环   2、怎么判断两个无环单链表是否相交   3、101个硬币中有一个假币，有一个无砝码的天平，称两次，判断假币比真币重还是轻。 点评：老掉牙的题，没点评的欲望，原文请看：http://blog.csdn.net/cqsctlsss/article/details/12747631。
   23. 10月13日，百度笔试题： 1、 给出数组A={a_0,a_1,a_2,...,a_n}（n是可变的），打印出所有元素的组合 2、 数组A中任意两个相邻元素大小相差1，现给定这样的数组A和目标整数t，找出t在数组A中的位置。 3、 求二叉树的面积（高乘宽），高为二叉树根到叶子节点的最大距离，宽慰二叉树最多的节点数。 4、给了一个百度地图的截图，对于地图上的某一点，需要在地图上标注该点的信息，将信息抽象成一个矩形，可以在该点的左边标记，也可以在该点右边标记。但是任意两点标记后的矩形是不能有覆盖的，否则删除其中一个点     问题1，现给一固定区域，有n个点，设计一个算法，要求标记足够多的点     问题2，当点足够多时候，算法会遇到性能瓶颈，需要对算法重新优化。 更多题目请参见：http://blog.csdn.net/xyanghomepage/article/details/12687771。
   24. 腾讯笔试题两道 1、有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。 点评：老题，与caopengcs讨论后，得出具体思路为： ①先把100W个关键字hash映射到小文件，根据题意，100W*50B = 50*10^6B = 50M，而内存只有1M，故干脆搞一个hash函数 % 50，分解成50个小文件； ②针对对每个小文件依次运用hashmap(key，value)完成每个key的value次数统计，后用堆找出每个小文件中value次数最大的top 10； ③最后依次对每两小文件的top 10归并，得到最终的top 10。 注：很多细节需要注意下，举个例子，如若hash映射后导致分布不均的话，有的小文件可能会超过1M，故为保险起见，你可能会说根据数据范围分解成50~500或更多的小文件，但到底是多少呢？我觉得这不重要，勿纠结答案，虽准备在平时，但关键还是看临场发挥，保持思路清晰关注细节即可。OK，更多类似题目参见此文：http://blog.csdn.net/v_july_v/article/details/7382693。 2、求二叉树的任意两个节点的最近公共祖先。 点评：何谓最低公共祖先，如下图所示：节点1和节点7的最低公共祖先便是5 点评：此题看似简单，实则不简单，下面参考引用《Cracking the Coding Interview》一书上的解法： 说简单是因为如果这棵树是二叉查找树，则最低公共祖先t必在两个节点p和q的中间处，即p