狗家VO

求问第二题是求是否有条路径从X到Y点，并且这条路径里面只能有A或者只能有B landmark吗？

kamarkaka 发表于 2022-03-07 19:58:13
哎呀兄弟你可算是说到点子上了，我也是一开始用bst做的，结果面试官大哥还在问有没有其他办法，我给整没辙了就写了个segment tree，我真心觉得和bst完全没差。。。

就是想问下segment tree怎么设计呢？我感觉segment tree一般是解决区间问题的，这题的话区间是0到percentile吗？segment tree的每个节点存哪些值呢？

Caroline0128 发表于 2022-03-07 23:11:40
求问第二题是求是否有条路径从X到Y点，并且这条路径里面只能有A或者只能有B landmark吗？

不是的。比如说input会是(x, y, A)，那么只要有一条路径是从x到y并且经过的节点上至少有一个A就可以了，只有所有路径的所有节点全部是B的情况才返回false

魔群月光 发表于 2022-03-08 05:12:56
就是想问下segment tree怎么设计呢？我感觉segment tree一般是解决区间问题的，这题的话区间是0到percentile吗？segment tree的每个节点存哪些值呢？

我是觉得区间没办法用percentile，因为这样节点会不断变化，本来在higher 50%区间的很可能一会儿就跑到lower 50%去了，完全没法maintain啊，我最后还是用的绝对价格做区间，根节点就是[0, MAX_PRICE]，然后下面依次减半

kamarkaka 发表于 2022-03-08 05:59:10
我是觉得区间没办法用percentile，因为这样节点会不断变化，本来在higher 50%区间的很可能一会儿就跑到lower 50%去了，完全没法maintain啊，我最后还是用的绝对价格做区间，根

想问下如果用价格做区间的话，query怎么求任意ratio的price呢？一般我用segment tree都是求最值或者是和。

魔群月光 发表于 2022-03-08 06:35:16
想问下如果用价格做区间的话，query怎么求任意ratio的price呢？一般我用segment tree都是求最值或者是和。

和之前BST的方法一样还是数节点…比如根节点告诉我一共有100个价格，现在percentile是0.2的话就找20个最小的然后输出第21个价格。所以我也没懂为啥要用到segment tree

明白了，相当于每个区间要维护区间内节点数量。谢谢老哥。

羡慕楼主这么顺利！我的design也是之前没准备过的问题然后时间没把握好clarification完就快30分钟了都没有完全讲完估计凉了 算法题也是纯粹写多线程完全没准 整体算法不难但是我本人垃圾在小地方犯了个煞笔错误不知道面试官之后回去看是不是一下子就会发现😅 分了两天面面完 第一天晚上已经丧得不行了 第二天两轮算法感觉就是死马当活马医的状态了

lxxxxxxx 发表于 2022-3-8 09:17
羡慕楼主这么顺利！我的design也是之前没准备过的问题然后时间没把握好clarification完就快30分钟了都没有 ...

我觉得面试就真挺看运气的。不过有时候自己的感觉和最后结果也不一定一致，我回头细想也发现code里面有一两处小bug

请问楼主 不是很了解segment tree。 是要用array实现么。。。stream的话size会一直增大