logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
美鸡待价而沽 (转载)
avatar
美鸡待价而沽 (转载)# Joke - 肚皮舞运动
h*g
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的？
avatar
i*p
2 楼
对方希望不用保险，自己讨钱。
找了几个bodyshop估了一下，起码要600到800块钱。
其实蹭得也不太厉害，觉得要对方掏那么多钱多了点。但是车还挺新的，不修又很难看
。不知道有没有
简单的办法我自己可以修，对方掏材料钱就可以了。
avatar
l*r
3 楼
【 以下文字转载自 Seattle 讨论区 】
发信人: watermore (water3m), 信区: Seattle
标 题: 美鸡待价而沽
关键字: 鸡，蛋，宠物。
发信站: BBS 未名空间站 (Sat Jan 28 18:26:27 2012, 美东)
美丽的黑白羽毛。下棕色的蛋。平均5蛋／week。现在正是她们俩的active产蛋期。 一
直放养。友好，与人亲近，很安静，是不错的后院宠物。出售原因：家中的小朋友移情
别物，我们也比较忙，没太多时间照顾她们。
$30 each, some free chicken food and wood chips to go with. You may check
craglist for price reference.
有意者请站内联系。
avatar
w*x
4 楼
就是排序所有时间端点, 然后那个时间点上begin points - end points就是当前在线
人数
avatar
w*n
5 楼
还第一次遇到这么实在的

【在 i***p 的大作中提到】
: 对方希望不用保险，自己讨钱。
: 找了几个bodyshop估了一下，起码要600到800块钱。
: 其实蹭得也不太厉害，觉得要对方掏那么多钱多了点。但是车还挺新的，不修又很难看
: 。不知道有没有
: 简单的办法我自己可以修，对方掏材料钱就可以了。
avatar
L*Q
6 楼
我估计这题的意思是给定一个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的？
avatar
h*n
7 楼
太实在了
朋友么?

【在 i***p 的大作中提到】
: 对方希望不用保险，自己讨钱。
: 找了几个bodyshop估了一下，起码要600到800块钱。
: 其实蹭得也不太厉害，觉得要对方掏那么多钱多了点。但是车还挺新的，不修又很难看
: 。不知道有没有
: 简单的办法我自己可以修，对方掏材料钱就可以了。
avatar
w*x
8 楼

预处理因该就是, 还是先按时间端点排序, 遍历一遍时间小段, 记录时间小段的在线人
数, 就是根据开始点-结束点算, 对于给定时间点做binary search定位到时间小段并返
回在线人数

【在 L***Q 的大作中提到】
: 我估计这题的意思是给定一个login/logout 时间的set，每次给你一个time，你的
: function返回那个time在线人数。
: 那么每次function都去scan一遍效率就挺低了。应该是有个预处理，然后给一个time，
: 能很快返回在线人数，不需要去scan原来的set。
: 我瞎猜的哈
:
: online
avatar
i*p
9 楼
不是，但是是同胞。

【在 h****n 的大作中提到】
: 太实在了
: 朋友么?
avatar
h*g
10 楼
en it is reasonable

【在 L***Q 的大作中提到】
: 我估计这题的意思是给定一个login/logout 时间的set，每次给你一个time，你的
: function返回那个time在线人数。
: 那么每次function都去scan一遍效率就挺低了。应该是有个预处理，然后给一个time，
: 能很快返回在线人数，不需要去scan原来的set。
: 我瞎猜的哈
:
: online
avatar
M*s
11 楼
如果对方是Toyota，可以告自动加速，这样两边钱都省下来了
avatar
p*2
12 楼
a period of time是多大，given time的单位是什么。
avatar
v*z
13 楼
yes, if you have the tool.
I can lend you my tools if in ca.
avatar
p*2
14 楼

能详细再谈一下吗。这题我想研究一下。你是按start排序吗？

【在 w****x 的大作中提到】
:
: 预处理因该就是, 还是先按时间端点排序, 遍历一遍时间小段, 记录时间小段的在线人
: 数, 就是根据开始点-结束点算, 对于给定时间点做binary search定位到时间小段并返
: 回在线人数
avatar
i*p
15 楼
what tool do I need? Maybe I can buy one.

【在 v*****z 的大作中提到】
: yes, if you have the tool.
: I can lend you my tools if in ca.
avatar
w*x
16 楼

1. 任何一个时间段(login time & logout time)都是由两个端点(login logout)组成,
首先不分端点是login还是logout对所有端点排序. 然后遍历整个数轴, 对每个端点和
端点之间的小段, 记录其在线人数(当前的login端点数 - 当前logout端点数), 这步是
算预处理, O(n)
2. 因为用户login, logout都是按时间顺序的, 所以可以很轻松的动态维护这个数轴.
3. 当需要查询一个时间点用户数的时候, 用binary search找出这个时间点坐落于哪个
时间小段, 这个时间小段对应的在线用户数就是答案(logn)

【在 p*****2 的大作中提到】
:
: 能详细再谈一下吗。这题我想研究一下。你是按start排序吗？
avatar
l*i
17 楼
painting 能自己做
avatar
p*2
18 楼

成,
第一步最复杂，比如{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)
avatar
c*n
19 楼
难怪难怪, 看你的照片是江南美女啊, 这里哪个猥琐男不想蹭你?

