百度面试题讨论

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

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

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

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


感觉我没答到点上，求思路
#百度#
全部评论
典型的线段树 or 树状数组
点赞 回复
分享
发布于 2016-08-11 18:07
这个应该就是线段树了
点赞 回复
分享
发布于 2016-08-11 21:03
联易融
校招火热招聘中
官网直投
令牌桶
点赞 回复
分享
发布于 2016-08-11 22:59
利用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
这道题是百度以前的面试题了，4楼正解
点赞 回复
分享
发布于 2016-08-12 14:35
这题目跟统计某时刻的IP在线一样啊，简单来说就是分成每一时刻，记录进站出站，4楼正解
点赞 回复
分享
发布于 2016-08-12 17:08

相关推荐

头像
想开了的突尼斯海怪很活跃
04-26 14:49
Java
用友裁应届
下半年准备来用友的24应届生们，请三思！！！&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;我是23届某9研究生，2月份用友以绩效低为由被裁（我一个应届生跟老员工比绩效，搞笑呢）。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;半年被裁，找工作太难了，大、中型公司进不去（工作经验太少了面试机会都不给，就算给面试，用友所用到的这点技术根本不够打），国企银行进不去（要么只要应届生，要么就要工作经验3年以上的），小公司和外包工资低，降薪10k上下实在有点无法接受，但不去又没有更好的选择。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;下图是前段时间找工作时某公司hr跟我说的，很多来...
投递用友等公司10个岗位 >
点赞 评论 收藏
转发
头像
匿名牛油
不愿透露姓名的神秘牛友
04-25 21:47
已编辑
小米校招（测开岗）
bg双非硕，在四月底拿到了小米的offer（测开），本双非鼠鼠已经相当满意了，感谢小米。笔试（2024/3/12）一面（2024/4/11）技术面1.站在用户角度，质量保证最核心的那部分是什么？若换一个网站，比如阅读平台，这两个系统站在测试角度，最大的差异是是什么？&nbsp;&nbsp;测试目的，推导测试2.测开和开发的区别3.未来职业规划4.操作系统的了解？5.进程不同状态转换的关系？&nbsp;&nbsp;&nbsp;6.进程同步的方式？7.如何判断bug是前端还是后端？8.个人的优点和缺点9.小米操作系统的测试10.对小米公司的理解二面（2024/4/12）技术面1.为什么要找测试的岗位2.重载&nbsp;重写&nbsp;&nbsp;隐藏3.C++空类成员函数4....
小米开奖106人在聊 双非本科求职如何逆袭 晒一晒我的offer
点赞 评论 收藏
转发
头像 头像
神奇小赛尔
04-07 20:08
已编辑
美团_测试开发(准入职员工)
点赞 评论 收藏
转发
头像
nulldybxf
04-10 16:30
集美大学诚毅学院 计算机类
点赞 评论 收藏
转发
头像
安迪很爱吃鸡腿
昨天 12:33
西安电子科技大学 计算机类
点赞 评论 收藏
转发
点赞 收藏 评论
分享

招聘动态

查看更多

滴滴

2025届秋招储备实习生招聘

联易融2024届营销管培生校园招聘

全站热榜

正在热议
# 牛友的五一计划 #
18746次浏览 383人参与
# 晒一晒我的offer #
2831555次浏览 49978人参与
# 牛客帮帮团来啦！有问必答 #
401198次浏览 7837人参与
# 无实习如何秋招上岸 #
173430次浏览 2730人参与
# 如何看待offer收割机的行为 #
194733次浏览 2990人参与
# 如何一边实习一边秋招 #
201950次浏览 4009人参与
# 华为求职进展汇总 #
442887次浏览 4446人参与
# 春招别灰心，我们一人来一句鼓励 #
21588次浏览 313人参与
# 产品实习，你更倾向大公司or小公司 #
31286次浏览 491人参与
# 非技术岗薪资爆料 #
9022次浏览 188人参与
# 硬件人的春招flag #
14569次浏览 199人参与
# 女生做医疗销售有前景吗 #
3897次浏览 49人参与
# 字节跳动工作体验 #
54057次浏览 1579人参与
# 聊聊这家公司值得去吗 #
63810次浏览 1280人参与
# 第一次面试 #
17953次浏览 277人参与
# 在国企工作的人，躺平了吗？ #
73041次浏览 883人参与
# 机械人，你的秋招第一份简历被谁挂了 #
27033次浏览 492人参与
# 来聊聊机械薪资天花板是哪家 #
22964次浏览 180人参与
# 你更愿意参加线上面试还是线下面试？ #
6992次浏览 95人参与
# 如何KTV领导 #
7559次浏览 73人参与
牛客网
牛客企业服务