b******6
发帖数: 38 | 1 一个快餐店内一排N个座位，顾客进来后随机选位置，唯一的限制条件是不远已经有人
坐下的相邻位置。这样只到所有可选位置都被占。问题是最终被顾客坐下的位置的百分
比的mean, std.只要求给出N=25和50000时的数值解。 |
s****h
发帖数: 3979 | 2 题目看不懂
第一句很有趣，可是不知道问的是啥？
看懂的解释一下？
25个顾客一起进的话，最多只有13个坐下，剩下12个离开？
1M个顾客的流水席，同时在座位上的人在1-13之间，25个座位都会被坐到吧。 |
b******6
发帖数: 38 | 3 sorry, 这里有错别字“唯一的限制条件是不选已经有人坐下的相邻位置。”就是新来
的顾客选座位会和已经有人的地方相隔至少一个位置。等所有这样的位置没有了
，给出百分比的答案。比如25个座位，最多只可能坐13个人，也可能少于13, 但是不会
是只有一个， 最终两个顾客间最多可以相隔两个空座 相隔三个的话就能多坐一个人了
，求平均值
和平均方差？ 一个更简单的例子，N=3,最终的情况可能是*-*, -*-, *-*（*表示有人
， -表示没人）,这样平均值是1/3×(2/3+1/3+2/3)=5/9。 |
s****h
发帖数: 3979 | 4 貌似比较难啊
F(N) 是N个座位时顾客数的mean,
F(neg) = F(0) = 0
F(1) = F(2) = 1
F(3) = 5/3
有递推公式：F(N) = 1 + 1/N * sum(i from －1 to N-2) ( F(i) + F(N-3-i)
写个程序可以算出来。
用笔算就不会了。 |
b******6
发帖数: 38 | 5 嗯，这个和我想得差不多，那std呢，可以递推吗？
【在 s****h 的大作中提到】
: 貌似比较难啊
: F(N) 是N个座位时顾客数的mean,
: F(neg) = F(0) = 0
: F(1) = F(2) = 1
: F(3) = 5/3
: 有递推公式：F(N) = 1 + 1/N * sum(i from －1 to N-2) ( F(i) + F(N-3-i)
: 写个程序可以算出来。
: 用笔算就不会了。
|
s****h
发帖数: 3979 | 6 std的公式就复杂了。
需要sum(i from -1 to N-2, j from -1 to N-2) F(i) * F(j) 之类的 |
l****s
发帖数: 6 | 7 你这题不需要时间概念吗？
【在 b******6 的大作中提到】
: sorry, 这里有错别字“唯一的限制条件是不选已经有人坐下的相邻位置。”就是新来
: 的顾客选座位会和已经有人的地方相隔至少一个位置。等所有这样的位置没有了
: ，给出百分比的答案。比如25个座位，最多只可能坐13个人，也可能少于13, 但是不会
: 是只有一个， 最终两个顾客间最多可以相隔两个空座 相隔三个的话就能多坐一个人了
: ，求平均值
: 和平均方差？ 一个更简单的例子，N=3,最终的情况可能是*-*, -*-, *-*（*表示有人
: ， -表示没人）,这样平均值是1/3×(2/3+1/3+2/3)=5/9。
|
c***3
发帖数: 27 | 8 什么时间概念？
【在 l****s 的大作中提到】
: 你这题不需要时间概念吗？
|
n*******y
发帖数: 437 | 9 跟我前两天做的笔试题好像，
我用模拟做了，但是运行速度好慢，
而且我为了加快速度已经做了一些优化：
1) size大的variable用节省存储空间的data type，比如本来用0,1表示座位是不是
available，但是matlab默认0,1是double精度，我现在规定是binary datatype: True/
False
2) 本来是每轮在available的座位中随机产生的下一个要坐的座位，现在改为在一开始
产生全部的随机数(1-N的permutation)
code在这里(Matlab)，大家能不能帮我看看怎样提高速度，谢谢~
clear;
N = 25; %N = 50000; % how many seats in total
repeat = 1e6;
% count how many seats are taken
count = zeros(repeat, 1, 'uint16'); % uint16: 0-65535
for i = 1:repeat % repeat simulations
disp(i);
seq = uint16( randperm(N) );
seats = true(1,N); % seat(i)==true ~ available, ==false ~ unavailable
jj = 0;
while ( any(seats) ) % while any seat available
jj = jj + 1;
if seats( seq(jj) ) == false % if that seat unavailable, skip to
next loop
%disp('skip');
else % if that seat is available:
% sit, making that seat unavailable
seats( seq(jj) ) = false;
count(i) = count(i) + 1; % count how many seats are sit on
% neighboring seat(s) unavailable
if seq(jj) == 1
seats(2) = false;
elseif seq(jj) == N
seats(N-1) = false;
else
seats( seq(jj)+1 ) = false;
seats( seq(jj)-1 ) = false;
end
%disp(seats)
end
end
end
fraction_mean = mean(count1)/N;
fraction_std = std(double(count1))/N; |
n*******y
发帖数: 437 | 10 谢谢分享！ 能不能解释一下这个递推公式怎么推导的？谢谢！
【在 s****h 的大作中提到】
: 貌似比较难啊
: F(N) 是N个座位时顾客数的mean,
: F(neg) = F(0) = 0
: F(1) = F(2) = 1
: F(3) = 5/3
: 有递推公式：F(N) = 1 + 1/N * sum(i from －1 to N-2) ( F(i) + F(N-3-i)
: 写个程序可以算出来。
: 用笔算就不会了。
|
|
|
s****h
发帖数: 3979 | 11 这个很直观啊。
N个座位，1到N，1号被坐，剩下的和N-2个座位一样。
i号被坐，i+1, i-1就不能坐了。
1 ～ i-2 不就是F(i-2),
i+2～N不就是F(N-i-2+1)
【在 n*******y 的大作中提到】
: 谢谢分享！ 能不能解释一下这个递推公式怎么推导的？谢谢！
|
T*****u
发帖数: 7103 | |
b******6
发帖数: 38 | 13 递推的python code
import numpy as np
def deduction(N):
"""
For number of seats taken, deduction:
mean(s(0)) = 0;
mean(s(1)) = 1;
mean(s(N)) = sum{1/N*[mean(s(k-2))+mean(s(N-k-1))+1]} sum for k =
1, 2, ..., N;
mean(s(N)) = 1 + 2/N*[mean(s(-1)) + mean(s(0)) + ... + mean(s(N-2
))] for N > 1.
here s(-1) is added for convenience and s(-1)=0.
For variance:
var(s(0)) = 0;
var(s(1)) = 0;
var = mean(s(N)^2) - (mean(s(N)))^2 for N > 1;
(mean(s(N)))^2 is known;
let p(s(k)) be the corresponding probability
mean(s(N)^2) = 1/N*sum{[s(k-2)+s(n-k-1)+1]^2*p(s(k-2))*p(s(n-k-1)
)}
sum for all k and all possible values of s(k-2) and s(n-k-1).
Expand all the terms:
==> mean(s(N)^2) = 1/N*sum{mean(s(k-2)^2)+mean(s(n-k-1)^2)+2*mean(s(k
-2))+\
2*mean(s(n-k-1))+2*mean(s(k-2))*mean(s(n-k-1
))+1} ===>
==> mean(s(N)^2) = 1 + 2/N*{mean(s(-1)^2)+mean(s(0)^2)+...+mean(s(N-2
)^2)}+\
4/N*{mean(s(-1))+mean(s(0))+...+mean(s(N-2))}+\
2/N*{mean(s(-1)*mean(s(N-2))+mean(s(0))*mean(s
(N-3))+...+\
mean(s(k-2))*mean(s(N-k-1))+...+mean(s(N-
k-1))*mean(s(k-2))+\
mean(s(N-3))*mean(s(0))+mean(s(N-2))*mean
(s(-1))}
where k = 1, 2, ..., N
Return (fraction_mean, fraction_std) = (mean(s(N))/N, sqrt(var(s(N))/
N)
"""
if N == 0: return (0.0, 0.0)
if N == 1: return (1.0, 0.0)
# _sum = mean(s(-1)) + mean(s(0)) + mean(s(1)) + ... + mean(s(N-2))
# _prev = [mean(s(-1)), mean(s(0)), mean(s(1)), ..., mean(s(N-1))]
# _prev_sm = mean(s(N-1)^2)
# _sum_sm = mean(s(-1)^2) + mean(s(0)^2) + ... + mean(s(N-2)^2) #sum of
square mean
# using decimal type to avoid float point rounding error
_prev_m = [0.0, 0.0, 1.0]
_prev_sm = 1.0
_sum = 0.0
_sum_sm = 0.0
for i in xrange(2, N+1):
mean = 1.0 + 2.0 / i * _sum
prev = np.array(_prev_m[:-1])
square_mean = (1.0 +
2.0 / i * _sum_sm +
4.0 / i * _sum +
2.0 / i * np.dot(prev, prev[::-1]))
_sum += _prev_m[-1]
_sum_sm += _prev_sm
_prev_m.append(mean)
_prev_sm = square_mean
mean_square = mean*mean
var = square_mean - mean_square
return (float(mean/N), float(np.sqrt(var))/N)
N = 25: mean = 4.442122414e-01, std = 2.864508024e-02
N = 50000: mean = 4.323382983e-01, std = 6.052559416e-04 |
l********m
发帖数: 284 | 14 难道是data incubator？这个simulation呀，很简单呀。递推mean意义就变了吧？ |
l********m
发帖数: 284 | 15 楼上递推mean和variance的没上过统计课吧？ |
T*****u
发帖数: 7103 | 16 我开始也是这么想。不过现在出题的精了流行往多层次嘛。25个好模拟，给个
100000000出来就算死了，所以怎么模拟也东东脑筋。
【在 l********m 的大作中提到】
: 难道是data incubator？这个simulation呀，很简单呀。递推mean意义就变了吧？
|
l********m
发帖数: 284 | 17 50000 simulation确实要时间多些。楼主这是什么面试题呀？我做了一道一样的是data
incubator。 |
b******6
发帖数: 38 | 18 是data incubator的。确实没上过统计， 见笑了。可以解释下为什不不能推导吗？ 那
比如说最简单的coin toss也要模拟？ |
l********m
发帖数: 284 | 19 Simulation 的意义在于通过对实际情况的大尺度模拟（或者说Sampling）来估算true
mean. 我们不知道true mean。所以true mean. 简单的说不能推他的patern. 就算推
也是带erorr term 的。你那个算法是用 两个 sample mean 来推三个sample 的mean
，在推四个sample 的sample mean。推的都不是一个x 呀！
模拟是要考虑random ness的。不考虑randomness的叫数值计算。coin toss 每投一次
可能是正面可能是背面。
那个data incubator 我也做了。不知道啥前有消息呀？招多少个人呀？你知道吗？ |
b******6
发帖数: 38 | 20 我也不知道
true
mean
【在 l********m 的大作中提到】
: Simulation 的意义在于通过对实际情况的大尺度模拟（或者说Sampling）来估算true
: mean. 我们不知道true mean。所以true mean. 简单的说不能推他的patern. 就算推
: 也是带erorr term 的。你那个算法是用 两个 sample mean 来推三个sample 的mean
: ，在推四个sample 的sample mean。推的都不是一个x 呀！
: 模拟是要考虑random ness的。不考虑randomness的叫数值计算。coin toss 每投一次
: 可能是正面可能是背面。
: 那个data incubator 我也做了。不知道啥前有消息呀？招多少个人呀？你知道吗？
|
|
|
s****h
发帖数: 3979 | 21 肯定弄错了，mean怎么可能这么小？
mean > N / 3
=
-2
【在 b******6 的大作中提到】
: 递推的python code
: import numpy as np
: def deduction(N):
: """
: For number of seats taken, deduction:
: mean(s(0)) = 0;
: mean(s(1)) = 1;
: mean(s(N)) = sum{1/N*[mean(s(k-2))+mean(s(N-k-1))+1]} sum for k =
: 1, 2, ..., N;
: mean(s(N)) = 1 + 2/N*[mean(s(-1)) + mean(s(0)) + ... + mean(s(N-2
|
b******6
发帖数: 38 | 22 ratio
【在 s****h 的大作中提到】
: 肯定弄错了，mean怎么可能这么小？
: mean > N / 3
:
: =
: -2
|
d******e
发帖数: 7844 | 23 mean可以用Law of total expectation来递归。
variance可以用Law of total variance来递归，不过也忒麻烦点了。
【在 s****h 的大作中提到】
: std的公式就复杂了。
: 需要sum(i from -1 to N-2, j from -1 to N-2) F(i) * F(j) 之类的
|
l********m
发帖数: 284 | |
l********m
发帖数: 284 | 25 你用law of total expectation, conditional probability 怎么算呢？这个题 每个
座位两边是一个位子还是两个位子不确定呀，分三种情况，一边一个（1/4），一边一
个另一边两个（1/2），两边两个（1/4）？还有两个把头的座位也不一样。
【在 d******e 的大作中提到】
: mean可以用Law of total expectation来递归。
: variance可以用Law of total variance来递归，不过也忒麻烦点了。
|
n*******y
发帖数: 437 | 26 哦！这就是recursive方法是吧~ 谢谢分享！
请问一下，是不是recursive比起重复模拟（就是随机的一个一个位子坐）快？
【在 s****h 的大作中提到】
: 这个很直观啊。
: N个座位，1到N，1号被坐，剩下的和N-2个座位一样。
: i号被坐，i+1, i-1就不能坐了。
: 1 ～ i-2 不就是F(i-2),
: i+2～N不就是F(N-i-2+1)
|
n*******y
发帖数: 437 | 27 我也做了 对 是the data incubator的
你第三题做什么了？
我想不出什么特有商业价值的
只要做了chicago crime data的分析，说商业上也会关心local安全
data
【在 l********m 的大作中提到】
: 50000 simulation确实要时间多些。楼主这是什么面试题呀？我做了一道一样的是data
: incubator。
|
d******e
发帖数: 7844 | 28 X_N,N个椅子上的人数。
Y第一个人做在J把椅子上。
P(Y=1) = ... = P(Y=N) = 1/N
E(X_N) = \sum_{J=1}^N P(Y=J)*[E(X_{J-2}) + 1 + E(X_{N-J-1})]
第1把到第J-2把 第J+2把到底N把。
【在 l********m 的大作中提到】
: 你用law of total expectation, conditional probability 怎么算呢？这个题 每个
: 座位两边是一个位子还是两个位子不确定呀，分三种情况，一边一个（1/4），一边一
: 个另一边两个（1/2），两边两个（1/4）？还有两个把头的座位也不一样。
|
d******e
发帖数: 7844 | 29 我觉得对于面试来说递归就已经到头了。
但话说回来，递归并不算是数值解法。Simulation的话又闲得太无聊了。
问的挺奇怪。
【在 n*******y 的大作中提到】
: 哦！这就是recursive方法是吧~ 谢谢分享！
: 请问一下，是不是recursive比起重复模拟（就是随机的一个一个位子坐）快？
|
g******2
发帖数: 234 | 30 for n = 50000 case,
x <- rbinom(1000, 16666, 0.5)
y <- (50000 - x*3)/2
mean((x+y)/50000)
sd((x+y)/50000)
this should be a good enough approximation |
|
|
d******c
发帖数: 2407 | 31 我是直接求distribution然后再递推，N数字大了以后太慢，python程序优化之后到N＝
500都是立刻
出来，但是N到800以后就越来越慢，到50000不知道要算多久，拟合一下可能能估计出
来，没再试了。因为中间那些情形的计算是组合爆炸的，没什么办法能绕开，上map
reduce用并行倒是可以。
上面直接对sd递推可能比我这个要少计算很多。 |
b********x
发帖数: 2 | 32 搭车同问有关这个data incubator的项目，有人收到回复了吗，它家会默拒申请人吗？ |
m****9
发帖数: 492 | 33 还没有收到回复，估计3月1号左右能知道结果。
【在 b********x 的大作中提到】
: 搭车同问有关这个data incubator的项目，有人收到回复了吗，它家会默拒申请人吗？
|