【在 i***p 的大作中提到】
: 对方希望不用保险，自己讨钱。
: 找了几个bodyshop估了一下，起码要600到800块钱。
: 其实蹭得也不太厉害，觉得要对方掏那么多钱多了点。但是车还挺新的，不修又很难看
: 。不知道有没有
: 简单的办法我自己可以修，对方掏材料钱就可以了。
avatar
w*x
20 楼

举个例子{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} 找总数吗？
avatar
K*r
21 楼
PAINT自己做如果没点经验的话会做的大花脸，而且很麻烦
avatar
s*t
22 楼
离散化+线段树可以做，或者离散化+树状数组，对于每个pair，直接插入，时间为log(
n)，总共为nlog(n)。然后查询的时候，每次查询log(n)
wwwyhx说的本质上就是离散化吧，如果我没理解错的话。本质上相当于把一个相当大的
区间离散成较小的区间，比如说有一个对是(1,100000)另一个是(2,300000)，真用一个
300000的数组去存就不太划算了，其实把几个点排下序然后离散化，4个点就可以
avatar
j*e
23 楼
同问，怎么操作。
我蹭pickup把自己的防擦条全给蹭了，还好对方屁事没有。

【在 l********i 的大作中提到】
: painting 能自己做
avatar
w*x
24 楼

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个点就可以
avatar
z*y
25 楼

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的？
avatar
p*2
26 楼

3}的
不错的idea。赞一个。

【在 w****x 的大作中提到】
:
: log(
: 不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如
: struct TIME_POINT
: {
: bool bLogin;
: float fTimePoint;
: };
: 如果拿300000来做, 直接都不用binary search了
avatar
p*2
27 楼

3}的
要不要搞一个可以动态添加{login,longout}的算法呢？
感觉应用上应该是动态添加的吧？

【在 w****x 的大作中提到】
:
: log(
: 不用真的拿300000的来做啊, 这么做的话float就没法整了, 就用结构体就可以了, 比如
: struct TIME_POINT
: {
: bool bLogin;
: float fTimePoint;
: };
: 如果拿300000来做, 直接都不用binary search了
avatar
w*x
28 楼

所有的user的login logout时间都是自然按顺序的, 因该没啥问题.维护一个integer代
表当前用户数, login一个产生一个时间小段, 就是integer++, logout 一个又产生一
个时间小段, integer--

【在 p*****2 的大作中提到】
:
: 3}的
: 要不要搞一个可以动态添加{login,longout}的算法呢？
: 感觉应用上应该是动态添加的吧？
avatar
p*2
29 楼

login, logout产生是以logout为主的。所以login可能是很早以前。这样就需要更新以
前有overlap的小段。

【在 w****x 的大作中提到】
:
: 所有的user的login logout时间都是自然按顺序的, 因该没啥问题.维护一个integer代
: 表当前用户数, login一个产生一个时间小段, 就是integer++, logout 一个又产生一
: 个时间小段, integer--
avatar
w*x
30 楼

不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况
, 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那
之后不管登陆登出9点到10点这个历史在线人数永远不会改变

【在 p*****2 的大作中提到】
:
: login, logout产生是以logout为主的。所以login可能是很早以前。这样就需要更新以
: 前有overlap的小段。
avatar
h*g
31 楼
niu

3}的

【在 w****x 的大作中提到】
:
: 不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况
: , 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那
: 之后不管登陆登出9点到10点这个历史在线人数永远不会改变
avatar
p*2
32 楼

我想到的是logout以后在把数据加入进来。不过确实即使没有logout，login也应该算
进去。

【在 w****x 的大作中提到】
:
: 不需要, 以前的小段代表在那个时间段有多少人在线, 过了那个时间段不管是什么情况
: , 历史数据都不会改变. 比如我<9, 10> ==> 100, 代表9点到10点100人恒定在线, 那
: 之后不管登陆登出9点到10点这个历史在线人数永远不会改变
avatar
c*p
33 楼
把所有事件在时间轴上排序。
如果数据源是log的话直接按顺序插入就好了。
时间轴上的事件点保留两个信息就可以了：
对于相连的、发生在T_i和T_i+1的两个事件，时间段[T_i, T_i+1)的在线人数就等于T_
i事件的当前在线人数。
应该不用考虑记录的增删问题，要加也是在数轴的后端加，不会影响已排序部分。【
在 huameng (huameng) 的大作中提到: 】
online
avatar
C*U
34 楼
这个题目和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的？
相关阅读
路和鞋的质量都不错BB的小二太牛鼻了 (转载)师姐搂着师弟（重口味）压力好大妇女能踢半边天。。人的气质 (转载)【视频】央视女记者被村主任推倒在地掐脖子 (转载)女总理手搭奥巴马臀部 脸红照片【图书管理员】1919年，他27岁，是北京大学的图书管理员 (转载)飞机上看到的一幕，震撼了！真正的重口味，以前的重口味都弱爆了！！！发包子内涵公益广告师兄跪别师妹最近跟漂亮MM谈恋爱，请大家推荐几本英文哲学书 (转载)定语真强大微软企图用免费培根吸引谷歌亚麻人士zz我真吃不下了，别让我吃了发嗲搞基版三国：曹操喊干干的时候，瞬间阵亡了 (转载)老公是同性恋出轨，对象是男人，要跟我离婚，我跟老公不到2岁的(转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。