近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1878|回复: 11
收起左侧

Bloomberg新鲜电面

[复制链接] |试试Instant~ |关注本帖
outlookeye 发表于 2015-10-1 02:39:51 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Bloomberg - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚刚的电面,之前被放过一次鸽子,重新约的时间
题没来得及copy过来,页面就失效了
听口音是白人小哥,全程情绪不怎么高
上来先问用什么语言,做过哪些projects,遇到哪些challenge,怎么解决。然后问了一个project里细节问题
然后coding
一堆文字,理了半天才明白让干啥。
卖车票,n个车票窗口,每个窗口里有a_i张票,票价和窗口内剩的票数一样。需要卖掉m张票。问卖m张票得到的最多的总钱数(max profit)

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

评分

1

查看全部评分

wilsonyqm 发表于 2015-10-1 11:20:32 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这道题是不是用priority Queue啊?Maxheap
回复 支持 反对

使用道具 举报

wilsonyqm 发表于 2015-10-1 11:20:39 | 显示全部楼层
关注一亩三分地微博:
Warald
这道题是不是用priority Queue啊?Maxheap
回复 支持 反对

使用道具 举报

 楼主| outlookeye 发表于 2015-10-2 05:40:38 | 显示全部楼层
我是这样弄的
回复 支持 反对

使用道具 举报

redong 发表于 2015-10-4 11:54:57 | 显示全部楼层
请问楼主,coding 那题 是给你一个array,然后return max profit?
回复 支持 反对

使用道具 举报

tk1322715 发表于 2015-10-5 10:35:33 | 显示全部楼层
个人还有一种做法不用max heap。先根据票数把窗口sort一遍。之后再由大到小扫一遍数组就可以算出答案来了。时间复杂度o(nlogn)
回复 支持 反对

使用道具 举报

 楼主| outlookeye 发表于 2015-11-1 05:03:14 | 显示全部楼层
tk1322715 发表于 2015-10-5 10:35
个人还有一种做法不用max heap。先根据票数把窗口sort一遍。之后再由大到小扫一遍数组就可以算出答案来了。 ...

这样能行吗?票价是会变的。每从一个窗口卖掉一张票,这个窗口的票剩余数量就变了,所以这个窗口的票价也会变。你这样sort,每卖掉一张票,都得重新sort吧
回复 支持 反对

使用道具 举报

 楼主| outlookeye 发表于 2015-11-1 05:05:00 | 显示全部楼层
redong 发表于 2015-10-4 11:54
请问楼主,coding 那题 是给你一个array,然后return max profit?

是的,但是array里得值是会变的,是当前窗口剩余的票数量
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-10 04:48:45 | 显示全部楼层
请问一下楼主后来结果如何?
回复 支持 反对

使用道具 举报

22691482 发表于 2015-12-11 06:27:06 | 显示全部楼层
从大到小排序,从第一个开始看,买那个窗口与后面窗口相差的票:. more info on 1point3acres.com
比如{10,8,6,4,2}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
在第一个窗口买两张 -》{8,8,6,4,2}. 1point3acres.com/bbs
在前两个窗口买四张 -》{6,6,6,4,2}. 鍥磋鎴戜滑@1point 3 acres
在前三个窗口买六张 -》{4,4,4,4,2}
.。。
直到买的票数为m
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-11 08:20:26 | 显示全部楼层
22691482 发表于 2015-12-10 17:27
从大到小排序,从第一个开始看,买那个窗口与后面窗口相差的票:
.鏈枃鍘熷垱鑷1point3acres璁哄潧比如{10,8,6,4,2}.1point3acres缃
在第一个窗口买两 ...

这样时间复杂度有点太高
回复 支持 反对

使用道具 举报

dunan00001 发表于 2017-1-16 13:28:09 | 显示全部楼层
不能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). 1point 3acres 璁哄潧
知道买了m张
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-25 17:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表