G家ONSITE

from here



第一题, 找出一个二叉树的最深节点。

这个题目实际是送分给我的。结果我太紧张，用递归函数完成算法，但是把返回最深节点程序写成了返回最深深度。后来考官提醒我不对，我方寸有点乱，推翻全部递归算法，重新用DFS写了一个非递归算法。结果虽然正确，但是过于复杂。后来想了想，其实这个问题稍微修改一下原有递归算法就好了。面试官是个老白，人还算NICE。




第二题，一个LIST里面放了很多句子，找出每个句子共同的PREFIX。这个问题不是很难，我写了个比较函数，然后依次比较每个句子。考官问我算法效率，我说是LIST长度乘最长的LIST单词长度。 他问我有没有更好的算法，我说可以先扫描LIST,找出最短的句子，以它为初始比较，可以减少比较次数。面试官感觉是个东欧白人，比较NICE.




第三题，设计一个 KEY-VALUE机制，必须在O(1)做下列操作: 插入，删除，get(),random_get（）,可以使用hashmap.

这个题目非常tricky. 貌似可以直接使用一个HASHMAP就能完成，但是实际上random_get必须把每个K-V对与一个0到N的整数关联，这个如果直接把MAP放到一个LIST里面去，算法效率就变成了O(N). 我最终使用了两个HASHMAP来实现这个功能，一个HASH表记录0-N的整数下标与KEY的关系，另外一个HASH表记录K-V，还有这个下标。这个算法其实在删除时也有问题，因为删除后会有下标GAP.我实际上是使用了一个机制，让删除操作，每次只删除HASH表最后那个K-V值（之前让最后值与删除值换个位置）。面试官是个亚裔小年轻，非常NICE.



第四题，找出一个GRAPH里面全部的三角形

我的算法： 先做一个访问队列，从一个节点开始BFS遍历，每次把一个节点的所有未访问过的邻居点放入一个LIST,判断这个邻居LIST里面有多少点互相连接。这个就是与这个节点有关的三角形，对它们计数并把结果记入累加器。之后把这个LIST加入队列，继续遍历。累加器最后返回三角形总数。

这个面试官是个三哥，态度很糟糕。似乎看不懂我写的算法，问了很多莫名其妙的问题。估计他给我的REVIEW很差。请各位大神看看，我的算法确实有问题，还是三哥有问题。


第五题 字符串PATTERN MATCH。 一个P字符串 ，一个S字符串。P中下划线 "_"字符通配S的单个字符，"%" 通配S中任意长度字符。

我的算法出现了一个问题，P字符串“ABC_AB%AB"与S字符串 "ABCXABXXXXABAB"这样的匹配，我报FALSE,他说正确的应该是TRUE.

修改过程没有完成时间到了。




好了，情况就这些了，祝各位好运！




补充内容 (2015-2-8 15:46):

这次G家先前电面了我两轮，都比较顺利。后来G出机票让我来ONSITE，题目我没有我想象的难，没想到没过，略有些失望。我不是科班出身，编程和算法都是自学的，没有工作经验应该也是FAIL的原因之一