先说完pptv的终面吧，16号下午去他们公司终面，面试我的就是上一个面试官说的领导--据说是清华毕业的，在微软工作过的大牛··，那天好像有其他公司来PPTV洽谈什么业务貌似，那个面试官要去开会，所以这次面试不超过30分钟··，只有2个算法题。（我跪了一个··这次面试感觉不是很好··现在还在等消息估计也是挂了），下面是题目。
1、给定一个方法f();这个方法一次可以排序5个数，给定25个无序的数，怎么只用这个方法从这25个数中选出前4个，最少要调用几次这个方法？

已经搬好小板凳，坐等更新！话说楼主哪个学校毕业的？硕士吗？

这个题目其实算简单的···但是我没求出最优解，（因为面试官问了我还没有更好的办法）
我给的答案是9次，把25个数分成5组，分别对这5组进行排序（5次调用），然后分别取这5组的最大数（或最小数）排一次序，可以确定一个最大数（或者最小数），接下来依次重复这个步骤（就是每次都从每一组里取出最大数进行排序），一共需要9次，其实这样的方法做了无用的功，因为排在第五组的数是可以不用去考虑的，第五组最大的数最大也只能是这25个数中第五个大的数，而题目是要取前四个，所以可以忽略第五组，··当时我也考虑忽略第五组能有什么好的办法··但是想来想去最坏情况下还是要9次···所以这道题就这样过了

留名！

5次

是5个步骤，9次……

第二道题是关于算术表达式的，一个算术表达式比如 (1+2) * (3-6)可以化成一个二叉树
如图
现在的问题是给你一个这样的二叉树，怎么还原成这个算术表达式

先分5组，排序，5次，再从中5组中分别取最小的排序，得出最小的，再从这个最小的那组取出最小的加到这4中排序，如此下来就可以取出最小的4个数，次数5+4

第二个题目应该是考二叉树的前序，中序，后序的遍历吧，早就忘光了

当时我一看这不就是一个二叉树的前序遍历么····但是我又想不可能这么简单···，我把遍历的结果写了一遍发现少了括号···对，就是这个括号把我搞死了···没有接触过这方面的题，没办法也只能硬着头皮写了，我想大概的思路就是要比较运算符的优先级，然后在适当的位置添加括号···当时就是这么和面试官说的··就是按前序遍历，遍历到运算符的时候，查看他的左右子节点是否也是运算符，如果左子节点是运算符，则比较优先级，如果左子节点优先级小于等于根节点，则在输出根节点之前输出一个“)”，同时寻找左节点的最左的一个为数字的节点，在这个节点之前添加一个"("，然后右边的节点处理就和左边的相反了，如果右子节点的优先级小于等于根节点的优先级，输出一个"("，同时寻找其最右的一个为数字的子节点，在其之后输出一个")"，当时也是说的稀里糊涂的，面试官问了一句你有没有考虑过多括号的情况，比如
5 * ((2+4) / 4) 这样的，左边有两个括号···当时我也不知道我这个方法对不对，正在考虑的时候，他就说今天先这样吧，我这边等下还要开会，你先回去吧····那一刻我就知道这次面试是挂了···

先去吃饭了··回来再更

好贴必须顶！