Google MTV onsite面经，5轮4个三哥

chishui 发表于 2015-7-26 05:16
我的方法是写两个iterator，一个中序遍历，一个是和中序遍历相反的遍历（先右子树后左子树），然后按2Sum ...

可是楼主，你这样并不会有时间复杂度上质的变化吧？BST本身的属性就决定了你可以lgN时间内找到某个数啊。。。。

chishui 发表于 2015-7-26 05:18
基本就是hash table统计频率，然后把word和频率放到BST里，然后找出top1000，这个方法会经常调用，所以要 ...

楼主，你动用BST的时候，肯定是扫描完query文件，并且hashtable也建立完成之后吧?那这个问题不就妥妥的变成了经典的求前K大的问题了嘛?   
与其辛苦的调整BST的平衡，为何不直接用heap呢？

chishui 发表于 2015-7-26 05:18
基本就是hash table统计频率，然后把word和频率放到BST里，然后找出top1000，这个方法会经常调用，所以要 ...

楼主，这里用prority queue更好吧，维护成本比bst低不少。最后依次取顶上1000个。

chishui 发表于 2015-7-26 05:18
基本就是hash table统计频率，然后把word和频率放到BST里，然后找出top1000，这个方法会经常调用，所以要 ...

这个感觉Priority Queue更合适一些。

给字符串，写压缩算法，解压算法已有，例如aaabbbbcccc->aaa4xb4xc，需要考虑3aaaaa->35xa会出问题

可不可以用3xxx5xa表示3aaaaa，比如xxx就用3xx表示


5. 判断一个word的任何permutation是不是palindrome

为什么我觉得除非这个单词所有字符都一样，才可能是palindrome= =
比如aba,  baa就不是palindrome了
任意排列可能性实在太多了吧

lxia 发表于 2015-8-5 17:44
给字符串，写压缩算法，解压算法已有，例如aaabbbbcccc->aaa4xb4xc，需要考虑3aaaaa->35xa会出问题

可 ...

palindrome这题的意思感觉应该是要判断这个字符串是否存在某个permutation是palindrome？

第5题是否是return boolean判断是否存在permutation是回文？如果这样是不是要统计word中的letter频率，如果有两个以上的letter的频率是奇数，就return False，else return True？ 请指教

chishui 发表于 2015-7-20 07:59
类似hello或者testhellolala

请问这个比较是不是利用tag的信息把text之间的包含关系构建出来，然后比较text+structure？

chishui 发表于 2015-7-25 13:16
我的方法是写两个iterator，一个中序遍历，一个是和中序遍历相反的遍历（先右子树后左子树），然后按2Sum ...

请问楼主怎么iterator tree? 我只想到用stack，但是这样并没有办法控制读一个就暂停，再比较一下，再可能读下一个。iterator直接while loop了停不下来啊


补充内容 (2015-8-12 15:12):
懂了，iterate把tree先都push到stack，一次调用pop一个就是一个数据，处理一下push回去，下次再调用再pop又是一个数据。

ChrisGates23 发表于 2015-8-11 08:39
第5题是否是return boolean判断是否存在permutation是回文？如果这样是不是要统计word中的letter频率，如果 ...

赞同我也这样想