九月十月百度人搜，阿里巴巴，腾讯华为小米搜狗笔试面试八十题
（ 算法&面试题交流与讨论：149977547；“2012年度CSDN博客之星”的活动，欢迎为我投上一票：http://t.cn/zjf4HEI，多谢）
自发表上一篇文章至今（事实上，上篇文章更新了近3个月之久），blog已经停了3个多月，而在那之前，自开博以来的21个月每月都不曾断过。正如上一篇文章支持向量机通俗导论（理解SVM的三层境界）末尾所述：”额，blog许久未有更新了，因为最近实在忙，无暇顾及blog。“与此同时，工作之余，也一直在闲心研究数据挖掘："神经网络将可能作为Top 10 Algorithms in Data Mining之番外篇第1篇，同时，k-最近邻法(k-nearest neighbor，kNN)算法谈到kd树将可能作为本系列第三篇。这是此系列接下来要写的两个算法，刚好项目中也要用到KD树“。
但很显然，若要等到下一篇数据挖掘系列的文章时（更新：下一篇kd树目前已经完成：http://t.cn/zjLQ8Ky），说不定要到年底去了，而最近的这段时间，9月、10月，正是各种校招/笔试/面试火热进行的时节，自己则希望能帮助到这些找工作的朋友，故此，怎能无动于衷，于是，3个多月后，blog今天更新了。
再者，虽然blog自10年10月开通至11年10月，一年的时间内整理了300多道面试题(这300道题全部集锦在此文中第一部分：http://blog.csdn.net/v_july_v/article/details/6543438)。但毕竟那些题已经是前年或去年的了，笔试面试题虽然每年类型变化不大，但毕竟它年年推陈出新，存着就有其合理性。
OK，以下是整理自8月下旬至10月份内的各大公司的笔试面试三十题（注：所有题目基本上全部为软件开发方向，题目来源：网络收集），相信一定能给正在参加各种校招的诸多朋友多少帮助，学习参考或借鉴（如果你手头上有好的笔试/面试题，欢迎通过微博私信：http://weibo.com/julyweibo，或邮箱：zhoulei0907@yahoo.cn发给我，或者干脆直接评论在本文下；同时，若你对以下任何一题有任何看法.想法.思路或建议，欢迎留言评论，大家一起讨论，共同享受思考的乐趣，谢谢）。
「我正在一点一点 做.整理下面的笔试面试题，欢迎读者朋友们跟我一起做，你可以把你的答案或代码直接评论在本文之下，也可以通过私信或邮件发给我，感谢诸位。同时，以下所有任何题目所给的点评里的答案，尤其是所给的外部链接若有任何问题，欢迎在本文评论下留言指正，谢谢。答题除了让你感受到思考的乐趣以外，还有奖哦，请君自看。July、二零一二年十月十一日」-
9月11日， 京东：
-
阿里巴巴二道题 第一道： 对于给定的整数集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都属于S。集合的元素个数小于等于 2000个 ，元素的取值范围在[- 2^28，2^28 - 1 ]，假定可用内存空间为100MB，硬盘使用空间无限大，试分析时间和空间复杂度，找出最快的解决方法。 @绿色夹克衫：两两相加转为多项式乘法，比如 (1 2 4 6) + (2 3 4 5) => (x + x^2 + x^4 + x^6)*(x^2 + x^3 + x^4 + x^5) 。更多思路请见这 ：http://www.51nod.com/answer/index.html#!answerId=569 。 阿里巴巴第二道(研发类)
笔试题1，原题大致描述有一大批数据，百万级别的。数据项内容是：用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间，且是连续的，可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘，空间大小均为512M，内存空间64M。
1) 为实现快速查询某用户ID对应的各科成绩，问磁盘文件及内存该如何组织；
2) 改变题目条件，ID为0~10亿之间，且不连续。问磁盘文件及内存该如何组织；
3) 在问题2的基础上，增加一个需求。在查询各科成绩的同时，获取该用户的排名，问磁盘文件及内存该如何组织。
笔试题 2： 代码实现计算字符串的相似度。 和计算两字符串的最长公共子序列相似。 设Ai为字符串A( a1a2a3 … am )的前i个字符（即为 a1,a2,a3 … ai ） 设Bj为字符串B( b1b2b3 … bn )的前j个字符（即为 b1,b2,b3 … bj） 设 L(i , j)为使两个字符串和Ai和Bj相等的最小操作次数。 当ai等于bj时 显然L(i, j)=L(i-1, j-1) 当ai不等于bj时 若将它们修改为相等，则对两个字符串至少还要操作L(i-1, j-1)次 若删除ai或在Bj后添加ai，则对两个字符串至少还要操作L(i-1, j)次 若删除bj或在Ai后添加bj，则对两个字符串至少还要操作L(i, j-1)次 此时L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) ) + 1 显然，L(i, 0)=i，L(0, j)=j, 再利用上述的递推公式，可以直接计算出L(i, j)值。具体代码请见这：http://blog.csdn.net/flyinghearts/article/details/5605996。 - 9月14日，小米笔试，给一个浮点数序列，取最大乘积子序列的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积子序列为3，0.5，8。
点评：
解法一、
或许，读者初看此题，自然会想到最大乘积子序列问题类似于最大子数组和问题：http://blog.csdn.net/v_JULY_v/article/details/6444021，然实则具体处理起来诸多不同，为什么呢，因为乘积子序列中有正有负也还可能有0。
既如此，我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。So，
我们让maxCurrent表示当前最大乘积的candidate，
minCurrent反之，表示当前最小乘积的candidate。
（用candidate这个词是因为只是可能成为新一轮的最大/最小乘积），
而maxProduct则记录到目前为止所有最大乘积candidates的最大值。
由于空集的乘积定义为1，在搜索数组前，maxCurrent,minCurrent,maxProduct都赋为1。
假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates，新读入数组的元素x(i)后，新的最大乘积candidate只可能是maxCurrent或者minCurrent与x(i)的乘积中的较大者，如果x(i)<0导致maxCurrent<minCurrent，需要交换这两个candidates的值。
当任何时候maxCurrent<1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent为1，类似的可以更新minCurrent。任何时候maxCurrent如果比最好的maxProduct大，更新maxProduct。
具体代码如下：
解法二、
本题除了上述类似最大子数组和的解法，也可以直接用动态规划求解（其实，上述的解法一本质上也是动态规划，只是解题所表现出来的具体形式与接下来的解法二不同罢了。这个不同就在于下面的解法二会写出动态规划问题中经典常见的状态转移方程，而解法一是直接求解）。具体解法如下：
假设数组为a[]，直接利用动归来求解，考虑到可能存在负数的情况，我们用Max[i]来表示以a[i]结尾的最大连续子序列的乘积值，用Min[i]表示以a[i]结尾的最小的连续子序列的乘积值，那么状态转移方程为：
Max[i]=max{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
Min[i]=min{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
初始状态为Max[1]=Min[1]=a[1]。代码如下：
根据“负负得正”的乘法性质，自然想到从 N个整数中去掉一个负数，使得 -1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组，把绝对值最小的负数给去掉就可以了。3. P为正数
类似地，如果数组中存在正数值，那么应该去掉最小的正数值，否则去掉绝对值最大的负数值。 上面的解法采用了直接求N个整数的乘积P，进而判断P的正负性的办法，但是直接求乘积在编译环境下往往会有溢出的危险（这也就是本题要求不使用除法的潜在用意），事实上可做一个小的转变，不需要直接求乘积，而是求出数组中正数（+）、负数（-）和0的个数，从而判断P的正负性，其余部分与以上面的解法相同。
在时间复杂度方面，由于只需要遍历数组一次，在遍历数组的同时就可得到数组中正数（+）、负数（-）和0的个数，以及数组中绝对值最小的正数和负数，时间复杂度为O（N）。 - 9月15日，中兴面试：
小端系统
输出结果为？（答案：32 20） - 一道有趣的Facebook面试题：
给一个二叉树，每个节点都是正或负整数，如何找到一个子树，它所有节点的和最大？
点评：
@某猛将兄:后序遍历，每一个节点保存左右子树的和加上自己的值。额外一个空间存放最大值。
@陈利人：同学们，如果你面试的是软件工程师的职位，一般面试官会要求你在短时间内写出一个比较整洁的，最好是高效的，没有什么bug的程序。所以，光有算法不够，还得多实践。
写完后序遍历，面试官可能接着与你讨论，a). 如果要求找出只含正数的最大子树，程序该如何修改来实现？b). 假设我们将子树定义为它和它的部分后代，那该如何解决？c). 对于b，加上正数的限制，方案又该如何？总之，一道看似简单的面试题，可能能变换成各种花样。
比如，面试管可能还会再提两个要求：第一，不能用全局变量；第一，有个参数控制是否要只含正数的子树。其它的，随意，当然，编程风格也很重要。 - 谷歌面试题：
有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据。也尽量少用网络带宽。 - 小米，南京站笔试（原第20题）：
一个数组里，数都是两两出现的，但是有三个数是唯一出现的，找出这三个数。
点评：
3个数唯一出现，各不相同。由于x与a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。具体答案请参看这两篇文章：1、http://blog.csdn.net/w397090770/article/details/8032898，2、http://zhedahht.blog.163.com/blog/static/25411174201283084246412/。 - 9月19日，IGT面试：你走到一个分叉路口，有两条路，每个路口有一个人，一个说假话，一个说真话，你只能问其中一个人仅一个问题，如何问才能得到正确答案？点评：答案是，问其中一个人：另一个人会说你的路口是通往正确的道路么？
- 9月19日，创新工厂笔试题：
给定一整型数组，若数组中某个下标值大的元素值小于某个下标值比它小的元素值，称这是一个反序。
即：数组a[]; 对于i < j 且 a[i] > a[j],则称这是一个反序。
给定一个数组，要求写一个函数，计算出这个数组里所有反序的个数。
点评：
归并排序，至于有的人说是否有O（N）的时间复杂度，我认为答案是否定的，正如老梦所说，下限就是nlgn，n个元素的数组的排列共有的排列是nlgn，n！（算法导论里面也用递归树证明了：O(n*logn)是最优的解法，具体可以看下这个链接：）。然后，我再给一个链接，这里有那天笔试的两道题目：http://blog.csdn.net/luno1/article/details/8001892。 - 9月20日，创新工厂南京站笔试：
已知字符串里的字符是互不相同的，现在任意组合，比如ab，则输出aa，ab，ba，bb，编程按照字典序输出所有的组合。
点评：非简单的全排列问题（跟全排列的形式不同,abc 全排列的话，只有６个不同的输出：http://blog.csdn.net/v_july_v/article/details/6879101）。本题可用递归的思想，设置一个变量表示已输出的个数，然后当个数达到字符串长度时，就输出。 - 11月10日，百度笔试题：
1、20个排序好的数组，每个数组500个数，按照降序排序好的，让找出500个最大的数。
2、一在线推送服务，同时为10万个用户提供服务，对于每个用户服务从10万首歌的曲库中为他们随机选择一首，同一用户不能推送重复的，设计方案，内存尽可能小，写出数据结构与算法。
-
从今天开始，在继续整理笔试面试题的同时，将整理上面已经收录的一系列笔试面试题的答案，欢迎诸君与我共同讨论.思考.做之「参与的方式为：你除了可以直接评论在本文之下,你也可以通过邮件：zhoulei0907@yahoo.cn或私信：http://weibo.com/julyweibo 给我，或自己写一篇博文把链接发给我收录,无任何语言限制」2012.10.19...
注意：
请所有凡是已经在本文评论下show 出了你的代码code(含思路)的朋友：「10.13日之前第一批：zhutou100hao，zzran，yuankangjian_2，caopengcs，iamzhaiwei，milo_zhang_bs， tpm0513， huangxy10，宇智波鼬，sos-phoenix，aini201，aini201，xsfrank，zz198808 ，Dracula777，li850221，ghostjay0216，a81895898，donghang0535， iamzhaiwei，fengchaokobe，umissmesomuch，believe3，aini201， liuliuliu11，qichi_bj」+ 「10月13日以后第2批： 杜，litaoye，smilearchery，jiadong1125，nwpulei，wumuzi520，..，尽快发“ID号+你在本文评论下做的题目的题号”到我邮箱「zhoulei0907@yahoo.cn」或者联系QQ：786 165 179，我会在尽快发给你 十五个经典算法研究的 可自行编辑修改的WORD文档，或者直接转发加群下载得到：http://weibo.com/1580904460/z4fqHcWDV，欢迎各位及其他朋友们继续参与，感谢诸位。
本文评论下的所有代码未经仔细验证，如果读者发现其中任何问题或错误，欢迎指正，经验证后，我也会给你发送文档，其他此前通过私信或邮件或QQ发过我题目或答案的朋友们如若需要也请发邮件：“名字+ 原文中的题号” 给我以便传送文档。July、二零一二年十月十六日。