上题目之前先叨叨点废话。

这个月被腾讯和微软两家公司折腾的死去活来，笔试一家一次，一共两次。面试一共十轮，腾讯广州研发部四轮，腾讯全国统一校招三轮，微软三轮，结果还算顺利，两家都拿到了offer,最后决定去北京中关村的微软，因为北京离家近，而且死党们暑假也在北京。

本来想写写这个月的辛酸转为欣慰的感慨，后来想想还是算了，因为很多优秀的同学可能RP没有攒够，结果没有拿到自己理想的offer。我一“小人”，在“得志”之后，大发成功感言，无异于在人家伤口上撒盐。此片日志我只想起到雪中送炭的作用，因为后面还有IBM，百度等大公司的实习招聘。我也希望我晒得这些东西能对那些一时失手的童鞋带来些帮助。招聘这个过程偶然因素很多，笔试侥幸过了还有第一轮面试，第一轮侥幸过了，还有第二轮，第二轮侥幸过了还有第三轮。其中只要有一个环节出了差错就game over 了。所以千万不要拿一次面试失败就否定了你自己的实力。

废话不多说了，我把我三次面试的详细题目包括我的解答晒一晒，也许比什么面试感想更有用一些。

提前说明一下，很多题目是没有标准答案的，我之后也懒得查资料做进一步分析。我只能把我当时的回答大概回忆着描述一下，仅作为参考，如果有bug的话，还望高手留言指教。还有，由于该贴得照顾到对计算机掌握程度不同的童鞋，所以每一点我都力求描述的详细一些，大牛觉得啰嗦请直接忽视。

总述：

微软面试，每一轮至少一个小时，一对一PK。几乎不问你项目什么的，因为他们觉得你带来的项目肯定是自己在下面已经准备好了，考不出实力，于是，他们一般是上来就拿题目让你分析。这一点相对于腾讯面试要蛋疼一些，而且，现场写代码是肯定会有的重要环节。经历了三轮面试，感觉微软的面试很有规律，他只会出两类题目，一类是算法数据结构的题目，一类是工程题目。总体感觉，尤其是因为微软的面试时间是在腾讯刚刚结束不久，相比之下，每次面完微软都有一种意犹未尽，荡气回肠的感觉，因为在面试官的点播和提示之下，你解决了很多新颖的问题，但是用到的东西却是你曾经在课本上学到的，或者在竞赛比赛实践生活中掌握的知识。而不像腾讯，展示了两个曾经开发的手机软件，不到二十分钟就把我轰出去了，最后居然还给了我offer。

（先说第二轮吧，因为第一轮面试，一个小时就考了一道工程题，描述起来比较蛋疼）

第二轮面试 第一道题目：

题目描述：现在让你在普通的计算器（位数最多12位）上增加一个功能button，点击这个button之后能进行数字显示模式的切换，即能显示我们汉语对数字表达的习惯。比如计算器最初显示“零”，你按“1”这个按键之后，屏幕显示的是“一”，继续按”9”这个键，显示的是”十九”，继续按“0”这个键，显示的是“一百九十”… …而且，还要增加两个功能button，“退格键”和“清空键”。继续按退格键，显示的是“十九”，继续按“清空建”，显示的是“零”。

分析：

这道题实际上是一道工程题。

首先第一步也是最容易想到的一步就是先建立映射数组，即开辟一个数组用来保存“零，一，二，三，四，九”，以将单个数字快速转化为汉子。

然后再建立一个映射数组用来保存单位，这里有个大陷阱，等会儿再说，我先按照错着来，这个数组保存从小到大的单位“十，百，千，万，十万，百万，，，亿，十亿，百亿，，，”

做完映射这一步，你可以用一个数试一试，比如“931”转化为中文表达为“九百三十一”的过程为：将一个数从左往右扫描，9映射为“九”正确，该数字在百位，映射为“百”，继续，你最终能得到“九”“百”“三”“十”“一”，拼起来“九百三十一”，哇，正确！

如果仅做到此步，你就向面试官描述了你的答案，那么就很危险了。。。

最明显的一个错误是你没有增加对于“0”的处理。

