Citadel的sde面经

网申的，rotation program，芝加哥一年纽约一年的，看着上天的工资就想着不是湾区也申一波~~~感觉码农们就是对金融不敢兴趣啊网申的竟然两三天就给了结果，过了轮巨难的OA之后没想到电面还要难的多。。。。。。接电话寒暄一大堆简历本来就没多少时间了上来就是一道hard~

能马上知道是个DP问题但是最后还是有bug：题目如下：

（读懂题就花了好久，你买入就算赚不像传统李口是卖出和买入的差值算赚。。。给的array是股票涨跌的变化值（leetcode都是股票自己的价值））
/*
#Q: given a stock return list of length n,
#Try to

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

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

时彻底搞明白了：
如果有想不出的小伙伴以下作为hint：
        if (j > 0) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + input[i]);
        if (j < k) dp[i][j] = Math.max(dp[i][j], dp[i-1][j+1] - input[i]);

方便在做更多的解释吗，不是特别的理解

求解释一下第二题为啥赚了6

加油星鹏 发表于 2019-1-14 13:21
求解释一下第二题为啥赚了6

可以short position吧...

补充内容 (2019-1-14 23:12):
好像不太对, 第一个test case 那就解释不通了....

加油星鹏 发表于 2019-1-14 13:21
求解释一下第二题为啥赚了6

trading list都给你看了嘛，买入是1卖出是-1，然后看上面的公式~
我在电面的时候也花了很久理解，第一个testcase是因为没有+1买入过不能卖出

想问一下楼主dp同样弱的话，应该如何补救? 有什么书或者leetcode题目要针对这个的吗?

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

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

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

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

xygong 发表于 2019-1-24 08:45
这道题不一定用dp吧，感觉可以用两个size为10的PQ O(n)扫描一遍就可以。扫描的时候正数加到一个PQ，负数加 ...

分析题的时候我一开始就说了pq，面试官直接的否认了我想用sorting和pq的方法，就没接着想下去了

1. class Stock:
   
2.     def run(self):
   
3.         testcases = [
   
4.             ([-2, -1, 2, 1], [0, 0, 1, 1]),
   
5.             ([2, 1, -2, -1], [1, 1, -1, -1]),
   
6.         ]
   
7.         for stock, result in testcases:
   
8.             print(self.stock_price(stock), result)
   
9. 
   
10.     def stock_price(self, prices):
    
11.         """
    
12.         f(i, k) -> maximum profit can get after ith day and I have k stocks (k <= i)
    
13.         max(
    
14.         f(i-1, k+1) - prices[i-1],  # sell at i-1 day
    
15.         f(i-1, k-1) + prices[i-1],  # buy at i-1
    
16.                 f(i-1, k)                   # do nothing
    
17.                 )
    
18.         """
    
19.         dp = [[0] * 10 for _ in range(len(prices))]
    
20.         path = [[0] * 10 for _ in range(len(prices))]
    
21.         delta = [(0, 0), (1, -1), (-1, 1)]  # {direction, decision}
    
22. 
    
23.         for i in range(len(prices)):
    
24.             for k in range(i+2):
    
25.                 max_profit = -float('inf')
    
26.                 max_decision = 0
    
27.                 for dk, decision in delta:
    
28.                     if k + dk < 0 or k + dk > i:
    
29.                         continue
    
30.                     prev = 0 if i == 0 else dp[i-1][k+dk]
    
31.                     profit = prev + decision * prices[i]
    
32.                     if profit > max_profit:
    
33.                         max_profit = profit
    
34.                         max_decision = decision
    
35.                 dp[i][k] = max_profit
    
36.                 path[i][k] = max_decision
    
37. 
    
38.         return max(dp[len(prices)-1])
    
39. 
    
40. 
    
41. Stock().run()
    

复制代码