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: 小留们，小五毛们，别再跟我抢女人了 (转载)想起年轻时做过的缺德事，夜不能寐 (转载)学术一下，汽车防水袋的使用埃及奥运代表团缺钱只能穿假货，nike牌的衣服上拉链上是adidas(转载)zz最流行的11个成人笑话，你懂多少？（答案）钓鱼趣帖 zz考拉睡觉被鸟啄，飞身逃跑麋鹿兄弟你妹！zz小伙子，你是来寻开心的吧。为艺术变身的蝙蝠侠奇怪颜色的动物 (转载)学术学习：这个神经科学有才啊，借用别人的文章混国内特聘回放方舟子打假傅瑾电话采访, 2B主持人亮了!【视频】 (转载)武汉恐怖片：午夜来袭我倒是觉得遗产税是美国强大的真正原因这是神马片子！打斗的也太激烈了～给你们这么一说，啥能喝？一个iPhone4S的真实故事 (转载)