比如“901”转换为“九百零一”而不是“九百零十一”，所以，有零的位置并不输出“单位”。

比如“1001”转换为“一千零一”而不是“一千零零一”，所以，连续0的地方只输出一个零。

比如“1010”转换为“一千零一十”而不是“一千零一十零”，所以，0在最后的时候不作为输出。

关于零的处理我当时就说了这三步处理，我看他的表情没有任何异常，我就没再考虑是否还有遗漏情形。

然后他问我OK了吗？我半信半疑的点了点头。。。

然后他写了一个数，让我用我刚才描述的算法翻译一下“1230123”。正确表达是“一百二十三 万 零一百二十三”，而我的算法翻译得到结果却是“一百万 二十万 三万 零一百二十三”。。。我勒个去！！！当场SB了。不过没关系，如果能及时想办法解决掉，反而能衬托出你灵活处理问题的能力。我自己又测试了一个比较大的数之后，发现问题就出现在单位数组的设置上，就是刚才提到的那个“大陷阱”。“十万”“百万”“十亿”“百亿”等等，这些是“复合单位”，跟十，百，千，万，亿，这几个单位不同。

意识到这一点，我给他说了新的算法思路，对于一个数，首先分成几段，从右到左，每四位一段，比如“123 0123”就会被分为两段，第一段“0123”和第二段“123”然后写一个子函数专门处理四位数以下的翻译工作，0123翻译为“零一百二十三”，处于第一段，不用加单位。然后123会被翻译为一百二十三 ，由于处于第二段，所以加上单位“万”（当然，如果处于第三段，加上单位“亿”）。两段拼起来得到最终答案“一百二十三万零一百二十三”。

说到此，他点了点头，然后让我代码实现，一阵子奋笔疾书，搞定。他检查了一遍，一时没挑出大毛病，就问我，这个问题你解决完整了吗？

我有点疑惑，难道还有神马特殊情形我没想到？

他看我一脸疑惑就在纸上给我画了一个框架图，他说，解决一个问题，要善于将大的问题拆分成数个小的问题，你只解决了一个最关键的子问题，你回想一下我刚才给你提的要求。

原来，我遗漏了解决“输入问题”。汗。。。

他没让我说思路，直接让我写了代码。

注意，如果代码写成：

Int num;

num = input();

mPrint(num);

那就over了。。。

考虑到平时我们使用的计算器的实际情形，正确输入代码如下：

