狗家l3 MTV onsite面经

匿名者 发表于 2019-12-14 05:34
啊，child id就是node自己的id，我没说清楚，sry

那这样做起来就简单了

xuzhenzhen2real 发表于 2019-12-14 15:12
请问楼主如果第二题follow up less than k怎么做？没想到O n的解法，谢谢啦～

个人感觉，就是对每一个prefix_sum放到一个multi set中，在放之前利用二分查找找lower_bound of prefix_sum-k的位置，这样就很容易找到对应此prefix_sum的开始的位置，最后把这个prefix_sum放到这个multiset中。进入下一个位置。

匿名者 发表于 2019-12-14 05:35
是啊，当时一时没想到用hashmap，没有用最优的方法做出来。面完以后觉得凉了半截

面试中很容易思路想歪了。我觉得放松会好一点

spirit_room 发表于 2019-12-15 08:07
个人感觉，就是对每一个prefix_sum放到一个multi set中，在放之前利用二分查找找lower_bound of prefix_s ...

这样可以处理array里面有负数的情况吗？第一问的时候用hashmap可以是因为求的是val = preSum - k, 正好。现在这个是所有小于 preSum - k 的值, 感觉不好找. example:

array:
[1, 3, -7,  9]
k: 2
preSum array:
[1, 4, -3, 6]

如果preSum处理到最后一个元素， preSum =6, val  = preSum - k = 4，你找到lowerbound是4 （index : 1）, 然后怎么做？

xuzhenzhen2real 发表于 2019-12-15 08:39
这样可以处理array里面有负数的情况吗？第一问的时候用hashmap可以是因为求的是val = preSum - k, 正好。 ...

应该是找upperbound。
这个时候那个multiset中是 -3 1 4，所以upperbound找到4后边的end（），从这儿往后，有0个元素，所以已9结尾的subarray less than 2的数目是0,然后把prefix sum 6加到multiset中

第一题跟leetcode 608有点像

请问楼主是怎么做的？怎么分出左右子树的，没提到是二叉树啊

spirit_room 发表于 2019-12-15 12:58
应该是找upperbound。
这个时候那个multiset中是 -3 1 4，所以upperbound找到4后边的end（），从这儿往 ...

明白了明白了，谢谢！请问一下multiset是怎么维护顺序的？每次有新的presum的话是logN插入的吗？我用的是java，不太熟悉multiset

最后一题，感觉要搞3遍二分查找，第一遍找到peak，第二遍在前半部分找，第二遍在后半部分找，还有更好方法吗？

找右边节点那题感觉并不简单，能说详细点吗？

xuzhenzhen2real 发表于 2019-12-15 13:47
明白了明白了，谢谢！请问一下multiset是怎么维护顺序的？每次有新的presum的话是logN插入的吗？我用的是 ...

multiset实际就是BST。是logN，Java肯定也有multiset，但我具体我就不知道了。

spirit_room 发表于 2019-12-15 13:53
multiset实际就是BST。是logN，Java肯定也有multiset，但我具体我就不知道了。

最后一题是不是利口三三