facebook onsite

tracywade 发表于 2015-4-3 03:05
开始我也是这么想的 后面你仔细一想 其实inorder就出来了， 因为你知道root 在哪  那肯定就是往左还是往 ...

还是不太明白具体怎么inorder做，LZ能给个详细点的说明吗（伪码也行），多谢~~~

royalheart 发表于 2015-4-7 03:28
还是不太明白具体怎么inorder做，LZ能给个详细点的说明吗（伪码也行），多谢~~~

list = inorder(root);
hashmap<node , index> map;  //node --- position in list;
int l = 0 , r = list.size() - 1;
cur = root;
while(l <= r){
   int index  = map.get(cur);
  left =  findmin(list , l , index - 1)
  right = findmin(list , index + 1 , r);
   cur = left > right ? root.right : root.left;
    l = left > right ? index + 1 : l;
  r = left > right ? r : index - 1;
}


大概就这样  时间复杂度 是  n + n /2 + n / 4 ..... = (1 - (1 / 2)^h)  * n/ ( 1 - 1/2)  ( h = lgn)  所以是线性时间复杂度

求第一题的detail和解法！输入是job名字和需要时间吗？

zengm321 发表于 2015-4-3 13:19
用deque可以实现O(K)space, 等价于O(1).
用一个长度为K的deque，每次检查的时候就数queue里面有没有出 ...

兄弟，deque貌似不能直接访问当中某个元素的吧，难道你每次都pop_front()然后再push回去？

感觉不能直接找含最小数的子树而舍弃另一子树吧，如果最小数相同，而要通过次小数决定大小呢？我觉得这个貌似还是一个global property

我感觉如果空间复杂度方面较为宽容的话，可以在每一个叶子节点存这个path所有的node value，然后heapify，然后每个heap poll一个值，直到找出一个最小值。

第一题我好像都看到两个版本了。有一种版本是可以交换job的次序的。这个帖子里面的queue的解法是对应的保持原本job次序的问题

第二道题，题目应该是想考察dfs，这道题有两点不清楚，1，如果两个child一样数字怎么做？2，如果两条path长度不一样，哪个更小？比如一条path是50 100 1，另外一条是50 2? 第一条更长，但是1更小。如果path长度一样的话，就可以dfs了。思路，每个节点返回包含自己的已经排序的最小path给parent。一个parent拿到两个来自child的path，从中选出最小的一条，之所以这个work是因为，假设两条path是path1, path2, 他们再各自加上相同的从root到parent的path, 只需要根据path1, path2的相互关系就知道merge后大小的相互关系。所以就是dfs一路向上了。

returning 发表于 2016-3-27 07:47
第二道题，题目应该是想考察dfs，这道题有两点不清楚，1，如果两个child一样数字怎么做？2，如果两条path长 ...

你这个说的最清晰，最屌！bottom up！

前面有人说得清楚。

最小值的node首选

以min node为root，找min node again.

....

so, make traversal twice.

First time, find min node for each node as the root.
Then, extract these min nodes into a list.
Second time, traverse until all the nodes in the list are visited.