Optiver Shanghai 23 summer intern OA

因为照片数量限制发不全 但是题目跟那个澳洲还是悉尼的那位朋友发的是一

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

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

估计是固定的。求米pym

咄咄逼人的煎饼果子 发表于 2023-03-16 21:54:23
不会做。。有大神讲一下思路么。。。

第一题我能想到的是先排序构造一个树。每个节点记录该节点的左子树的和。每次删除和插入节点都向上回溯更新左子树和需要更新的节点。这么一来不考虑树的平衡问题的话 可以基本上做到update和check都是logN复杂度。没有检测过能不能过测试集。因为我看了一下题目就放弃了。这个想法也是事后跟舍友讨论出来的。第二题没看。各位有见解的可以随便讲哈！

我咋感觉就暴力比较下就可以了？需要排序吗 calculate O(N)。class FuturePricingEngine {
private:
    int stockPrice;
    vector<pair<int, int>> dividends; // Pair of amount and day

public:
    FuturePricingEngine(int stockPrice, const vector<pair<int, int>>& dividends)
        : stockPrice(stockPrice), dividends(dividends) {}

    void updateDividend(int dividendId, int updatedAmount, int updatedDay) {
        if (dividendId - 1 < dividends.size()) {
            dividends[dividendId - 1] = {updatedAmount, updatedDay};
        }
    }

    int calculateFuturePrice(int daysToFuture) {
        int futurePrice = stockPrice;
        for (const auto& dividend : dividends) {
            if (dividend.second <= daysToFuture) {
                futurePrice -= dividend.first;
            }
        }
        return futurePrice;
    }
};

如果题目是online update/calculate：需要用线段树进行实时update和calculate，能达到 O(NlogN) 的效率。

但是个人猜想这个题目应该是offline的，也就是一次性给出输入，然后一次性输出所有结果。
那么可以完全读入所有的update和calculate之后按照日期进行排序，再按照更小的日期对update和calculate的操作进行遍历（2 pointer）。
效率也类似上面online的效果。

感谢分享！请问这是ds还是sde的intern呢？

Marshmellow 发表于 2023-03-16 14:55:13
感谢分享！请问这是ds还是sde的intern呢？

sde哦！

不会做。。有大神讲一下思路么。。。

我投的 shanghai c++ summer intern 做的 OA 不是这两题诶😂 一个是订单处理，另一个是车辆位置订阅

Thanks for sharing

update次数比较少，关键节点排序暴力就可以了，ac

Deluxurous 发表于 2023-3-17 18:05
我投的 shanghai c++ summer intern 做的 OA 不是这两题诶😂 一个是订单处理，另一个是车辆位置订阅

求问你做的题在地里之前的题库里吗？