当前在线人数15831
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
狗面经题1
[版面:待字闺中][首篇作者:uwwu] , 2018年07月07日17:45:31 ,1418次阅读,4次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
uwwu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: uwwu (Vera), 信区: JobHunting
标  题: 狗面经题1
发信站: BBS 未名空间站 (Sat Jul  7 17:45:31 2018, 美东)

请问这题C++怎么实现,很难搞的样子?

公交车管理问题
公交车站里面有若干公共汽车, 类似这样 terminal:{bus1, bus2, bus3, ...}, bus
是一个类, 有int
id, String company和一个出发时间 int time. 然后让实现几个函数 :
- add(bus) 向一个车站里加入一辆车
- getnext() 得到下一辆出发的车
- dispatch() 让下一辆车从车站出发
- removeAll(company) 除掉车站中某一个公司的所有车。
问每个函数的时间复杂度。
Map<String, PriorityQueue> companyToQueue,k个company,每个队列长度为L,则
- add(bus): O(logL)
- getNext(): O(k)
- dispatch(): O(k)
- removeAll(company): O(1)
follow up, 自己实现priority queue 来实现上面的每个问题。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

 
sapphirewing
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: sapphirewing (Audrey的树), 信区: JobHunting
标  题: Re: 狗面经题1
发信站: BBS 未名空间站 (Sat Jul  7 22:25:30 2018, 美东)

c++增加了什么额外难度吗?(我不怎么用c++)
你都已经给出用map实现了,不就是做个priority tree的工作了吗?

【 在 uwwu (Vera) 的大作中提到: 】
: 请问这题C++怎么实现,很难搞的样子?
: 公交车管理问题
: 公交车站里面有若干公共汽车, 类似这样 terminal:{bus1, bus2, bus3, ...},
bus
: 是一个类, 有int
: id, String company和一个出发时间 int time. 然后让实现几个函数 :
: - add(bus) 向一个车站里加入一辆车
: - getnext() 得到下一辆出发的车
: - dispatch() 让下一辆车从车站出发
: - removeAll(company) 除掉车站中某一个公司的所有车。
: 问每个函数的时间复杂度。
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2601:641:0:5c40]

 
uwwu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: uwwu (Vera), 信区: JobHunting
标  题: Re: 狗面经题1
发信站: BBS 未名空间站 (Mon Jul  9 21:57:13 2018, 美东)

就是自己实现priority queue 很痛苦啊,感觉写完api 就没有时间实现了

【 在 sapphirewing (Audrey的树) 的大作中提到: 】
: c++增加了什么额外难度吗?(我不怎么用c++)
: 你都已经给出用map实现了,不就是做个priority tree的工作了吗?
: bus



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

 
stanleyli
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: stanleyli (Stanley), 信区: JobHunting
标  题: Re: 狗面经题1
发信站: BBS 未名空间站 (Fri Jul 13 19:30:26 2018, 美东)

自己做priority queue需要做到哪个层次?可以使用push_heap和pop_heap吗?


【 在 uwwu (Vera) 的大作中提到: 】
: 就是自己实现priority queue 很痛苦啊,感觉写完api 就没有时间实现了



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
uwwu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: uwwu (Vera), 信区: JobHunting
标  题: Re: 狗面经题1
发信站: BBS 未名空间站 (Sat Jul 14 17:39:47 2018, 美东)

这是个网上面经题。我写了个API 就花了30 分钟,需要用pq. 估计写完follow up是
implement priority queue
既然需要用到push,pop,getMin就的实现这些功能吧。
不过,估计只需要聊聊大体怎么弄就好了,没有时间写完整代码。
【 在 stanleyli (Stanley) 的大作中提到: 】
: 自己做priority queue需要做到哪个层次?可以使用push_heap和pop_heap吗?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996