传说中有人说：google笔试很变态，题目希奇古怪；google题目比较基础简单。
终于得于一见。
晚上干完活才去，到的时候已经7点左右。在二教已经没有空余座位，无赖多等了20多分钟才安排了一个新的教室。
发题，答卷。
整体感觉就是比较基础，没有什么很难的题目，除最后一题目以外。
选择题目9个，比较基础。
第一题，相对比较简单，递归
第二题，基本是看是否对函数效率是否有概念。似乎也跟动态规划的记录法有点相似之处。
最后一题目回想起来实在惭愧，其实还是题目没有怎么读懂。嗨！
以下是科苑上，看到的解法。惭愧惭愧
第一和第二应该是不错的选择！
特别是第二种方法！
发信人:oasis(绿洲),信区:SISE2004702
标题:笔试最后一题想到的几种解法
发信站:BBS科苑星空站(WedOct1803:24:342006),站内
反正也晚了，干脆再折腾一会儿。
题目：n个点组成的无向图，对于任意给出的两点，判断其是否有长度为K的通路。
分析：无向图是允许有环存在的，也允许两点间有多条边，长度为K是指从一个点
移动到相邻点这样过程的次数。比如AB两点相邻，那么A-B-A-B就是长度为3的通路。
解法一：直接利用图论中的一个定理，邻接矩阵U的K次方后所得矩阵的(i,j)元素
即为原无向图中i,j两点之间长度为K的通路数量。因此复杂度只需要对U^K分析。
由于U^2的时间复杂度为O(n^3)，（这里使用了传统矩阵乘法，不过即使用strassan
方法也依然是O(n^(2+e))，其中0小技巧，不需要去依次的乘，否则的话需要K-1次矩阵乘法，可以从U^2，算出U^4，
依此类推，因此总的时间复杂度为O(n^3*lgK)。空间复杂度不细述O(n^2)。
评论一：细心的人会注意到这样的解法其实比题目的要求要强，因为题目中只是要
求出任意给定的两点间K通路数目，而上述做法，则是把所有的两点组合都求出来
了。因此还应该存在着改进的算法在O(n^2)这个时间复杂度级别。
解法二：这是看水木上一个网友的解法，我重写成下面这样：设所给的两点为A、B。
那么首先把A的所有相邻点全部放入U集合中，接着对之前放入U中的点i分别求出其相
邻点，并将它们放入U中（而原先的点i本身则从集合中事先去除）。这样做过K次后，
看队列中是否有B点。若有则表明存在着长度为K的通路。由于每次寻找邻接点的次数
不超过n^2，而要进行K次，因此时间复杂度为O(n^2*K)，空间复杂度为O(n)。
评论二：和解法一相比，从n^3*lgK变为了n^2*K，也就是n*lgK与K之间的差别，若n=k
的话，也就说明后者比前者快了lgK倍。
解法三：从A到B利用深度优先遍历，找出每一条AB间的路径，其中没有点重复经过。
对每一条这样的路径进行分析：
若长度>K，该路径不可能满足；
若长度=K，则已满足；
若长度一次加一）。若无环，则看K-当前路径长度，若该值为偶数，则可以在该路径上的某两
个邻接点上来回的重复走从而满足要求（每来回走一次加二）。其他情况，无法满足。
由上得到算法的时间和空间复杂度均为O(n^2)，
评论三：时间复杂度很可能不是O(n^2)，因为从A到B上找出每一条AB间的简单路径，由
于存在着重复边和环的情况，多半就不是简单的深度遍历的O(n^2)了，具体是多少我也
说不清。笔试里我用的这个方法，现在感觉挺玄。。。
