脸熟跪经

OaPhoneOnsite 发表于 2017-3-7 14:38
我想的是基于leetcode上股票2找出所有单调递增的区间，这样就有了一系列的交易。然后判断两个相邻的交易 ...

懂了，这题其实跟股票 cooldown 那题差不多。因为有了 transaction fee，有些天可以不用做任何交易（比如有几天如果做了交易，获得的利润还不够 transaction fee 的，那么就不做，相当于 cooldown）。所以对这题我们只要在原 cooldown 的状态转移方程里把 transaction fee 减掉就可以了。

OaPhoneOnsite 发表于 2017-3-7 14:38
我想的是基于leetcode上股票2找出所有单调递增的区间，这样就有了一系列的交易。然后判断两个相邻的交易 ...

懂了，这题其实跟股票 cooldown 那题差不多。因为有了 transaction fee，有些天可以不用做任何交易（比如有几天如果做了交易，获得的利润还不够 transaction fee 的，那么就不做，相当于 cooldown）。所以对这题我们只要在原 cooldown 的状态转移方程里把 transaction fee 减掉就可以了。

OaPhoneOnsite 发表于 2017-3-7 14:38
我想的是基于leetcode上股票2找出所有单调递增的区间，这样就有了一系列的交易。然后判断两个相邻的交易 ...

懂了，这题其实跟股票 cooldown 那题差不多。因为有了 transaction fee，有些天可以不用做任何交易（比如有几天如果做了交易，获得的利润还不够 transaction fee 的，那么就不做，相当于 cooldown）。所以对这题我们只要在原 cooldown 的状态转移方程里把 transaction fee 减掉就可以了。

电面2如果有一个element小于k不就return true了吗，不知道题目有没有理解对？

LZ辛苦了 你觉得系统设计面得不好的地方在哪 是说你没回答好面试官的问题还是什么

mingzhou1987 发表于 2017-3-7 15:33
电面2如果有一个element小于k不就return true了吗，不知道题目有没有理解对？

是等于k，写错了。。

BabyShung 发表于 2017-3-7 21:15
LZ辛苦了 你觉得系统设计面得不好的地方在哪 是说你没回答好面试官的问题还是什么

面试官当时不太满意，问了我latency的问题我也没答上来

感谢lz
确实难。

comment 一下：
1.1 用heap对吗？
2.2 确实很烦，写原题的时候想了一下，但是没有细想感觉现场很难写出来。

4.2 股票2变形我的想法是还是dp
f[i,0] 第i天手里没有股票
f[i,1] 有股票。

f[i,0] = Max(f[i-1,0],f[i-1,1] + price[i] - 手续费）
f[i,1] = Max(f[i-1,1],f[i-1,0] - price[i] - 手续费）
return f[n,0]
不知道对不对。

5.2有一个问题 有duplicate的话， 比如说sort 完之后 是1，2，2，3，3，4，然后target 是5
那么找到1和4之后， 中间如果有重复的element的话lz是怎么算的？没有duplicate 应该是2^ count个, 但是有的话只能想到用subset的解法，但是感觉非常不好。求教一下。

最后再次感谢lz 表述的非常清晰，看的出lz很强，一定会拿到offer的

多谢楼主分享，楼主很厉害，一定可以顺利拿到offer！

30048686 发表于 2017-3-9 15:32
感谢lz
确实难。

5.2 又想了一下，求subset个数的子问题，应该是统计所有unique element 和它们的freq 然后 把（freq+1）相乘。
这样worse应该是n的。
但是可以优化，
sort完之后实际上不需要存整个array了
只要存 val,count 的pair
这样每次移动也不用考虑判重

如果不考虑结果超界，可以先把所有的（freq+1）乘起来，然后每次left++或者righ--再从中除去。
这样应该就是 n log n (sort) + n (product of all) + n (2 pointers) 的复杂度

不知道讲的对不对？