Bloomberg新鲜电面

刚刚的电面，之前被放过一次鸽子，重新约的时间
题没来得及copy过来，页面就失效了
听口音是白人小哥，全程情绪不怎么高
上来先问用什么语言，做过哪些p

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

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

）

就一道题，估计挂了。。。。都说bloomberg两题才能过电面么

tk1322715 发表于 2015-10-5 10:35
个人还有一种做法不用max heap。先根据票数把窗口sort一遍。之后再由大到小扫一遍数组就可以算出答案来了。 ...

这样能行吗？票价是会变的。每从一个窗口卖掉一张票，这个窗口的票剩余数量就变了，所以这个窗口的票价也会变。你这样sort，每卖掉一张票，都得重新sort吧

从大到小排序，从第一个开始看，买那个窗口与后面窗口相差的票：
比如{10，8，6，4，2}
在第一个窗口买两张 -》{8，8，6，4，2}
在前两个窗口买四张 -》{6，6，6，4，2}
在前三个窗口买六张 -》{4，4，4，4，2}
.。。
直到买的票数为m

不能merget k sorted list?
第一个窗口7，第二个窗口6，第三个窗口8  heap(8,7,6)
放进heap, pop 8 , push (8 - 1) heap(7,7,6)
再pop 7, push 6;heap(7,7,6)
知道买了m张

这道题是不是用priority Queue啊？Maxheap

这道题是不是用priority Queue啊？Maxheap

我是这样弄的

请问楼主，coding 那题 是给你一个array，然后return max profit？

个人还有一种做法不用max heap。先根据票数把窗口sort一遍。之后再由大到小扫一遍数组就可以算出答案来了。时间复杂度o(nlogn)

redong 发表于 2015-10-4 11:54
请问楼主，coding 那题 是给你一个array，然后return max profit？

是的，但是array里得值是会变的，是当前窗口剩余的票数量

请问一下楼主后来结果如何？