h*****g
发帖数: 312 | 1 A period of time where users login and logout, given a sets of login and
logout time pairs, write a function that can show the number of users online
at any given time.
http://www.glassdoor.com/Interview/A-period-of-time-where-users
我感觉直接scan 就行啊 从头到尾 看在哪个区间里， O(n)?
glassdoor 上给的answer 怎么那么复杂呢？ 又sort, 又用什么tree的？ | w****x
发帖数: 2483 | 2 就是排序所有时间端点, 然后那个时间点上begin points - end points就是当前在线
人数 | L***Q
发帖数: 508 | 3 我估计这题的意思是给定一个login/logout 时间的set，每次给你一个time，你的
function返回那个time在线人数。
那么每次function都去scan一遍效率就挺低了。应该是有个预处理，然后给一个time，
能很快返回在线人数，不需要去scan原来的set。
我瞎猜的哈
online
【在 h*****g 的大作中提到】
: A period of time where users login and logout, given a sets of login and
: logout time pairs, write a function that can show the number of users online
: at any given time.
: http://www.glassdoor.com/Interview/A-period-of-time-where-users
: 我感觉直接scan 就行啊 从头到尾 看在哪个区间里， O(n)?
: glassdoor 上给的answer 怎么那么复杂呢？ 又sort, 又用什么tree的？
| w****x
发帖数: 2483 | 4
预处理因该就是, 还是先按时间端点排序, 遍历一遍时间小段, 记录时间小段的在线人
数, 就是根据开始点-结束点算, 对于给定时间点做binary search定位到时间小段并返
回在线人数
【在 L***Q 的大作中提到】
: 我估计这题的意思是给定一个login/logout 时间的set，每次给你一个time，你的
: function返回那个time在线人数。
: 那么每次function都去scan一遍效率就挺低了。应该是有个预处理，然后给一个time，
: 能很快返回在线人数，不需要去scan原来的set。
: 我瞎猜的哈
:
: online
| h*****g
发帖数: 312 | 5 en it is reasonable
【在 L***Q 的大作中提到】
: 我估计这题的意思是给定一个login/logout 时间的set，每次给你一个time，你的
: function返回那个time在线人数。
: 那么每次function都去scan一遍效率就挺低了。应该是有个预处理，然后给一个time，
: 能很快返回在线人数，不需要去scan原来的set。
: 我瞎猜的哈
:
: online
| p*****2
发帖数: 21240 | 6 a period of time是多大，given time的单位是什么。 | p*****2
发帖数: 21240 | 7
能详细再谈一下吗。这题我想研究一下。你是按start排序吗？
【在 w****x 的大作中提到】
:
: 预处理因该就是, 还是先按时间端点排序, 遍历一遍时间小段, 记录时间小段的在线人
: 数, 就是根据开始点-结束点算, 对于给定时间点做binary search定位到时间小段并返
: 回在线人数
| w****x
发帖数: 2483 | 8
1. 任何一个时间段(login time & logout time)都是由两个端点(login logout)组成,
首先不分端点是login还是logout对所有端点排序. 然后遍历整个数轴, 对每个端点和
端点之间的小段, 记录其在线人数(当前的login端点数 - 当前logout端点数), 这步是
算预处理, O(n)
2. 因为用户login, logout都是按时间顺序的, 所以可以很轻松的动态维护这个数轴.
3. 当需要查询一个时间点用户数的时候, 用binary search找出这个时间点坐落于哪个
时间小段, 这个时间小段对应的在线用户数就是答案(logn)
【在 p*****2 的大作中提到】
:
: 能详细再谈一下吗。这题我想研究一下。你是按start排序吗？
| p*****2
发帖数: 21240 | 9
成,
第一步最复杂，比如{1,3}, {5,7}
你首先得把1,3,5,7放到一个数组里排序吧？
然后你找小段
{1,3} 你要遍历一边所有的{login, logout} 找总数吗？
【在 w****x 的大作中提到】
:
: 1. 任何一个时间段(login time & logout time)都是由两个端点(login logout)组成,
: 首先不分端点是login还是logout对所有端点排序. 然后遍历整个数轴, 对每个端点和
: 端点之间的小段, 记录其在线人数(当前的login端点数 - 当前logout端点数), 这步是
: 算预处理, O(n)
: 2. 因为用户login, logout都是按时间顺序的, 所以可以很轻松的动态维护这个数轴.
: 3. 当需要查询一个时间点用户数的时候, 用binary search找出这个时间点坐落于哪个
: 时间小段, 这个时间小段对应的在线用户数就是答案(logn)
| w****x
发帖数: 2483 | 10
举个例子{1, 5} {2, 6} {3, 4}
==> 1(in), 2(in), 3(in), 4(out), 5(out), 6(out)
==>维护一个计数, 遇到login的+1, logout的-1
==>遍历时间点的所有小段:
<1,2> --> 1 <2,3> -->1+1 = 2 <3, 4> --> 2+1 = 3
<4, 5> --> 3 - 1 = 2 <5, 6> --> 2 - 1 = 1 <6, +无穷> --> 1 - 1 = 0
==>给各时间比如4.3, 做binary search 找到对应的小段 --> <4, 5> -->在线人数是
2
"你要遍历一边所有的{login, logout} 找总数吗" -->当然不用, 如果有cover住{1, 3}的
会有一个login point在1前面或{1,3}中间,in which case {1,3}就不算一个小段了
【在 p*****2 的大作中提到】
:
: 成,
: 第一步最复杂，比如{1,3}, {5,7}
: 你首先得把1,3,5,7放到一个数组里排序吧？
: 然后你找小段
: {1,3} 你要遍历一边所有的{login, logout} 找总数吗？
| | | s******t
发帖数: 169 | 11 离散化+线段树可以做，或者离散化+树状数组，对于每个pair，直接插入，时间为log(
n)，总共为nlog(n)。然后查询的时候，每次查询log(n)
wwwyhx说的本质上就是离散化吧，如果我没理解错的话。本质上相当于把一个相当大的
区间离散成较小的区间，比如说有一个对是(1,100000)另一个是(2,300000)，真用一个
300000的数组去存就不太划算了，其实把几个点排下序然后离散化，4个点就可以 | w****x
发帖数: 2483 | 12
log(
不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如
struct TIME_POINT
{
bool bLogin;
float fTimePoint;
};
如果拿300000来做, 直接都不用binary search了
【在 s******t 的大作中提到】
: 离散化+线段树可以做，或者离散化+树状数组，对于每个pair，直接插入，时间为log(
: n)，总共为nlog(n)。然后查询的时候，每次查询log(n)
: wwwyhx说的本质上就是离散化吧，如果我没理解错的话。本质上相当于把一个相当大的
: 区间离散成较小的区间，比如说有一个对是(1,100000)另一个是(2,300000)，真用一个
: 300000的数组去存就不太划算了，其实把几个点排下序然后离散化，4个点就可以
| z*y
发帖数: 1311 | 13
online
每个user是一个区间，query是一个点
用interval tree
【在 h*****g 的大作中提到】
: A period of time where users login and logout, given a sets of login and
: logout time pairs, write a function that can show the number of users online
: at any given time.
: http://www.glassdoor.com/Interview/A-period-of-time-where-users
: 我感觉直接scan 就行啊 从头到尾 看在哪个区间里， O(n)?
: glassdoor 上给的answer 怎么那么复杂呢？ 又sort, 又用什么tree的？
| p*****2
发帖数: 21240 | 14
3}的
不错的idea。赞一个。
【在 w****x 的大作中提到】
:
: log(
: 不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如
: struct TIME_POINT
: {
: bool bLogin;
: float fTimePoint;
: };
: 如果拿300000来做, 直接都不用binary search了
| p*****2
发帖数: 21240 | 15
3}的
要不要搞一个可以动态添加{login,longout}的算法呢？
感觉应用上应该是动态添加的吧？
【在 w****x 的大作中提到】
:
: log(
: 不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如
: struct TIME_POINT
: {
: bool bLogin;
: float fTimePoint;
: };
: 如果拿300000来做, 直接都不用binary search了
| w****x
发帖数: 2483 | 16
所有的user的login logout时间都是自然按顺序的, 因该没啥问题.维护一个integer代
表当前用户数, login一个产生一个时间小段, 就是integer++, logout 一个又产生一
个时间小段, integer--
【在 p*****2 的大作中提到】
:
: 3}的
: 要不要搞一个可以动态添加{login,longout}的算法呢？
: 感觉应用上应该是动态添加的吧？
| p*****2
发帖数: 21240 | 17
login, logout产生是以logout为主的。所以login可能是很早以前。这样就需要更新以
前有overlap的小段。
【在 w****x 的大作中提到】
:
: 所有的user的login logout时间都是自然按顺序的, 因该没啥问题.维护一个integer代
: 表当前用户数, login一个产生一个时间小段, 就是integer++, logout 一个又产生一
: 个时间小段, integer--
| w****x
发帖数: 2483 | 18
不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况
, 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那
之后不管登陆登出9点到10点这个历史在线人数永远不会改变
【在 p*****2 的大作中提到】
:
: login, logout产生是以logout为主的。所以login可能是很早以前。这样就需要更新以
: 前有overlap的小段。
| h*****g
发帖数: 312 | 19 niu
3}的
【在 w****x 的大作中提到】
:
: 不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况
: , 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那
: 之后不管登陆登出9点到10点这个历史在线人数永远不会改变
| p*****2
发帖数: 21240 | 20
我想到的是logout以后在把数据加入进来。不过确实即使没有logout，login也应该算
进去。
【在 w****x 的大作中提到】
:
: 不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况
: , 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那
: 之后不管登陆登出9点到10点这个历史在线人数永远不会改变
| c****p
发帖数: 6474 | 21 把所有事件在时间轴上排序。
如果数据源是log的话直接按顺序插入就好了。
时间轴上的事件点保留两个信息就可以了：<时间，当前在线人数>
对于相连的、发生在T_i和T_i+1的两个事件，时间段[T_i, T_i+1)的在线人数就等于T_
i事件的当前在线人数。
应该不用考虑记录的增删问题，要加也是在数轴的后端加，不会影响已排序部分。【
在 huameng (huameng) 的大作中提到: 】
online | C***U
发帖数: 2406 | 22 这个题目和interval相交个数那个差不多
可以转换成数括号
A period of time where users login and logout, given a sets of login and
logout time pai........
★ Sent from iPhone App: iReader Mitbbs 7.52 - iPad Lite
【在 h*****g 的大作中提到】
: A period of time where users login and logout, given a sets of login and
: logout time pairs, write a function that can show the number of users online
: at any given time.
: http://www.glassdoor.com/Interview/A-period-of-time-where-users
: 我感觉直接scan 就行啊 从头到尾 看在哪个区间里， O(n)?
: glassdoor 上给的answer 怎么那么复杂呢？ 又sort, 又用什么tree的？
|
|
