Google Onsite 面试经验

Job Hunting Interview
, , , , , ,
1

11/13 完成了google onsite interview
1.国人:
a.输入常数N, 生成1 - 2 ^ N, 然后头尾两两合并，直到最后只有一个数组，暴力解就可以了
b.find the only one peek in integer array, 答: binary search

2.印度人: List Of String, find out the first pair with common unique characters (ABCCC和CAB就满足条件，应为他们都有ABC)
答: One for loop + HashMap<String, Integer>, 每进来一个word单独处理一下就好了
印度人曰: HashMap 太浪费空间了，提升一下

答: 不要任何数据结构了， two for loop生比吧
印度人曰: 太浪费时间了，中和一下吧

答: 用个set吧，只要set里面有了，就跳出loop，和前面的比一下，找到了就返回， 时间是linear的
印度人曰: what are you talking about , I didnt get?

心理答: f*** off, stupid
印度人曰: 再提升一下效率

答: 还是生比, 用一个int[256]把以处理完的存起来
时间到，没空写fellow up的代码了

3.国人: Predict Search Term - Trie problem, 返回List, 要求用线性的时间完成, 类似于leetcode Word Search 2
fellow up: time/space complexity analysis
fellow up: 每个单词有权重，权重大的在前面
fellow up: 尽可能减少排序的时间，答: 建树的时候每个节点放一个PriorityQueue
fellow up: 如果权重可以更新的话，怎样用logN的时间完成，答: 实现自定义的priorityQueue, 可以randomAccess任意节点

4.ABC小哥: LeetCode 399
fellow up: 如何只用线性的空间复杂度，而时间复杂度任然是constant: 答: 所有的点连到一个中心点上，这个点相当于一个transit, 和压缩过路径的union find有点像

面试官都挺和善的，印度人那一轮答得不是很好，感觉他心理有一个预设的方案，不是他那个就一定不行，fellow up答的不好。感觉fellow up挺重要的，代码写的太快，面试官为了hold住面试就必须要一直想fellow up, 这样反倒给自己挖了坑, 希望能集一点人品吧

2

真是很怕遇到硬度人，这样不行，那样也不行，再加上黑着个脸，什么心情没有了

3

第二题也用trie保存出现过的节点的signature就好了 signature就是类似于 AABBC 都转成ABC这种
绝对比hashmap省很多空间

4

楼主能说一下第四题怎么constant时间复杂度嘛？

谢谢~

5

第二题意思是不是两个string a、b，不管在a中出现的字母在b中出现了几次，只要都出现了而且没有其他的字母就是一个pair了？还有string里面除了会出现大写字母还会出现其他字符吗？

6

他没有告诉我具体怎么实现，我们讨论了一下理论就时间到了

我原来这个题是用hashmap<String, Hashmap<String, Double>>来构建图的

如果用union find的话，可能需要一个列表来储存所有union set的根节点

union find本身使用数组实现的，我觉得这个也是可以用数组的，然后另外一个数组用来保存value就可以了

我仔细想了一下，其实搜索的时间按照他的方法是约等于constant，但是有可能会有很多union set，这样就有很多root node，不是严格的constant

7

是的，字符集是256的ASCii
其他的不用纠结，这个估计是那个烙印现场想的，因为我觉得他想要问的也不是什么很复杂的算法，只是一直让你比较tradeoff

8

第二题不用hashset 拼接起来用string 就可以了呀

9

感觉第二题整个歪掉了。。
让我写的话，每一个字符串搞一个check value。用比特运算。刚想起来这个是leetcode原题。
比如 “abc” 搞成 000000…0111
“abcd” -> 00000000…1111
然后比较一下两个数是否相等就好。
这样空间是n，时间是n*k。k是字符串最大程度。

补充内容 (2017-11-15 04:02):
好吧，时间上少乘了个n。。

10

256个字符