狗家店面

今天刚刚面完的phone interview,  没听出面试官是哪里的口音，肯定不是三哥或者美国人。bq的话大概3分钟，问了一下最proud的project和这个project里最困难的部分。然后就coding了。
题目是给一串input代表box，每个bo

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

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

w扫一遍，写完了代码，手动跑了3-4个test case，分析了时间空间复杂度，这时候已经一个小时了，就结束了。
希望能拿到onsite啊！！！！！！！！

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

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

a62253162 发表于 2019-10-3 10:41
用prefixsum 从左到右扫一遍，然后做一个array , leftShortInterval, leftShortInterval = minimal length  ...

谢谢分享，你的方法是不是允许了重叠的情况啊

请问楼主两个interval可以重复吗？
如果不可以，我觉得长度最小的interval不一定会被用到。

比如 2 2 4 4 2 2 1 1 1 1 k=8
长度最小的是4+4，但如果用了这个，另一个长度最小的就是2+2+4*1

可是和最小的两个interval应该是2+2+4，4+2+2

不知道对题目是不是有什么误解，请楼主指正😄

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

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

ymillyh 发表于 2019/10/03 10:11:08
好像是我考虑错了，你的理解应该是对的，你有什么好办法吗？

我觉得可以dp~ 用hashtable 大概就可以O(n)

regina8023 发表于 2019/10/03 10:17:10
我觉得可以dp~ 用hashtable 大概就可以O(n)

我刚开始也是想的dp但是没敢说，怕想不出来.....hashtable做感觉得dfs啊

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

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

a62253162 发表于 2019/10/03 10:41:56
用prefixsum 从左到右扫一遍，然后做一个array , leftShortInterval, leftShortInterval = minimal length of the interva...

嗯我刚刚想了一下你这个应该是可以的

可以用个heap么，heapq.heappush(heap,-length) 当heap长度大于2的时候pop一下就行~