今天下午去参加了大众点评网的笔试，先是各种类似于公务员考试的语言推理、数字推理、图形推理的题，我发现我在这方面真是弱爆了，到后面都没时间做了，图形推理题各种诡异。。。最后给了半个小时做两道算法题，题目如下：
题目一：一个单入口单出口的有向无环图中，要求在某些地方插入一些节点使得任何一条由起点到终点所经历的节点数相同，类似于下面的图，要求给出算法描述并分析时间复杂度。
如上图所示，节点A到C有两条路径，ABC这条路径经过了一个节点，而AC路径经过了0个节点，我们的算法所要做的事就是要在AC路径中间加入一个节点，然后ABC路径和ADC路径都经过了一个节点。
我在试卷上给出的解决方案：
（1）、首先求出最长路径的长度n（意即最长的路径经过n-1个节点），这个可以用DFS来做，应该比较容易
（2）、从出口节点开始，遍历每个指向出口节点的节点，如果该节点已经是起始节点，则在这两个节点之间插入n-1个节点，否则递归调用该过程，只不过传递给给节 点的路径长度减1
那么这个解决方案是正确的么？考虑右面这个图(请先忽略图的红色部分)，按照我的算法，求得的n应该是3，然后递归到节点4时，发现节点1已经是起始节点，然后就在节点4和节点1之间插入一个新的节点8，然后问题出现了：最长路径已经变成了4！所以这个算法是错误的，紧接着我又想到了，递归的过程可不可以从起始节点开
始？需要增加的节点插入到整个路径的最后两个节点之间，对于刚才的图，这样貌似是解决了问题，但是我们给刚才的图加上红色部分节点，我们用这个算法时，首先得到最长路径为4，然后按1478路径的长度是3，按照算法，我们将在节点7和节点8之间增加一个节点，刚才的问题又出现了，任何一条经过节点78的原来路径长度为4的路径，现在长度变为了5，还是出现了刚才的问题，所以这个算法也是错误的。总结一下，我们可以发现，刚才两种算法错误的原因都是因为添加节点的位置是不对的，如果我们在正确的位置添加了节点（相对右图就是在节点4和节点7指点添加一个节点，在节点4和8之间添加两个节点），那么我们怎么做到这一点呢？我想到的一个算法是这样的：对于每个节点维护一组信息，包括节点的层数（起始节点到该节点的路径长度，起始节点设为0）以及生成该长度的父节点，相对于右图，节点6维护的不经处理的信息就是：层数2来自节点3和节点4；节点7维护的不经处理的信息就是：层数3来自节点5和节点6以及层数2来自节点4；节点8的不经处理的信息是：层数4来自节点7，层数3来自节点7，层数2来自节点4。我们算法所要做的事就是最终使每个节点需要维护的层信息变为一个，即无论从那条路径到该节点，该节点所处的层数都是固定的。算法如下：
1、初始化起始节点的层数信息
2、从起始节点开始遍历每条路径，遇到每个节点生成一个维护信息
（1）如果此节点不存在维护信息，创建之；
（2）如果该节点存在维护信息，有两种情况：
（a）如果生成的维护信息的层数和原来已有的维护信息的层数是相同的，则合并这两个维护信息，比如对于例子中的图，节点5原来的维护信息为“层数3来自节点2”，然后从节点3到节点5生成的维护信息为“层数3来自节点3”，由于层数相同，我们可以将其合并为“层数3来自节点2和节点3”；
（b）如果生成的维护信息的层数和原来节点的维护信息的层数不一致，我们需要比较那一个的层数较大：
a.如果原来维护信息的层数较大，此时，我们只需要在生成此维护信息的节点与此节点之间插入一个新的节点，然后生成新节点的维护信息，然后从新节点开始（2）过程
b.如果新生成的维护信息的层数较大，将新生成的节点信息存入此节点，然后我们需要在生成原来维护信息的所有节点和此节点之间插入新节点，并且需要从所有的新插入节点开始（2）过程
整个算法就是这样，需要遍历的路径（或者节点）我们用栈来存储就可以～
当然这只是我暂时想出来的一种解决方案，或许里面存在错误，也肯定存在较为高效的算法，欢迎大家指正和指教～
题目二：论坛管理员管理论坛时，需要揪出论坛里的灌水者，灌水定义是这样的：某段时间内总的发帖数是N，如果有超过N/2的贴是由某一个ID发的，那么这个ID就是灌水的。设计一个算法在最短的时间内找出该ID。
其实这个就是寻找众数的问题，首先能想到的就是抽出所有帖子的ID，然后进行排序，取排序结果的最中间的ID即可，因为如果存在灌水者的话，他的ID的数目是大于N/2的，当然也有可能会出现误杀，我们在得到这个ID后，再遍历一遍所有ID，得到该ID的数目即可。这种方法的时间复杂度就是各种排序算法的时间复杂度。
由于规定N/2这个数目，我们可以有更简单的算法：在所有ID中，我们每次不放回的取出两个不同的ID，一直取到不能继续取的时候，也就是说最后剩下的ID都是相同的，如果灌水者存在的话，那么这个ID肯定是灌水者的ID，当然还是存在误杀的可能，我们可以继续通过遍历一遍来确定；这个方法可以推广到N/A的发帖数目，我们每次只需要取A个不同的ID即可，A大于2的时候可能存在一些细节问题，都比较简单了。
按照这种思路，在设定为N/2时我们有一个线性时间的算法，该算法的伪代码如下，begin和end分别指向存储ID的数组的起始位置和结束位置：
1 string find_most_appear(string *begin, string *end){ 2string str = *begin, appear_times = 1; 3++begin; 4while(begin != end) 5{ 6 if(*begin == str) 7 { 8 ++appear_times; 9 }else if(appear_times != 0){10 --appear_times;11 }else{12 str = *begin;13 appear_times = 1;14 }15 ++begin;16}
当然，还是有可能不存在灌水者，所以依然要进行验证，时间复杂度O(n)，没什么说的。
半个小时做两道还是比较费力的，这一题想到这的时候，已经到时间了，哈～
本文来自大笤帚，扫除一切障碍奋勇向前的大笤帚！
谢谢阅读，并留下中肯意见。
