Citadel的变态OA 欢迎大家讨论

刚刚做了Citadel的OA，60分钟3道题，从时间上来说题量并不小，而且test case也非常tricky
尤其是第二题，除了题目中给出的example以外其他test case全军覆没和小伙伴讨论了很久也找不到问题出在哪里，欢迎地里的大神发表意见。

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

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

具体题目截图在附件里：

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

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

祝各位好运~

我也只做出来第一题，心态爆炸了。。。不过我后来想了下第二题，楼主你看看这个行不行？暂时只能想出这个时间复杂度的解法了。如果你想交流，可以发我email: davechan813@gmail.com. 谢谢啦！

1. #include <iostream>
   
2. 
   
3. int helper(const vector<int>& prices, int l, int maxIndex) {
   
4.     int res = 0;
   
5.     for (int i = l; i < maxIndex; i++) res += max(0, prices[maxIndex] - prices[i]);
   
6.     return res;
   
7. }
   
8. 
   
9. int maxProfit(const vector<int>& prices, int l, int r) {
   
10.     if (l >= r) return 0;
    
11.    
    
12.     int maxPrice = INT_MIN, maxIndex = -1;
    
13.     for (int i = l; i <= r; i++)
    
14.         if (prices[i] > prices[i-1] && prices[i] > maxPrice) {
    
15.             maxPrice = prices[i];
    
16.             maxIndex = i;
    
17.         }
    
18.         
    
19.     if (maxIndex == l) return 0;
    
20.     return helper(prices, l, maxIndex) + maxProfit(prices, maxIndex+1, r);
    
21. }
    
22. 
    
23. int maxProfit(const vector<int>& prices) {
    
24.     return maxProfit(prices, 0, prices.size()-1);
    
25. }
    
26. 
    
27. int main() {
    
28.     // vector<int> prices = {6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4}; // 16
    
29.     // vector<int> prices = {7, 8, 10, 3, 2, 1, 0, 1, 2, 3, 4}; // 21
    
30.     // vector<int> prices = {5, 3, 2}; // 0
    
31.     // vector<int> prices = {1, 2, 100}; // 197
    
32.     vector<int> prices = {1, 3, 1, 2}; // 3
    
33.     cout<<maxProfit(prices)<<endl;
    
34. }

复制代码

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

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

请问楼主是海投还是内推的啊？感觉被人内推后就没消息了

想问楼主citadel这个公司怎么样啊   这oa 60分钟也太变态了吧  都不敢投了orz。。。

60分钟写出来不容易，但是应该能够做到。都不是难题。

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

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

jennifermiao 发表于 2018-9-2 08:25
不是一个码农公司，但据说包裹很大

那我也投一个hhh

暑假给我们实习生做了一下这三题-.-被我们吐槽死了...没想到是用来做OA的

求问楼主是海投还是内推的，谢谢！