a*t
2 楼
原来去大华，不过发现羊肉片好贵的。
请教各位大侠，有没有更好的地方采购羊肉片的呢？
多谢啦！！
请教各位大侠，有没有更好的地方采购羊肉片的呢？
多谢啦！！
s*s
3 楼
【 以下文字转载自 Soccer 讨论区 】
发信人: driftmit (荒漠), 信区: Soccer
标 题: 百度百科太搞了
发信站: BBS 未名空间站 (Mon Aug 15 21:17:35 2011, 美东)
http://baike.baidu.com/view/425079.htm
小法简介： 1987年5月4日，塞斯克·法布雷加斯出生在巴塞罗那以北不到40公里
的小城Arenys de Mar。这是西班牙东北部黄金海岸线上著名的旅游胜地，阳光海滩，
风景如画。 他的父亲弗兰塞斯克·法布雷加斯拥有一家地产公司，母亲努利亚·
索勒拥有一家面包店。九个月大的时候，法布雷加斯就被自己的外祖父带到了球场，观
看了一场精彩的足球比赛，小法心中埋下了足球种子。后来，法布雷加斯开始跻身巴塞
罗那青训营，可惜的是小法15岁多就离开了那里，远赴伦敦，在那里小法遇见了他的恩
师温格，开始登上了让他成为世界级中场的阿森纳。 法布雷加斯的家庭成员还包
括一个妹妹。他最喜欢的人是叔叔，除了足球最喜欢的运动是冰球，最喜欢看恐怖电影
。最喜欢的电视剧是《潜伏》。
发信人: driftmit (荒漠), 信区: Soccer
标 题: 百度百科太搞了
发信站: BBS 未名空间站 (Mon Aug 15 21:17:35 2011, 美东)
http://baike.baidu.com/view/425079.htm
小法简介： 1987年5月4日，塞斯克·法布雷加斯出生在巴塞罗那以北不到40公里
的小城Arenys de Mar。这是西班牙东北部黄金海岸线上著名的旅游胜地，阳光海滩，
风景如画。 他的父亲弗兰塞斯克·法布雷加斯拥有一家地产公司，母亲努利亚·
索勒拥有一家面包店。九个月大的时候，法布雷加斯就被自己的外祖父带到了球场，观
看了一场精彩的足球比赛，小法心中埋下了足球种子。后来，法布雷加斯开始跻身巴塞
罗那青训营，可惜的是小法15岁多就离开了那里，远赴伦敦，在那里小法遇见了他的恩
师温格，开始登上了让他成为世界级中场的阿森纳。 法布雷加斯的家庭成员还包
括一个妹妹。他最喜欢的人是叔叔，除了足球最喜欢的运动是冰球，最喜欢看恐怖电影
。最喜欢的电视剧是《潜伏》。
f*t
4 楼
检查第200条的发布时间跟现在相距是不是超过10分钟
rh
5 楼
鹿苑，不错吃哦
在atlantic & garvey
【在 a********t 的大作中提到】
: 原来去大华，不过发现羊肉片好贵的。
: 请教各位大侠，有没有更好的地方采购羊肉片的呢？
: 多谢啦！！
在atlantic & garvey
【在 a********t 的大作中提到】
: 原来去大华，不过发现羊肉片好贵的。
: 请教各位大侠，有没有更好的地方采购羊肉片的呢？
: 多谢啦！！
r*e
6 楼
哈哈,小法在阿森纳潜伏的任务终于结束了
【在 s***s 的大作中提到】
: 【 以下文字转载自 Soccer 讨论区 】
: 发信人: driftmit (荒漠), 信区: Soccer
: 标 题: 百度百科太搞了
: 发信站: BBS 未名空间站 (Mon Aug 15 21:17:35 2011, 美东)
: http://baike.baidu.com/view/425079.htm
: 小法简介： 1987年5月4日，塞斯克·法布雷加斯出生在巴塞罗那以北不到40公里
: 的小城Arenys de Mar。这是西班牙东北部黄金海岸线上著名的旅游胜地，阳光海滩，
: 风景如画。 他的父亲弗兰塞斯克·法布雷加斯拥有一家地产公司，母亲努利亚·
: 索勒拥有一家面包店。九个月大的时候，法布雷加斯就被自己的外祖父带到了球场，观
: 看了一场精彩的足球比赛，小法心中埋下了足球种子。后来，法布雷加斯开始跻身巴塞
【在 s***s 的大作中提到】
: 【 以下文字转载自 Soccer 讨论区 】
: 发信人: driftmit (荒漠), 信区: Soccer
: 标 题: 百度百科太搞了
: 发信站: BBS 未名空间站 (Mon Aug 15 21:17:35 2011, 美东)
: http://baike.baidu.com/view/425079.htm
: 小法简介： 1987年5月4日，塞斯克·法布雷加斯出生在巴塞罗那以北不到40公里
: 的小城Arenys de Mar。这是西班牙东北部黄金海岸线上著名的旅游胜地，阳光海滩，
: 风景如画。 他的父亲弗兰塞斯克·法布雷加斯拥有一家地产公司，母亲努利亚·
: 索勒拥有一家面包店。九个月大的时候，法布雷加斯就被自己的外祖父带到了球场，观
: 看了一场精彩的足球比赛，小法心中埋下了足球种子。后来，法布雷加斯开始跻身巴塞
c*1
7 楼
也就是说对于每个用户 要保存最近的200条？
这个是最优化的方法吗？
【在 f*******t 的大作中提到】
: 检查第200条的发布时间跟现在相距是不是超过10分钟
这个是最优化的方法吗？
【在 f*******t 的大作中提到】
: 检查第200条的发布时间跟现在相距是不是超过10分钟
a*t
8 楼
谢谢啦！！是已经切片好的，对吧？
【在 rh 的大作中提到】
: 鹿苑，不错吃哦
: 在atlantic & garvey
【在 rh 的大作中提到】
: 鹿苑，不错吃哦
: 在atlantic & garvey
d*e
9 楼
i think so
【在 c********1 的大作中提到】
: 也就是说对于每个用户 要保存最近的200条？
: 这个是最优化的方法吗？
【在 c********1 的大作中提到】
: 也就是说对于每个用户 要保存最近的200条？
: 这个是最优化的方法吗？
rh
10 楼
对的
【在 a********t 的大作中提到】
: 谢谢啦！！是已经切片好的，对吧？
【在 a********t 的大作中提到】
: 谢谢啦！！是已经切片好的，对吧？
f*t
11 楼
update的状态总得保存在什么地方吧
【在 c********1 的大作中提到】
: 也就是说对于每个用户 要保存最近的200条？
: 这个是最优化的方法吗？
【在 c********1 的大作中提到】
: 也就是说对于每个用户 要保存最近的200条？
: 这个是最优化的方法吗？
a*t
12 楼
谢谢！
【在 rh 的大作中提到】
: 对的
【在 rh 的大作中提到】
: 对的
c*1
13 楼
我们的task不需要保存状态 只需要检查用户的状态
是不是合法 合法的定义就是最近10分钟内是不是发送
了超过200条的status update.
应该是有更优化的方法 假设要求最近10分钟内最多
发送n条 对应每个用户应该是不需要保存n个的。。。
【在 f*******t 的大作中提到】
: update的状态总得保存在什么地方吧
是不是合法 合法的定义就是最近10分钟内是不是发送
了超过200条的status update.
应该是有更优化的方法 假设要求最近10分钟内最多
发送n条 对应每个用户应该是不需要保存n个的。。。
【在 f*******t 的大作中提到】
: update的状态总得保存在什么地方吧
l*e
14 楼
鹿苑不错，用的肉都是168里卖的羊肉，只是给切成薄片
原来我都是自己买羊肉自己切，费工费力
原来我都是自己买羊肉自己切，费工费力
i*e
15 楼
用一个循环数组。
数组长度由时间的精确度来决定。
比方说，如果要到一秒的精确度的话 size = 600.
保持一个 running sum，也就是数组内的总值。
指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
。（顺便把 running sum 递减）
随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
【在 c********1 的大作中提到】
: 我们的task不需要保存状态 只需要检查用户的状态
: 是不是合法 合法的定义就是最近10分钟内是不是发送
: 了超过200条的status update.
: 应该是有更优化的方法 假设要求最近10分钟内最多
: 发送n条 对应每个用户应该是不需要保存n个的。。。
数组长度由时间的精确度来决定。
比方说，如果要到一秒的精确度的话 size = 600.
保持一个 running sum，也就是数组内的总值。
指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
。（顺便把 running sum 递减）
随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
【在 c********1 的大作中提到】
: 我们的task不需要保存状态 只需要检查用户的状态
: 是不是合法 合法的定义就是最近10分钟内是不是发送
: 了超过200条的status update.
: 应该是有更优化的方法 假设要求最近10分钟内最多
: 发送n条 对应每个用户应该是不需要保存n个的。。。
E*T
16 楼
一个人懒就 大华买切好的。
有人伺候 就买COSTCO 的整陀， 回来拿切肉片儿的机器 切～～
又好看又好吃……
有人伺候 就买COSTCO 的整陀， 回来拿切肉片儿的机器 切～～
又好看又好吃……
c*1
17 楼
我知道这个方法 但是好像没有在原来的基础上提高啊
原来我存200个 time stamp
现在存了600个int
总之对于每个用户而言 占用的内存是线性与n的
我们的目的是要把这个线性的空间复杂度变为
const 比如说对于每个用户存3个或者4个数
0
【在 i**********e 的大作中提到】
: 用一个循环数组。
: 数组长度由时间的精确度来决定。
: 比方说，如果要到一秒的精确度的话 size = 600.
: 保持一个 running sum，也就是数组内的总值。
: 指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
: 。（顺便把 running sum 递减）
: 随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
: 这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
原来我存200个 time stamp
现在存了600个int
总之对于每个用户而言 占用的内存是线性与n的
我们的目的是要把这个线性的空间复杂度变为
const 比如说对于每个用户存3个或者4个数
0
【在 i**********e 的大作中提到】
: 用一个循环数组。
: 数组长度由时间的精确度来决定。
: 比方说，如果要到一秒的精确度的话 size = 600.
: 保持一个 running sum，也就是数组内的总值。
: 指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
: 。（顺便把 running sum 递减）
: 随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
: 这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
a*t
18 楼
原来是这样的，谢谢你啦！
【在 l*****e 的大作中提到】
: 鹿苑不错，用的肉都是168里卖的羊肉，只是给切成薄片
: 原来我都是自己买羊肉自己切，费工费力
【在 l*****e 的大作中提到】
: 鹿苑不错，用的肉都是168里卖的羊肉，只是给切成薄片
: 原来我都是自己买羊肉自己切，费工费力
H*M
19 楼
是天外飞仙吗？
只用3个int
【在 c********1 的大作中提到】
: 我知道这个方法 但是好像没有在原来的基础上提高啊
: 原来我存200个 time stamp
: 现在存了600个int
: 总之对于每个用户而言 占用的内存是线性与n的
: 我们的目的是要把这个线性的空间复杂度变为
: const 比如说对于每个用户存3个或者4个数
:
: 0
只用3个int
【在 c********1 的大作中提到】
: 我知道这个方法 但是好像没有在原来的基础上提高啊
: 原来我存200个 time stamp
: 现在存了600个int
: 总之对于每个用户而言 占用的内存是线性与n的
: 我们的目的是要把这个线性的空间复杂度变为
: const 比如说对于每个用户存3个或者4个数
:
: 0
a*t
20 楼
切肉片的机器？
那种老美的又能搅拌又能切土豆片的机器可以吗？
【在 E**********T 的大作中提到】
: 一个人懒就 大华买切好的。
: 有人伺候 就买COSTCO 的整陀， 回来拿切肉片儿的机器 切～～
: 又好看又好吃……
那种老美的又能搅拌又能切土豆片的机器可以吗？
【在 E**********T 的大作中提到】
: 一个人懒就 大华买切好的。
: 有人伺候 就买COSTCO 的整陀， 回来拿切肉片儿的机器 切～～
: 又好看又好吃……
c*1
21 楼
估计是有很巧妙的方法。。。。并且已经用在系统里了。。。
这么关心用户updates 的公司八成你也知道是哪个了
这么关心用户updates 的公司八成你也知道是哪个了
a*2
22 楼
真的需要这样省空间吗？integer来实现queue？
【在 c********1 的大作中提到】
: 估计是有很巧妙的方法。。。。并且已经用在系统里了。。。
: 这么关心用户updates 的公司八成你也知道是哪个了
【在 c********1 的大作中提到】
: 估计是有很巧妙的方法。。。。并且已经用在系统里了。。。
: 这么关心用户updates 的公司八成你也知道是哪个了
r*t
23 楼
就是算个 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
存上一次 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
24 楼
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"
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
25 楼
改变题意了。题目没有说每分钟的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"
题意允许第一分钟把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
26 楼
直接用stl的deque吧
【在 c********1 的大作中提到】
: 假设用户不停的发updates 现在想实现一个功能 就是
: 限制用户10分钟之内 最多发200条update 怎么实现？
【在 c********1 的大作中提到】
: 假设用户不停的发updates 现在想实现一个功能 就是
: 限制用户10分钟之内 最多发200条update 怎么实现？
c*1
27 楼
要求存储空间跟n没有关系。。。
【在 s****j 的大作中提到】
: 直接用stl的deque吧
【在 s****j 的大作中提到】
: 直接用stl的deque吧
s*j
28 楼
你说的n是什么？10分钟？还是200条？
deque和这两个都没关系啊
deque记录的是时间
每次push_back的时候check deque的front的时间，和当前时间差大于等于10分钟全部
pop_front，如果此时deque的size大于等于200那就不能push啊,否则就push_back
【在 c********1 的大作中提到】
: 要求存储空间跟n没有关系。。。
deque和这两个都没关系啊
deque记录的是时间
每次push_back的时候check deque的front的时间，和当前时间差大于等于10分钟全部
pop_front，如果此时deque的size大于等于200那就不能push啊,否则就push_back
【在 c********1 的大作中提到】
: 要求存储空间跟n没有关系。。。
s*j
29 楼
哦，你意思是要找o(1) space的方法？
【在 c********1 的大作中提到】
: 要求存储空间跟n没有关系。。。
【在 c********1 的大作中提到】
: 要求存储空间跟n没有关系。。。
c*1
30 楼
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
【在 s****j 的大作中提到】
: 你说的n是什么？10分钟？还是200条？
: deque和这两个都没关系啊
: deque记录的是时间
: 每次push_back的时候check deque的front的时间，和当前时间差大于等于10分钟全部
: pop_front，如果此时deque的size大于等于200那就不能push啊,否则就push_back
g*i
31 楼
板上以前讨论出来的就是这方法
0
【在 i**********e 的大作中提到】
: 用一个循环数组。
: 数组长度由时间的精确度来决定。
: 比方说，如果要到一秒的精确度的话 size = 600.
: 保持一个 running sum，也就是数组内的总值。
: 指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
: 。（顺便把 running sum 递减）
: 随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
: 这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
0
【在 i**********e 的大作中提到】
: 用一个循环数组。
: 数组长度由时间的精确度来决定。
: 比方说，如果要到一秒的精确度的话 size = 600.
: 保持一个 running sum，也就是数组内的总值。
: 指针指向数组其中一个位置，然后随着时间往前走。走到当前位置先初始化数组值为0
: 。（顺便把 running sum 递减）
: 随着用户发送新信息，增加 running sum 并且 +1 当前数组值。
: 这样我们随时随地就能立即知道用户是否超过了 200 次发送信息。
c*1
32 楼
恩 我知道 我回答的就是这个方法
面试官说可以存const 空间
但是没跟我说怎么做
搞的我最近一直在想这个。。。
【在 g*****i 的大作中提到】
: 板上以前讨论出来的就是这方法
:
: 0
面试官说可以存const 空间
但是没跟我说怎么做
搞的我最近一直在想这个。。。
【在 g*****i 的大作中提到】
: 板上以前讨论出来的就是这方法
:
: 0
s*j
33 楼
恩，我理解你的意思了
O(1)space的暂时没想法
O(n)的就看时间和允许条数哪个大了吧
时间range小就用1337的那个方法
【在 c********1 的大作中提到】
: n是200 你那样worst case 要存200条time stamp
O(1)space的暂时没想法
O(n)的就看时间和允许条数哪个大了吧
时间range小就用1337的那个方法
【在 c********1 的大作中提到】
: n是200 你那样worst case 要存200条time stamp
r*t
34 楼
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?
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
35 楼
题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
等待呢? 我觉得这个写法对你说的这个情况是没问题的。
【在 n*******w 的大作中提到】
: 改变题意了。题目没有说每分钟的quota是一样的。
: 题意允许第一分钟把quota用完，接下来9分钟等待。
: 唯一想到的解法就是1337写的那样。circular queue。
: 如果要精确到毫秒微妙的话，存每个update以及时间。
等待呢? 我觉得这个写法对你说的这个情况是没问题的。
【在 n*******w 的大作中提到】
: 改变题意了。题目没有说每分钟的quota是一样的。
: 题意允许第一分钟把quota用完，接下来9分钟等待。
: 唯一想到的解法就是1337写的那样。circular queue。
: 如果要精确到毫秒微妙的话，存每个update以及时间。
n*w
36 楼
那个伪码有一些bug吧。改好了能比较准确的说具体的问题。不然不是完全了解怎么
work。
【在 r****t 的大作中提到】
: 题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
: 等待呢? 我觉得这个写法对你说的这个情况是没问题的。
work。
【在 r****t 的大作中提到】
: 题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
: 等待呢? 我觉得这个写法对你说的这个情况是没问题的。
c*1
37 楼
可以解释下算法吗
感觉不太对呢。。。
【在 r****t 的大作中提到】
: 题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
: 等待呢? 我觉得这个写法对你说的这个情况是没问题的。
感觉不太对呢。。。
【在 r****t 的大作中提到】
: 题目没有提到 quota，不过为啥这个解法就不允许第一分钟把quota用完，接下来9分钟
: 等待呢? 我觉得这个写法对你说的这个情况是没问题的。
r*t
38 楼
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。
for n allowed messages in k minutes.
【在 n*******w 的大作中提到】
: 那个伪码有一些bug吧。改好了能比较准确的说具体的问题。不然不是完全了解怎么
: work。
相关阅读
厉害国不厉害了: 习近平指出无论将来中国怎么发展都永远属于图片连女鬼都不想勾搭你Re: 未来自动驾驶和电动车将改变湾区房价布局 (转载)不宜一双玉臂千人枕，青楼女子这上联无人能对老师课上和我们说西门庆的故事图片大保健来了 (转载)Re: 放军恢复中断二十年的刺杀训练 (转载)看看你的星座，适合养什么狗？坏人在森林里放了好大1块镜子 (转载)要给人民领袖明年阅兵：天安门城楼贴金箔 (转载)人前人后的2中装B风格 了解一下!对前女友霸王硬上弓的后果......小鲜肉骗钱，他美女姐姐就肉偿kuaishou大家这么喜欢看车祸老中都他妈刷题刷傻了，看白马工怎么拿Google的offer (转载)老婆偷情、丈夫不敢过去打扰！只能.......