Google Onsite 面试经验

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 太浪费空间了，提升一

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

个点相当于一个transit, 和压缩过路径的union find有点像

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

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

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

yuyuyu0905 发表于 2017-11-14 10:51
楼主能说一下第四题怎么constant时间复杂度嘛？

谢谢~

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

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

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

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

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

牛

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

谢谢~

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

freegyp 发表于 2017-11-14 11:13
第二题意思是不是两个string a、b，不管在a中出现的字母在b中出现了几次，只要都出现了而且没有其他的字母 ...

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

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

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

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

weiliango 发表于 2017-11-15 04:00
感觉第二题整个歪掉了。。
让我写的话，每一个字符串搞一个check value。用比特运算。刚想起来这个是leetc ...

256个字符