某一超大Hedge fund OA

刚做完AQR的OA 感觉怎么第一题就那么变态，题目附在图片里了。最后用了线段树写 但还是大多数test case都timeout了。不知道应该用什么更好的办法？
其他两题

您好！
本帖隐藏的内容需要积分高于 177 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 177 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一个题目，问下是不是这么个思路：
O(n)得到三个数组：
- max 从左到右：
- min 从右到左：
- diff = max - min
对于每个query就是直接在diff上在给的index range线性扫描一遍找max？感觉线段树的深度是log(max_num)，如果数组里数字很大会很慢吧

虽然积分低看不见，没有米，还是给你点个赞

可以问问楼主申的哪个职位吗？谢谢！

是2sigma吗

AQR

想看看题目的，可惜米不够！

nathanlrf 发表于 2019-7-25 16:19
第一个题目，问下是不是这么个思路：
O(n)得到三个数组：
- max 从左到右：

update:
对于query确实建一个线段树查找区间里的max会更好
更暴力的就是建hash 把所有的range都hash存起来吧
取决于查询次数有多少了

nathanlrf 发表于 2019-7-25 16:19
第一个题目，问下是不是这么个思路：
O(n)得到三个数组：
- max 从左到右：

应该是吧？

你第一个数组记录的是从左到current index上的最大么？如果是这样的话给出L，R 当前最大不一定在这个区间里面。还是应该建线段树。建树的话是O(n), 查询log n, 既然n只给到10^6，这个应该是可以通过的。。