google ,uber 跪经

求问第三轮那个binary search 怎么解决n/4的问题的？
第四轮要求O(1)的time和space吧，hashmap不能用了

我倒是很想知道怎么才能O1 space O1time

laogudongfu 发表于 2016-6-10 03:27
我倒是很想知道怎么才能O1 space O1time

哈哈哈O（1）的space大概是正好一眼看到了是不是子树然后回答了出来吧

laogudongfu 发表于 2016-6-10 02:47
我感觉并不用segment tree 这么麻烦。对这棵树分别做前序遍历和后序遍历，把遍历的顺序分别存在两个hashm ...

你这个办法挺有意思，对普通非BST也有效。


补充内容 (2016-6-10 04:19):
而且你用O(n) space, 面试官提示的做法其实也是O(n) space，具体写起来还没有你的简洁

请问找popular number怎么用BST？。。。。

jyttwc901231 发表于 2016-6-10 04:29
请问找popular number怎么用BST？。。。。

目测 先sort， 其实不用sort就可以了。。。

blackrose 发表于 2016-6-10 04:31
目测 先sort， 其实不用sort就可以了。。。

sort我知道，但是那个好像有点慢？。。。

jyttwc901231 发表于 2016-6-10 04:34
sort我知道，但是那个好像有点慢？。。。

直接设3个count,3个candidate,一次pass O(n)过不就可以了吗？
跟leetcode 的majority element II类似

handsomecool 发表于 2016-6-10 04:16
你这个办法挺有意思，对普通非BST也有效。

嗯，我和laogudongfu一起证了一下这个这个解法，应该是对的。O（n)的space，O（1）的time，代码也简单。不知道楼上讲的O（1）的space是什么。。。。感觉超出了我的知识范围> <

handsomecool 发表于 2016-6-10 02:18
同问google第四轮，即使是BST也不能通过存range来O(1)判断在不在吧，比如parent node记载的range是[1, 10]  ...

我觉得可以这么建segment tree吧  每个node 加个 range, 然后判断 target node 是不是在 source node range 里面  o1 time o1 space 举个栗子

      [1, 5]
      /     \
   [1, 3] [4, 5]
   /   \    /  \
[1,2] 3  4   5
/  \
1   2