c***z
发帖数: 6348 | 1 I am not sure if this is round 2 or what, since I was transferred to anther
team...
Interviewer was PhD in physics, just graduated this Feb. (yeah, Blook will be much happier if
interviewed by him...)
Questions:
1. Tell me about your research and your contribution.
2. Given a linked list of unknown length. Make a sublist of length m, which contains elements from the mother list, with equal prob for each element. You are allowed only one pass.
This is easy. And he said perfect.
3. Given 5 coins, | a****o
发帖数: 686 | | d*j
发帖数: 13780 | 3 orz, a CHinese?
maybe someone from this borad
hehe | s****n
发帖数: 1237 | 4 发包子了，bless。
另外说说你2,3,4的答案吧。
2.是不是先pick m个填满，后面的p=1/n use the new pick replace old pick，然后
对已经存在的m个都比较一次，所以是p=m/n？
3.conditional prob,最后是不是3/4
4.什么是unit disc，不懂：（。如果是单位圆的话是不是draw x,y iid u[0,1]，然后
x^2+y^2<=1就keep。
anther
be much happier if
which contains elements from the mother list, with equal prob for each
element. You are allowed only one pass.
flip twice, the result is HH. What is the chance to get an H for the third
flip?
on the unit disc.
move.
give baozi out.
【在 c***z 的大作中提到】
: I am not sure if this is round 2 or what, since I was transferred to anther
: team...
: Interviewer was PhD in physics, just graduated this Feb. (yeah, Blook will be much happier if
: interviewed by him...)
: Questions:
: 1. Tell me about your research and your contribution.
: 2. Given a linked list of unknown length. Make a sublist of length m, which contains elements from the mother list, with equal prob for each element. You are allowed only one pass.
: This is easy. And he said perfect.
: 3. Given 5 coins,
| p*****k
发帖数: 318 | | s****n
发帖数: 1237 | 6 thx, that's what I mean, the n is not fixed but nth pick.
【在 p*****k 的大作中提到】
: sunson, for 2 size of the list is unknown, see
: http://www.wilmott.com/messageview.cfm?catid=26&threadid=74084
| k*******d
发帖数: 1340 | 7 2.我不会，楼主好强
3.我算的也是3/4
4.在unit disk上要什么distribution?还是uniform？
感谢楼主提供面试经验，马上送你包子 | z****i
发帖数: 406 | 8 4
if you mean uniform on unit disc, can I use polar coordinates, generate x
and y both U(0,1), then let r =sqrt(x), theta =2•pi•y | c*********g
发帖数: 154 | | t********s
发帖数: 54 | 10 Well, that's uniform in the polar coordinate sense, not in cartesian
coordinate sense.
【在 z****i 的大作中提到】
: 4
: if you mean uniform on unit disc, can I use polar coordinates, generate x
: and y both U(0,1), then let r =sqrt(x), theta =2•pi•y
| | | B******i
发帖数: 213 | 11 thanks for sharing
could you also share GS interview round 1 questions? Thanks
anther
be much happier if
which contains elements from the mother list, with equal prob for each
element. You are allowed only one pass.
flip twice, the result is HH. What is the chance to get an H for the third
flip?
【在 c***z 的大作中提到】
: I am not sure if this is round 2 or what, since I was transferred to anther
: team...
: Interviewer was PhD in physics, just graduated this Feb. (yeah, Blook will be much happier if
: interviewed by him...)
: Questions:
: 1. Tell me about your research and your contribution.
: 2. Given a linked list of unknown length. Make a sublist of length m, which contains elements from the mother list, with equal prob for each element. You are allowed only one pass.
: This is easy. And he said perfect.
: 3. Given 5 coins,
| j*****4
发帖数: 292 | 12 that's right. the key of this problem is how to get the distribution of
function of r.v.s. R=sqrt(X^2+X^2) R<=1 and X,Y iid U[0,1]
【在 z****i 的大作中提到】
: 4
: if you mean uniform on unit disc, can I use polar coordinates, generate x
: and y both U(0,1), then let r =sqrt(x), theta =2•pi•y
| l**n
发帖数: 264 | 13 3.为什么不是3/10？
【在 c*********g 的大作中提到】
: 3.是3/4没错了。
: 4.要做单位圆上的均匀分布，应该取两个不相关的随机变量。极坐标系就是很好的选择
: 。有兴趣的童鞋可以看看球面分布：http://en.wikibooks.org/wiki/Mathematica/Uniform_Spherical_Distribution
| f***a
发帖数: 329 | 14 完整点解答：
P(H|HH)=P(HHH)/P(HH)
since P(HH)=P(HH|F)P(F)+P(HH|U)P(U)=(1/2)^2*(4/5)+1^2*(1/5)
and P(HHH)=P(HHH|F)P(F)+P(HHH|U)P(U)=(1/2)^3*(4/5)+1^3*(1/5)
thus P(H|HH)=3/4
（notation: H=head, F=fair coin, U=unfair coin）
【在 l**n 的大作中提到】
: 3.为什么不是3/10？
| f***a
发帖数: 329 | 15 For problem 2, 把mother list的index randomly order一下，然后把前m个pass到
sublist就行了？
可能我理解题目错了，呵呵 | f***a
发帖数: 329 | 16 For problem 4,
1st method:
generate iid U1, U2~ unif(0,1);
let theta=2pi*U1, r=U2;
then (x,y)=(r*cos(theta),r*sin(theta))
2nd method:
generate iid U1, U2~ unif(0,1);
let (x,y)=(U1,U2) if U1^2+U2^2<=1; | p*****k
发帖数: 318 | 17
fanta, as zhucai showed, you need to set r=sqrt(U2),
as the p.d.f. of the radius is linear.
problem 2, note the size of the linked list is unknown
【在 f***a 的大作中提到】
: For problem 4,
: 1st method:
: generate iid U1, U2~ unif(0,1);
: let theta=2pi*U1, r=U2;
: then (x,y)=(r*cos(theta),r*sin(theta))
: 2nd method:
: generate iid U1, U2~ unif(0,1);
: let (x,y)=(U1,U2) if U1^2+U2^2<=1;
| f***a
发帖数: 329 | 18 哦 我有点想当然了 T_T
确实是要考虑不同r时圆周不同
r=sqrt(U), U~unif(0,1) => f(r)=2r 0
多谢指教~
【在 p*****k 的大作中提到】
:
: fanta, as zhucai showed, you need to set r=sqrt(U2),
: as the p.d.f. of the radius is linear.
: problem 2, note the size of the linked list is unknown
| m*****n
发帖数: 2152 | 19 可以把polar转成cartesian啊，我也认为用polar更容易，更清晰。
【在 t********s 的大作中提到】
: Well, that's uniform in the polar coordinate sense, not in cartesian
: coordinate sense.
| m*****n
发帖数: 2152 | 20 关于4，为什么不能做一个unit square的均匀分布，然后把不在单位圆内的都扔掉呢？
我觉得园内
剩下的应该也是均匀分布啊？
anther
will be much happier if
which contains elements from the mother list, with equal prob for each
element. You are allowed only one pass.
and flip twice, the result is HH. What is the chance to get an H for the
third flip?
【在 c***z 的大作中提到】
: I am not sure if this is round 2 or what, since I was transferred to anther
: team...
: Interviewer was PhD in physics, just graduated this Feb. (yeah, Blook will be much happier if
: interviewed by him...)
: Questions:
: 1. Tell me about your research and your contribution.
: 2. Given a linked list of unknown length. Make a sublist of length m, which contains elements from the mother list, with equal prob for each element. You are allowed only one pass.
: This is easy. And he said perfect.
: 3. Given 5 coins,
| | | f***a
发帖数: 329 | 21 窃以为您说的没错 ：D
【在 m*****n 的大作中提到】
: 关于4，为什么不能做一个unit square的均匀分布，然后把不在单位圆内的都扔掉呢？
: 我觉得园内
: 剩下的应该也是均匀分布啊？
:
: anther
: will be much happier if
: which contains elements from the mother list, with equal prob for each
: element. You are allowed only one pass.
: and flip twice, the result is HH. What is the chance to get an H for the
: third flip?
| l**n
发帖数: 264 | 22 可以是可以，但是这个效率是PI/4. 直接转成
[r,theta]=[[J]]*[x,y]抽样，利用率是100%
【在 m*****n 的大作中提到】
: 关于4，为什么不能做一个unit square的均匀分布，然后把不在单位圆内的都扔掉呢？
: 我觉得园内
: 剩下的应该也是均匀分布啊？
:
: anther
: will be much happier if
: which contains elements from the mother list, with equal prob for each
: element. You are allowed only one pass.
: and flip twice, the result is HH. What is the chance to get an H for the
: third flip?
| l**n
发帖数: 264 | 23 哦，是，忘记前面已经的条件了，多谢
【在 f***a 的大作中提到】
: 完整点解答：
: P(H|HH)=P(HHH)/P(HH)
: since P(HH)=P(HH|F)P(F)+P(HH|U)P(U)=(1/2)^2*(4/5)+1^2*(1/5)
: and P(HHH)=P(HHH|F)P(F)+P(HHH|U)P(U)=(1/2)^3*(4/5)+1^3*(1/5)
: thus P(H|HH)=3/4
: （notation: H=head, F=fair coin, U=unfair coin）
| b*****e
发帖数: 474 | 24 那个解答有问题的。在 N 不预知的情况下，那样做可以使最后留下
的 m 个数都是有 m/N 的概率，但是每个数被扔掉的概率不一样?
【在 s****n 的大作中提到】
: thx, that's what I mean, the n is not fixed but nth pick.
| p*****k
发帖数: 318 | 25
babbage, this sounds surprising. if the prob of each # being
kept is same, how could the prob of them being discarded, which
is 1-Pr[being kept], different?
【在 b*****e 的大作中提到】
: 那个解答有问题的。在 N 不预知的情况下，那样做可以使最后留下
: 的 m 个数都是有 m/N 的概率，但是每个数被扔掉的概率不一样?
| m****r
发帖数: 141 | 26 请问
看什么书才能回答 这种 quant 面试中的 有关概率问题
谢谢
which contains elements from the mother list, with equal prob for each
element. You are allowed only one pass.
and flip twice, the result is HH. What is the chance to get an H for the
third flip?
numbers on the unit disc.
stupid move.
【在 c***z 的大作中提到】
: I am not sure if this is round 2 or what, since I was transferred to anther
: team...
: Interviewer was PhD in physics, just graduated this Feb. (yeah, Blook will be much happier if
: interviewed by him...)
: Questions:
: 1. Tell me about your research and your contribution.
: 2. Given a linked list of unknown length. Make a sublist of length m, which contains elements from the mother list, with equal prob for each element. You are allowed only one pass.
: This is easy. And he said perfect.
: 3. Given 5 coins,
| b*****e
发帖数: 474 | 27 I am talking about different types of prob. What I meant is, in the solution
, P(getting kept | already in the selection list) are clearly equal, and
thus P(getting kept eventually | initially selected)= m/N.
But does this automatically translate to P(getting discarded at some point)
being equal for all elements?
【在 p*****k 的大作中提到】
:
: babbage, this sounds surprising. if the prob of each # being
: kept is same, how could the prob of them being discarded, which
: is 1-Pr[being kept], different?
| p*****k
发帖数: 318 | 28 babbage, lets see a particular case with the (N-2)-th element:
P(made to the final list) = M/(N-2) * [1-M/(N-1)*1/M] * [1-M/N*1/M]
= M/N
(i.e., Pr[selected]*Pr[not replaced by (N-1)-th]*Pr[not by N-th])
P(being discarded) = [1-M/(N-2)] + M/(N-2) * [M/(N-1)*1/M]
+ M/(N-2) * [1-M/(N-1)*1/M] * [M/N*1/M]
=1-M/N
(Pr[not selected] + Pr[selected]*Pr[replaced by (N-1)-th]
+Pr[selected]*Pr[not replaced by (N-1)-th]*Pr[replaced by N-th])
it's st8forward to replace N-2 with the general index and one
ends u | b*****e
发帖数: 474 | 29 Ah, you're absolutely right. Thanks!
【在 p*****k 的大作中提到】
: babbage, lets see a particular case with the (N-2)-th element:
: P(made to the final list) = M/(N-2) * [1-M/(N-1)*1/M] * [1-M/N*1/M]
: = M/N
: (i.e., Pr[selected]*Pr[not replaced by (N-1)-th]*Pr[not by N-th])
: P(being discarded) = [1-M/(N-2)] + M/(N-2) * [M/(N-1)*1/M]
: + M/(N-2) * [1-M/(N-1)*1/M] * [M/N*1/M]
: =1-M/N
: (Pr[not selected] + Pr[selected]*Pr[replaced by (N-1)-th]
: +Pr[selected]*Pr[not replaced by (N-1)-th]*Pr[replaced by N-th])
: it's st8forward to replace N-2 with the general index and one
|
|
