c********1
发帖数: 52 | 1 假设用户不停的发updates 现在想实现一个功能 就是
限制用户10分钟之内 最多发200条update 怎么实现？ |
f*******t
发帖数: 7549 | 2 检查第200条的发布时间跟现在相距是不是超过10分钟 |
c********1
发帖数: 52 | 3 也就是说对于每个用户 要保存最近的200条？
这个是最优化的方法吗？
【在 f*******t 的大作中提到】
: 检查第200条的发布时间跟现在相距是不是超过10分钟
|
d**e
发帖数: 6098 | 4 i think so
【在 c********1 的大作中提到】
: 也就是说对于每个用户 要保存最近的200条？
: 这个是最优化的方法吗？
|
f*******t
发帖数: 7549 | 5 update的状态总得保存在什么地方吧
【在 c********1 的大作中提到】
: 也就是说对于每个用户 要保存最近的200条？
: 这个是最优化的方法吗？
|
c********1
发帖数: 52 | 6 我们的task不需要保存状态 只需要检查用户的状态
是不是合法 合法的定义就是最近10分钟内是不是发送
了超过200条的status update.
应该是有更优化的方法 假设要求最近10分钟内最多
发送n条 对应每个用户应该是不需要保存n个的。。。
【在 f*******t 的大作中提到】
: update的状态总得保存在什么地方吧
|
i**********e
发帖数: 1145 | 7 用一个循环数组。
数组长度由时间的精确度来决定。
比方说，如果要到一秒的精确度的话 size = 600.
保持一个 running sum，也就是数组内的总值。
指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
。（顺便把 running sum 递减）
随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
【在 c********1 的大作中提到】
: 我们的task不需要保存状态 只需要检查用户的状态
: 是不是合法 合法的定义就是最近10分钟内是不是发送
: 了超过200条的status update.
: 应该是有更优化的方法 假设要求最近10分钟内最多
: 发送n条 对应每个用户应该是不需要保存n个的。。。
|
c********1
发帖数: 52 | 8 我知道这个方法 但是好像没有在原来的基础上提高啊
原来我存200个 time stamp
现在存了600个int
总之对于每个用户而言 占用的内存是线性与n的
我们的目的是要把这个线性的空间复杂度变为
const 比如说对于每个用户存3个或者4个数
0
【在 i**********e 的大作中提到】
: 用一个循环数组。
: 数组长度由时间的精确度来决定。
: 比方说，如果要到一秒的精确度的话 size = 600.
: 保持一个 running sum，也就是数组内的总值。
: 指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
: 。（顺便把 running sum 递减）
: 随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
: 这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
|
H*M
发帖数: 1268 | 9 是天外飞仙吗？
只用3个int
【在 c********1 的大作中提到】
: 我知道这个方法 但是好像没有在原来的基础上提高啊
: 原来我存200个 time stamp
: 现在存了600个int
: 总之对于每个用户而言 占用的内存是线性与n的
: 我们的目的是要把这个线性的空间复杂度变为
: const 比如说对于每个用户存3个或者4个数
:
: 0
|
c********1
发帖数: 52 | 10 估计是有很巧妙的方法。。。。并且已经用在系统里了。。。
这么关心用户updates 的公司八成你也知道是哪个了 |
|
|
a**********2
发帖数: 340 | 11 真的需要这样省空间吗？integer来实现queue？
【在 c********1 的大作中提到】
: 估计是有很巧妙的方法。。。。并且已经用在系统里了。。。
: 这么关心用户updates 的公司八成你也知道是哪个了
|
r****t
发帖数: 10904 | 12 就是算个 quota 把，一个用户一个变量 quota, 一个变量 last_t
存上一次 update 的时间就好了。
quota_rate = max_quota / (10*60.)
def new_message(self, msg):
t = now()
quota += (t - self.last_t) * quota_rate
quota = quota if quota <= max_quota else max_quota
quota --
if quota<0:
raise "updates too frequently"
else:
send_msg(msg)
self.last_t = t |
m*****k
发帖数: 731 | 13 so can not post 1 update in min 1st and then idle then update 99 posts in
min 10th?
【在 r****t 的大作中提到】
: 就是算个 quota 把，一个用户一个变量 quota, 一个变量 last_t
: 存上一次 update 的时间就好了。
: quota_rate = max_quota / (10*60.)
: def new_message(self, msg):
: t = now()
: quota += (t - self.last_t) * quota_rate
: quota = quota if quota <= max_quota else max_quota
: quota --
: if quota<0:
: raise "updates too frequently"
|
n*******w
发帖数: 687 | 14 改变题意了。题目没有说每分钟的quota是一样的。
题意允许第一分钟把quota用完，接下来9分钟等待。
唯一想到的解法就是1337写的那样。circular queue。
如果要精确到毫秒微妙的话，存每个update以及时间。
【在 r****t 的大作中提到】
: 就是算个 quota 把，一个用户一个变量 quota, 一个变量 last_t
: 存上一次 update 的时间就好了。
: quota_rate = max_quota / (10*60.)
: def new_message(self, msg):
: t = now()
: quota += (t - self.last_t) * quota_rate
: quota = quota if quota <= max_quota else max_quota
: quota --
: if quota<0:
: raise "updates too frequently"
|
s****j
发帖数: 67 | 15 直接用stl的deque吧
【在 c********1 的大作中提到】
: 假设用户不停的发updates 现在想实现一个功能 就是
: 限制用户10分钟之内 最多发200条update 怎么实现？
|
c********1
发帖数: 52 | 16 要求存储空间跟n没有关系。。。
【在 s****j 的大作中提到】
: 直接用stl的deque吧
|
s****j
发帖数: 67 | 17 你说的n是什么？10分钟？还是200条？
deque和这两个都没关系啊
deque记录的是时间
每次push_back的时候check deque的front的时间，和当前时间差大于等于10分钟全部
pop_front，如果此时deque的size大于等于200那就不能push啊,否则就push_back
【在 c********1 的大作中提到】
: 要求存储空间跟n没有关系。。。
|
s****j
发帖数: 67 | 18 哦，你意思是要找o(1) space的方法？
【在 c********1 的大作中提到】
: 要求存储空间跟n没有关系。。。
|
c********1
发帖数: 52 | 19 n是200 你那样worst case 要存200条time stamp
【在 s****j 的大作中提到】
: 你说的n是什么？10分钟？还是200条？
: deque和这两个都没关系啊
: deque记录的是时间
: 每次push_back的时候check deque的front的时间，和当前时间差大于等于10分钟全部
: pop_front，如果此时deque的size大于等于200那就不能push啊,否则就push_back
|
g*****i
发帖数: 2162 | 20 板上以前讨论出来的就是这方法
0
【在 i**********e 的大作中提到】
: 用一个循环数组。
: 数组长度由时间的精确度来决定。
: 比方说，如果要到一秒的精确度的话 size = 600.
: 保持一个 running sum，也就是数组内的总值。
: 指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
: 。（顺便把 running sum 递减）
: 随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
: 这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
|
|
|
c********1
发帖数: 52 | 21 恩 我知道 我回答的就是这个方法
面试官说可以存const 空间
但是没跟我说怎么做
搞的我最近一直在想这个。。。
【在 g*****i 的大作中提到】
: 板上以前讨论出来的就是这方法
:
: 0
|
s****j
发帖数: 67 | 22 恩，我理解你的意思了
O(1)space的暂时没想法
O(n)的就看时间和允许条数哪个大了吧
时间range小就用1337的那个方法
【在 c********1 的大作中提到】
: n是200 你那样worst case 要存200条time stamp
|
r****t
发帖数: 10904 | 23 I forgot to make quota a member and init it to 100, that way u can do 1 in
1st min and 99 in the 9th min. just a thought. will check back later.
【在 m*****k 的大作中提到】
: so can not post 1 update in min 1st and then idle then update 99 posts in
: min 10th?
|
r****t
发帖数: 10904 | 24 题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
等待呢? 我觉得这个写法对你说的这个情况是没问题的。
【在 n*******w 的大作中提到】
: 改变题意了。题目没有说每分钟的quota是一样的。
: 题意允许第一分钟把quota用完，接下来9分钟等待。
: 唯一想到的解法就是1337写的那样。circular queue。
: 如果要精确到毫秒微妙的话，存每个update以及时间。
|
n*******w
发帖数: 687 | 25 那个伪码有一些bug吧。改好了能比较准确的说具体的问题。不然不是完全了解怎么
work。
【在 r****t 的大作中提到】
: 题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
: 等待呢? 我觉得这个写法对你说的这个情况是没问题的。
|
c********1
发帖数: 52 | 26 可以解释下算法吗
感觉不太对呢。。。
【在 r****t 的大作中提到】
: 题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
: 等待呢? 我觉得这个写法对你说的这个情况是没问题的。
|
r****t
发帖数: 10904 | 27 never mind. I see why my solution only allows n-k msgs in the first minute
for n allowed messages in k minutes.
【在 n*******w 的大作中提到】
: 那个伪码有一些bug吧。改好了能比较准确的说具体的问题。不然不是完全了解怎么
: work。
|
