h**********y
发帖数: 1293 | 1 上周五面的，两轮45分钟，今早上催了一下，下午来了据信。。
题目都很简单。。
1. find and store connected component in 0/1 matrix。
我用了 color fill algorithm, hash table store every pixel with 1
很快写好，面试官表示满意。
2. even sampling in a sphere, even sampling on sphere surface
简单。
3. 2D point cloud, find a line that has most points on it.
老印，英语口音不大。面完表示很满意。you did well。。
第二个面试官口齿不清。。可能是欧洲人，急急忙忙不耐烦的样子。
我打开的是正确的google doc，他打开的是第一个面试官的doc。。。
写完第二题他才说看不到。折腾半天才搞明白。。
然后doc里的copy不知道为啥不work，写完第二题还得把code抄到他打开的doc里。。。
1. public, private, friend
2. depth of binary tree
3. merge interval span
我用了stack，不过面试官似乎偏好更简单得。
其实我也知道别的做法，当时觉得stack好写就直接写了
除了最后一题不是面试官最想要的。都写出来了。。
诶。郁闷。到底要怎样。要是不会做我也认了。。 |
s******n
发帖数: 3946 | |
g*********e
发帖数: 14401 | |
g*********e
发帖数: 14401 | 4 2D point cloud, find a line that has most points on it.
这个是不是 对每一对pair 数总点数？O(n^2) |
h**********l
发帖数: 6342 | 5 pat
那个even sampling in a sphere是什么意思阿？
【在 h**********y 的大作中提到】
: 上周五面的，两轮45分钟，今早上催了一下，下午来了据信。。
: 题目都很简单。。
: 1. find and store connected component in 0/1 matrix。
: 我用了 color fill algorithm, hash table store every pixel with 1
: 很快写好，面试官表示满意。
: 2. even sampling in a sphere, even sampling on sphere surface
: 简单。
: 3. 2D point cloud, find a line that has most points on it.
: 老印，英语口音不大。面完表示很满意。you did well。。
: 第二个面试官口齿不清。。可能是欧洲人，急急忙忙不耐烦的样子。
|
h**********l
发帖数: 6342 | 6 好像是150上的题
【在 g*********e 的大作中提到】
: 2D point cloud, find a line that has most points on it.
: 这个是不是 对每一对pair 数总点数？O(n^2)
|
g*********e
发帖数: 14401 | 7
就是在一个 球体里面/球面 每个地方取到的概率都一样吧
【在 h**********l 的大作中提到】
: pat
: 那个even sampling in a sphere是什么意思阿？
|
q***y
发帖数: 236 | |
h**********l
发帖数: 6342 | 9 不好意思，还是不明白
这是问个什么？写个什么code？
【在 g*********e 的大作中提到】
:
: 就是在一个 球体里面/球面 每个地方取到的概率都一样吧
|
g*********e
发帖数: 14401 | 10
返回一个三维坐标吧
【在 h**********l 的大作中提到】
: 不好意思，还是不明白
: 这是问个什么？写个什么code？
|
|
|
m***n
发帖数: 2154 | 11 到中心距离相等，x,y,z ，三个随机变量。
【在 g*********e 的大作中提到】
:
: 返回一个三维坐标吧
|
h**********l
发帖数: 6342 | 12 so if center is (0,0,0), x==y==z?
【在 m***n 的大作中提到】
: 到中心距离相等，x,y,z ，三个随机变量。
|
w****x
发帖数: 2483 | 13
第一题递归, 然后每个相邻的block编号??
第二题是不是选一个垂直角度和一个水平角度就可以取得球面上的点? 球内的就在当前
的基础上求半径上的一个点? 不用编程吧.
第三题就是在遍历每个点, 然后计算和其他点的斜率, 经过同一个点的斜率相同的直线
一定是在同一直线上.
merge interval span??
具体怎么样的?? 是不是想考merge sort?? max(a.beg, b.beg) <= min(a.end, b.end)
就merge 成 min(a.beg, b.beg), max(a.end, b.end)
【在 h**********y 的大作中提到】
: 上周五面的，两轮45分钟，今早上催了一下，下午来了据信。。
: 题目都很简单。。
: 1. find and store connected component in 0/1 matrix。
: 我用了 color fill algorithm, hash table store every pixel with 1
: 很快写好，面试官表示满意。
: 2. even sampling in a sphere, even sampling on sphere surface
: 简单。
: 3. 2D point cloud, find a line that has most points on it.
: 老印，英语口音不大。面完表示很满意。you did well。。
: 第二个面试官口齿不清。。可能是欧洲人，急急忙忙不耐烦的样子。
|
a******9
发帖数: 12 | |
p*****2
发帖数: 21240 | |
s******n
发帖数: 3946 | 16 大概意思是random()两个角度，再random一个半径，那个半径要开3次方根。
这样生成的随机点可以均匀的分布在球体里
【在 h**********l 的大作中提到】
: so if center is (0,0,0), x==y==z?
|
z****4
发帖数: 194 | 17 这样的显然不是均匀分布
【在 s******n 的大作中提到】
: 大概意思是random()两个角度，再random一个半径，那个半径要开3次方根。
: 这样生成的随机点可以均匀的分布在球体里
|
g*********e
发帖数: 14401 | |
y***g
发帖数: 1492 | 19 考古挖个坟。。
请问这个uniformly distributed sampling是要看Jacobian?
for on unit sphere:
J=sin(b)d(a)d(b)=d(a)d(-cos(b))
所以只要生成a和z=cos(b)分别在（0，2pi）和（-1，1）中uniformly distribute?
for in unit ball:
since J=r^2 sin(b)d(a)d(b)d(r)=1/3 d(r^3)d(a)d(-cos(b))
所以要多一个开3次根的uniformly distributed variable in (0,1)? |
c****m
发帖数: 179 | 20 原来楼主是二进宫了。
感觉这些题用来电面都好难。。。球上sample之前没见过，估计就挂了。。。 |
|
|
s**********r
发帖数: 8153 | 21 怎么考语法阿？？
public, private, friend？？ |
o****d
发帖数: 2835 | 22 把球体用极坐标表示
http://en.wikipedia.org/wiki/Polar_coordinate_system
有三个变量
对那三个变量随机取
【在 s******n 的大作中提到】
: 大概意思是random()两个角度，再random一个半径，那个半径要开3次方根。
: 这样生成的随机点可以均匀的分布在球体里
|
b*******l
发帖数: 590 | 23 妈呀，现在狗狗怎么这么变态。我09年的时候电面只问了一个很简单的问题就让我去
onsite了，也许是因为我就在本地？ |
m****i
发帖数: 650 | 24 google题目真的是难好多，这个都是phone screening,只能说现在google股票疯长，申
请人太多了 |
y***g
发帖数: 1492 | 25 这么取出来的点不是evenly distributed
把球体用极坐标表示http://en.wikipedia.org/wiki/Polar_coordinate_system" x-apple-data-det........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 o****d 的大作中提到】
: 把球体用极坐标表示
: http://en.wikipedia.org/wiki/Polar_coordinate_system
: 有三个变量
: 对那三个变量随机取
|
h********3
发帖数: 2075 | 26 当然是。只要random产生数是独立且不相关的就行了。概率上也可以证明。
【在 z****4 的大作中提到】
: 这样的显然不是均匀分布
|
a********m
发帖数: 15480 | 27 近处的密度大呀。
【在 h********3 的大作中提到】
: 当然是。只要random产生数是独立且不相关的就行了。概率上也可以证明。
|
h********3
发帖数: 2075 | 28 为啥近处密度大？
科学松鼠会上以前有篇文章专门讨论过这个问题。这个是一个有趣的悖论问题。其实按
极坐标来产生和按照面积体积之比来产生，都是正确答案。关键取决于你对随机变量的
定义。
如果你在X,Y，Z空间看的觉得分布的密度是均匀的，那么在极坐标(r,\theta,\phi)空
间上看会觉得你的点趋向于产生r坐标较大的，那么也有人跳出来说你不是真正均
匀分布的。同理，你在任何一个空间看是均匀密度的点集。那么我都可以找到一种仿射
变换，我都可以让你的分布在那个空间上不是均匀的。
到底谁是正确的？
实际上，任何一块连续的空间，点的集合都是无穷大的。根本就没有点的密度可言或者
点的密度都是无穷大。
【在 a********m 的大作中提到】
: 近处的密度大呀。
|
h**********y
发帖数: 1293 | 29 挖坟好过分的。。掩面奔走～
【在 c****m 的大作中提到】
: 原来楼主是二进宫了。
: 感觉这些题用来电面都好难。。。球上sample之前没见过，估计就挂了。。。
|
a********m
发帖数: 15480 | 30 密度＝个数／体积，这个对不？
半径0-0.5和0.5-1.0两块分布的个数趋近相同么？体积一样么？
【在 h********3 的大作中提到】
: 为啥近处密度大？
: 科学松鼠会上以前有篇文章专门讨论过这个问题。这个是一个有趣的悖论问题。其实按
: 极坐标来产生和按照面积体积之比来产生，都是正确答案。关键取决于你对随机变量的
: 定义。
: 如果你在X,Y，Z空间看的觉得分布的密度是均匀的，那么在极坐标(r,\theta,\phi)空
: 间上看会觉得你的点趋向于产生r坐标较大的，那么也有人跳出来说你不是真正均
: 匀分布的。同理，你在任何一个空间看是均匀密度的点集。那么我都可以找到一种仿射
: 变换，我都可以让你的分布在那个空间上不是均匀的。
: 到底谁是正确的？
: 实际上，任何一块连续的空间，点的集合都是无穷大的。根本就没有点的密度可言或者
|
|
|
a********m
发帖数: 15480 | 31 没注意三次方根。那样的话感觉是对的。
【在 a********m 的大作中提到】
: 密度＝个数／体积，这个对不？
: 半径0-0.5和0.5-1.0两块分布的个数趋近相同么？体积一样么？
|
j********x
发帖数: 2330 | 32 显然暴露了你和松鼠会对概率缺乏精确的理解
这里even当然指的是概率密度。。。
【在 h********3 的大作中提到】
: 为啥近处密度大？
: 科学松鼠会上以前有篇文章专门讨论过这个问题。这个是一个有趣的悖论问题。其实按
: 极坐标来产生和按照面积体积之比来产生，都是正确答案。关键取决于你对随机变量的
: 定义。
: 如果你在X,Y，Z空间看的觉得分布的密度是均匀的，那么在极坐标(r,\theta,\phi)空
: 间上看会觉得你的点趋向于产生r坐标较大的，那么也有人跳出来说你不是真正均
: 匀分布的。同理，你在任何一个空间看是均匀密度的点集。那么我都可以找到一种仿射
: 变换，我都可以让你的分布在那个空间上不是均匀的。
: 到底谁是正确的？
: 实际上，任何一块连续的空间，点的集合都是无穷大的。根本就没有点的密度可言或者
|
j********x
发帖数: 2330 | 33 显然暴露了你和松鼠会对概率缺乏精确的理解
这里even当然指的是概率密度。。。
【在 h********3 的大作中提到】
: 为啥近处密度大？
: 科学松鼠会上以前有篇文章专门讨论过这个问题。这个是一个有趣的悖论问题。其实按
: 极坐标来产生和按照面积体积之比来产生，都是正确答案。关键取决于你对随机变量的
: 定义。
: 如果你在X,Y，Z空间看的觉得分布的密度是均匀的，那么在极坐标(r,\theta,\phi)空
: 间上看会觉得你的点趋向于产生r坐标较大的，那么也有人跳出来说你不是真正均
: 匀分布的。同理，你在任何一个空间看是均匀密度的点集。那么我都可以找到一种仿射
: 变换，我都可以让你的分布在那个空间上不是均匀的。
: 到底谁是正确的？
: 实际上，任何一块连续的空间，点的集合都是无穷大的。根本就没有点的密度可言或者
|
h********3
发帖数: 2075 | 34 你按照你的均匀密度产生的点集。在极坐标空间内不是均匀的。
在极坐标空间了，球体被转换成了一个3维的立方体。r从0到半径, theta从0到PI, phi
从0到PI。这个立方体的体积是多少？
X,Y,Z任意一个点有且仅有一个点跟极坐标空间内的一个点对应。既然我在极坐标内
uniform产生的点，为什么在X,Y,Z内就不是uniform产生的？
【在 a********m 的大作中提到】
: 密度＝个数／体积，这个对不？
: 半径0-0.5和0.5-1.0两块分布的个数趋近相同么？体积一样么？
|
y***g
发帖数: 1492 | 35 你看看极坐标的Jacobian就知道了
dV=\rho^2 sin(\phi) d(\rho)d(\theta)d(\phi)
即使\rho \theta \phi 都是uniformly distributed
但是单位球体内的点的数量 明显是\rho 和\phi的函数（而不是常数）
换个元就行了
【在 h********3 的大作中提到】
: 当然是。只要random产生数是独立且不相关的就行了。概率上也可以证明。
|
y***g
发帖数: 1492 | 36 是 但是这样积分空间和原空间的单位体积之间是有一个factor（坐标变换的Jacobian)
这个factor是随位置变化的
你仔细想想再球体里面是怎么积分的
phi
【在 h********3 的大作中提到】
: 你按照你的均匀密度产生的点集。在极坐标空间内不是均匀的。
: 在极坐标空间了，球体被转换成了一个3维的立方体。r从0到半径, theta从0到PI, phi
: 从0到PI。这个立方体的体积是多少？
: X,Y,Z任意一个点有且仅有一个点跟极坐标空间内的一个点对应。既然我在极坐标内
: uniform产生的点，为什么在X,Y,Z内就不是uniform产生的？
|
h********3
发帖数: 2075 | 37 并不是科学松鼠发表了那篇文章。别人不过是科普性质的引用，这个问题早100多年前
的数学界都讨论很久了。别人只是转述。极坐标产生的随机点集的概率密度在极坐标空
间内也是even的。
【在 j********x 的大作中提到】
: 显然暴露了你和松鼠会对概率缺乏精确的理解
: 这里even当然指的是概率密度。。。
|
h********3
发帖数: 2075 | 38 我知道你的意思。问题在于，为什么非要按照原空间的体积来计算的概率密度才是even
的？
Jacobian)
【在 y***g 的大作中提到】
: 是 但是这样积分空间和原空间的单位体积之间是有一个factor（坐标变换的Jacobian)
: 这个factor是随位置变化的
: 你仔细想想再球体里面是怎么积分的
:
: phi
|
y***g
发帖数: 1492 | 39 要求是要在原球体x,y,z坐标里面概率密度是常数
而不是在极坐标空间(\rho,\theta,\phi)里是常数 |
y***g
发帖数: 1492 | 40 你能找到松鼠会的原文给我看看么 我觉得你说跟我们说的不是一个东西
你可以看看这个：
http://mathworld.wolfram.com/SpherePointPicking.html
【在 h********3 的大作中提到】
: 并不是科学松鼠发表了那篇文章。别人不过是科普性质的引用，这个问题早100多年前
: 的数学界都讨论很久了。别人只是转述。极坐标产生的随机点集的概率密度在极坐标空
: 间内也是even的。
|
|
|
a********m
发帖数: 15480 | 41 密度概念本身就是基于普通三位空间。如果允许变化的话，任何分布总有变换能让它是
均匀的。
even
【在 h********3 的大作中提到】
: 我知道你的意思。问题在于，为什么非要按照原空间的体积来计算的概率密度才是even
: 的？
:
: Jacobian)
|
w********p
发帖数: 948 | 42 真心难啊。咋都这么难的题啊。还都是45分钟3题。
都快没信心做题了。
【在 c****m 的大作中提到】
: 原来楼主是二进宫了。
: 感觉这些题用来电面都好难。。。球上sample之前没见过，估计就挂了。。。
|
j********x
发帖数: 2330 | 43 极坐标空间是啥？
【在 h********3 的大作中提到】
: 并不是科学松鼠发表了那篇文章。别人不过是科普性质的引用，这个问题早100多年前
: 的数学界都讨论很久了。别人只是转述。极坐标产生的随机点集的概率密度在极坐标空
: 间内也是even的。
|
