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

2. 给字符串，写压缩算法，解压算法已有，例如aaabbbbcccc->aaa4xb4xc，需要考虑3aaaaa->35xa会出问题，三哥每次我想了没半分钟就给我提示，最后给的feedback是，需要不停的提示才行。。===>aaabbbbcccc->3xa4xb4xc ？3aaaaa->35xa 字符窜还有数字？

3. 给一堆query，求一个小时内出现次数最多的1000个query，用lg(n)的方法，BST. 这一堆， 是在一小时内完成的吗？

题目不难楼主被黑了

另外LZ 第三题用BST 怎么解? 我只有想到类似用quick select algorithm ? 还是我理解错误?

同问第三题条件，input是一个小时以内得还是多个小时，　bst的具体怎么用的

第一题，比如sum是8。用前序遍历一个一个点，比如找到3，就再去BST里面找5，找到就继续找下一对。是这样的嘛楼主？

补充内容 (2015-7-22 02:06):
然后复杂度是N * lgN

3. 给一堆query，求一个小时内出现次数最多的1000个query，用lg(n)的方法，BST

补充内容 (2015-7-22 04:15):
你说一堆，指的是大数据的意思嘛？  这一堆内存能不能装下？  需要将query string hash成数字嘛先？楼主可否说清楚下？

LZ，如何解决判断一个word的任何permutation是不是palindrome。全找出word的permutation，然后一个一个判断？还是有什么更巧妙的办法？

wugoat 发表于 2015-7-20 06:14
楼主辛苦了．这些ｆｅｅｄｂａｃｋ是HR给你的，还是通过内部系统看到的

这个hr真是好人。有的hr打死也不说feedback，更别提具体情况了。

say543 发表于 2015-7-20 12:41
lz BST 2 sum 是不是一样先inorder 跑出sorted sequence, 然后用原本2-sum 的算法解 有其他的限制吗?

要比O(n) space好些的方法

jiebour 发表于 2015-7-22 02:03
第一题，比如sum是8。用前序遍历一个一个点，比如找到3，就再去BST里面找5，找到就继续找下一对。是这样的 ...

我的方法是写两个iterator，一个中序遍历，一个是和中序遍历相反的遍历（先右子树后左子树），然后按2Sum的方法做

jiebour 发表于 2015-7-22 04:15
3. 给一堆query，求一个小时内出现次数最多的1000个query，用lg(n)的方法，BST

补充内容 (2015-7-22 04:15 ...

基本就是hash table统计频率，然后把word和频率放到BST里，然后找出top1000，这个方法会经常调用，所以要维护这个BST