百度面试题讨论

统计地铁   某一秒的 人数
数据：
时间都到秒级别
进站时间   出站时间   卡ID

然后怎么设计一种结构，可以提供查询  某一秒的 人数， 查第 3  第5秒的人数

感觉我的思路很naive：
假设查询第T秒，问题转化成   统计 出站时间 > T 并且 进站时间<T 的条数
这种日志一般都是有序的，先找到进站时间 >Ｔ的点，然后倒着往回找出站时间＜Ｔ的点，　它们之间的就是人数

然后把结果保存起来，用树形结构，加速查找。


感觉我没答到点上，求思路
#百度#
全部评论
典型的线段树 or 树状数组
点赞 回复 分享
发布于 2016-08-11 18:07
这题目跟统计某时刻的IP在线一样啊，简单来说就是分成每一时刻，记录进站出站，4楼正解
点赞 回复 分享
发布于 2016-08-12 17:08
这道题是百度以前的面试题了，4楼正解
点赞 回复 分享
发布于 2016-08-12 14:35
利用hash解决，开辟一个60*60*24 数组a，初始化为0.读取进和出的日志，比如在第10秒进有100人，则a[100]+=100.在第10秒出了20人，则a [100]-=20那么最后第10秒的人数为80.遍历万正个进和出的日志，那么数组a中就为每一秒的变化人数，在申请一个数住b大小和a一样，b[i]=a[i]+b[i-1], b[0]=a[0] 这样b[i]即为第 i秒前总人数
点赞 回复 分享
发布于 2016-08-11 23:06
令牌桶
点赞 回复 分享
发布于 2016-08-11 22:59
这个应该就是线段树了
点赞 回复 分享
发布于 2016-08-11 21:03

相关推荐

不愿透露姓名的神秘牛友
07-03 17:30
点赞 评论 收藏
分享
07-01 12:26
浙江海洋大学 Java
点赞 评论 收藏
分享
06-26 16:46
广东海洋大学 Java
牛友们为什么我的简历投出去看都没人看双飞java毕业真的只能送外卖了吗
程序员小白条：找的太晚，别人都是大三实习，然后大四秋招春招的，你大四下了才去实习，晚1年
点赞 评论 收藏
分享
06-21 01:03
门头沟学院 Java
点赞 评论 收藏
分享
头像
07-02 20:00
北京体育大学 测试工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

招聘动态

查看更多

现代汽车前瞻技术研发中心

京东TET

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 你觉得实习能学到东西吗 #
29685次浏览 626人参与
# 发工资后，你做的第一件事是什么 #
67407次浏览 228人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
25476次浏览 208人参与
# 秋招什么时候开投比较合适？ #
17804次浏览 261人参与
# 机械人集合！你是什么工程师？ #
15243次浏览 88人参与
# 如何准备秋招 #
17379次浏览 329人参与
# 工作中哪个瞬间让你想离职 #
25358次浏览 177人参与
# 百度工作体验 #
218703次浏览 1954人参与
# 硬件应届生薪资是否普遍偏低？ #
73471次浏览 513人参与
# 机械人与华为的爱恨情仇 #
115993次浏览 942人参与
# 影石Insta360求职进展汇总 #
123016次浏览 1069人参与
# 不考虑转正，实习多久合适 #
31442次浏览 145人参与
# 实习，不懂就问 #
40658次浏览 637人参与
# 通信和硬件还有转码的必要吗 #
57151次浏览 526人参与
# 面试被问期望薪资时该如何回答 #
255788次浏览 1479人参与
# 24届的你们都什么时候入职？ #
59847次浏览 424人参与
# 你们公司几号发工资 #
20303次浏览 136人参与
# 软开人，秋招你打算投哪些公司呢 #
102296次浏览 958人参与
# 每个月的工资都是怎么分配的？ #
24015次浏览 405人参与
# 你觉得现在还能进互联网吗？ #
7189次浏览 129人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
28927次浏览 460人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务