int num = 0;//当前需要显示的数

       int key_val;//每次按键的键值

       while(key_val = input()){//每次得到一个按键

              if(key_val == KEY_BACKSPACE){//如果案件为退格键

                     num/=10;

                     mPrint(num);//mPrint()函数就是刚才讨论过的那个翻译函数

                     continue;

              }

              else if(key_val == KEY_CLEAR){ //如果按键为清除键

                     num = 0;

                     mPrint(num);

                     continue;

              }

              else if(key_val == KEY_DIGIT){//如果为数字按键 0 -9

                     num*=10;

                     num+=key_val;

                     mPrint(num);

                     continue;

              }

              else{

                     //...计算器上的其他按键。

              }

写完代码之后，他问我，你觉得加上这个功能会对整个系统带来什么新的问题吗？

像这种问题一般都属于开放性的，想到什么就说什么，别怕错。

我想了一下，说了一个关于“显示”的问题，就是汉字表达一个数，和数字表达一个数的不同之处，比如：11111 和10001 都占五位，而翻译为汉字表达之后，在显示上占得字长相差很多。想到这点主要是因为最近做的一个开发在处理View框架下对字符串排版的时候很是头疼。

截至到此，这道题目就搞定了，题目不难，不涉及到高深技术，但是时间卡的很紧，当时这道题目的交流时间从头到尾进行了二十五分钟左右，包括最初问题描述，到中间的交流，算法描述，外加两段代码的书写。所以，每段代码的书写要控制在五分钟左右。注意，是在纸上写，不是电脑上，很不习惯，一定要提前练习一下。还有一点要注意，与核心算法无关的代码可以用伪代码实现。比如key_val = input(); input()这个函数，并不需要实现，这么写仅仅代表，计算器内部有一个函数机制能检测你按了那个键，然后返回你一个值就可以了。

第二轮面试 第二道题目

题目描述:给你一个数组，让你返回一个值，这个值在该数组中占得个数，超过数组总的个数的一半以上。比如一个数组有10个数[2, 14 , 2 , 3 , 4 , 2 , 2 , 2 , 2 , 14 ]。这个数组中数字2一共出现6次，那么就返回数字2。为了简化问题，可以认为，对于给定的数组，这个数一定存在。

解答：

当然最简单的方法就是，将数组排个序，然后返回数组中间位置那个数，比如上面那个数组排序之后为[2,2,2,2,2,2 ,3,4,14,14],中间的数为2，所以返回2.。

由于排序的最快时间复杂度事O(nlogn)所以，上面解法的算法复杂度是nlogn。

当然，微软既然拿这道题目考你，肯定不是靠你个简单排序。肯定会有O(n)的解决方法的。

算法很简单，既然他让我找的数值在这儿数组里面占得个数超过总数的一半，那么如果我每次同时去掉两个不同的数，那么剩下的数组里面，那个值的个数仍然占到一半以上。

最后剩下的一堆相同的数肯定就是那个值了。

算法跟他说完之后，他说，算法没问题，但是如何实现呢，也就是说，如果通过一次线性扫描，删掉俩俩不同的数呢？ 然后让我把实现代码写出来。

在实现上用到一个“虚拟栈”的技巧，这个方法很典型，幸亏过去接触过，否则在那么短的时间内很难写出高效的实现代码。

“虚拟栈”就是说，不需要真正开辟空间，我只是申请两个变量，一个记录栈顶的数值，一个记录此时栈里面当前元素个数。

这样，为了解决上面的问题，用“栈”的那套语言来描述就是：

从头到尾扫描原数组，每取出一个数x，进行如下操作。

首先如果栈为空，那么就把当前值x  压入栈；

如果栈不为空，就拿当前值x  跟栈顶元素top 比较：

如果x 等于 top ,那么把x压入栈；

如果x不等于top,那么把top弹出栈。

数组扫描完毕之后，栈顶元素值top即为需要找到的数。时间复杂度O(n)。

当然你会注意到，在栈动态变化的过程中，你会发现，栈中的元素如果数量大于1，必然是一堆相同的元素。所以根本没有必要开辟栈空间，这就用到刚才提到的“虚拟栈”，只需要记录栈顶元素值，和栈中元素的数量即可。可以将“运行时空间复杂度“由O(n)降到O(1)。

代码我就不贴了。

第二轮面试 第三道题目：

题目描述：这道题目挺有意思，他问我你知道”外部排序”吗？ 我一脸茫然，我说，我只知道快排，归并排序，希尔排序等等。。。他打断我，你说的都是”内部排序”。他说到这里，我瞬间想起来，我们那个英文版本的数据结构书，好像在讲内部排序的时候的前一章节有提过外部排序。不过由于不是考试内容，所以我当时就没看。。。他说，没事，不知道没关系，我给你描述一个问题场景，你就把他当成一个新问题来处理就行了（微软面试官好贴心，感动）。

他说，现在我要进行排序，不过需要排序的数据很大，有1000G那么大，但是我的机器内存只有2G大小，所以每次只能把2G的数据从文件中传入内存，然后用一个“内部排序“算法在内存排好序后，再将这有序数据，载入一个2G大小的文件。然后再载入第二个2G数据。。。循环500遍之后，我现在得到500个文件，每个文件2G，文件内部是有序的，然后我再比较这500个文件的第一个数，最小的肯定就是这1000G数据的最小的。那么之后的过程你肯能想到了，就是不断将这500个2G 数据进行一个归并，最终就能得到这1000G的有序数据文件了。

举个例子，比如我要排序10个数，但是我的内存一次只能装下5个数，所以最初的10个数我只能放到文件里面（文件时外存，只要硬盘或磁盘够大，想多大就多大）。内部排序肯定是得需要将数据载入内存中才可以进行的。

这10个数是[ 2 ,3,1,7,9 ,6, 8,4 ,5 ,0 ]。

第一次载入前五个数2,3,1,7,9.  排好序后是：1,2,3,7,9  然后导入一个只存五个数的文件中。

第二次载入后五个数6,8,4,5,0   排好序后是：0,4,5,6,8，然后倒入一个只存五个数的文件中。

之后在归并两个有序数列

第一个有序子数列的头位1，第二个为0，因为0然后在进行第二次比较，1和4进行比较。。。

重复进行最终得到一个有序数列的文件，里面存着，0,1,2,3，，，7,8,9

问题是：在这个过程中，你能想到哪些优化？

（擦，，，背景描述了半天，问题就一句话。。。当时我也很无语。。。） 

解答：

想了大概一分钟，除了增设一个缓冲buffer，加速从文件到内存的转储之外，我脑子里面一片空空。。。而且我想到的那个缓冲buffer所得到的回复是“假设这个优化系统已经帮你优化了” 。。。无语。。。

他看我眉头紧锁，然后给我做了一个提示：假设我现在把文件中的2G数据载入内存这个过程定义为”L”，把内存中的排序过程定义为”S” ,把排序好的 2G数据再转储到另一个文件这个过程定义为”T”…

他还没说完，瞬间反应过来了！“用流水线并行实现“，然后我把流水线那个图画了出来，就是在计算机组成原理那本书中经常出现的“流水线图”。图画好后，他点点头，我也长嘘一口气。。。

然后他问我，用流水线技术之后为什么会加速整个过程。

当然这个问题就很容易了，过去得把一组2G数据的三个过程全部处理完之后，才能进行下一个2G数据的处理，现在就可以三个过程并行着进行了。当时我也忘了，加速比怎么计算了，所以就没提这个东西。。。

他接着问，做了这个并行处理之后，会出现什么问题？

。。。MD，又是一个恶心问题，其实我清楚，问题不难，但是“找问题”好讨厌啊。。。

想了一下，我说，在“S”这个过程，也就是内部排序的这个环节最好不要用“快速排序”，因为快速排序是不稳定的排序，所以在流水线那个图中会出现不均匀的时间块，影响整体性能。

他想了一下，点点头。问，还有吗？给你个提示吧，你想想加了这个优化之后，某个资源会不会出问题？

我想了想，“资源”，计算机的资源没几样啊，CPU，内存。。。再一次，瞬间恍然大明白，是内存出的问题，因为，如果并行进行的话，打个比方，比如现在同时处理的过程是，第一个2G数据的“T”阶段（因为第一个2G数据，比较早的进入流水线，所以之前的两个阶段已经处理完毕），第二个2G数据的“S”阶段，第三个2G数据的“L”阶段，那么这三个阶段是都需要把数据放到内存中的，所以一共得需要6G内存，但是目前计算机的实际内存只有2G啊！！！

解决方法很简单，将内存平均分为三份，分别用于处理三个阶段的数据。

这样带来的影响是，现在一次就不能处理2G数据了，只能处理2/3G的数据，流水线会加长。

他看这块处理的差不多了，就继续提示，你看看在最后的归并上有什么优化？

最后的归并就是不断在一组有序数列中找最小值，还用刚才那个例子，最后不是得到500个2G有序数列吗，但是扫描每个文件头，找最小值，最差情形要比较500次，平均复杂度是O（n）,n为最后得到的有序数组的个数，此例子为500。

他既然问有没有什么优化？那么必然是存在logn的算法了。一提logn和最小值，那没的说，必须是“堆”啊！！！

然后我给他说了一下具体实现细节

就是维护一个大小为n的“最小堆”，每次返回堆顶元素，就为当前所有文件头数值的那个最小值。然后根据刚才弹出的那个最小值是属于哪个文件的，然后再将那个文件此时的头文件所指向的数，插入到最小堆中，文件指针自动后移。插入过程为logn复杂度，但是每次返回最小值的复杂度为O(1)，运行时空间复杂度为O(n)。 OK，搞定。

 

由于已经一个小时了，这道题目 他就没有让我写代码。幸运，堆那个上移，下移操作好长时间没有写过了。。。

第二面结束。