一道面试题， 挺难的， 求助# JobHunting - 待字闺中
m*r
1 楼
把一副扑克牌， 一张一张地随机放到一张大桌子上，
假设， 桌子的面积远远大于扑克牌的面积，
假设， 所有扑克牌都平落在桌子上，
如何计算扑克牌所覆盖的桌子的面积，
注意， 扑克牌可能会重叠， 可能会分散 不连续
请分析算法的复杂度
假设， 桌子的面积远远大于扑克牌的面积，
假设， 所有扑克牌都平落在桌子上，
如何计算扑克牌所覆盖的桌子的面积，
注意， 扑克牌可能会重叠， 可能会分散 不连续
请分析算法的复杂度
g*s
2 楼
没别的条件么？ 按你的说法从一张扑克的面积（全部完美重叠）到52×一张扑克的面
积 （全部分散）都有可能啊
积 （全部分散）都有可能啊
m*r
3 楼
是的， 都有可能， 这就是难点 !
【在 g*******s 的大作中提到】
: 没别的条件么？ 按你的说法从一张扑克的面积（全部完美重叠）到52×一张扑克的面
: 积 （全部分散）都有可能啊
【在 g*******s 的大作中提到】
: 没别的条件么？ 按你的说法从一张扑克的面积（全部完美重叠）到52×一张扑克的面
: 积 （全部分散）都有可能啊
z*3
4 楼
要计算每一张扑克覆盖以前每一张扑克所覆盖的面积
复杂度会升到n^2
复杂度会升到n^2
g*s
5 楼
你这个只能pseudo code吧，不然细节太多就变成图形学问题了。光是求两张任意角度
的牌并集面积就有的写了。
总体两种思路，都是对每一张新牌，求他和之前所有牌的并集面积。主要区别在于如何
找nearest neighbours
一种是每次遍历之前所有的牌，看和哪些重叠。总时间n^2, 用tree可以优化趋近于
nlogn, 空间1。
一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
根据新牌的落点可以直接找出之前落在这个grid的所有牌。总时间n， 空间m，m是桌面
的大小。
【在 m****r 的大作中提到】
: 是的， 都有可能， 这就是难点 !
的牌并集面积就有的写了。
总体两种思路，都是对每一张新牌，求他和之前所有牌的并集面积。主要区别在于如何
找nearest neighbours
一种是每次遍历之前所有的牌，看和哪些重叠。总时间n^2, 用tree可以优化趋近于
nlogn, 空间1。
一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
根据新牌的落点可以直接找出之前落在这个grid的所有牌。总时间n， 空间m，m是桌面
的大小。
【在 m****r 的大作中提到】
: 是的， 都有可能， 这就是难点 !
p*2
6 楼
什么公司的？
r*n
7 楼
关键字：随机
用Monte Carlo simulation，算法复杂都和你要求的精度有关系
比如精度要提高一位(0.1)，sampling number就要是原来的100倍，所以大致是O(n^2)
这个和算法没有什么关系，其实是numerical method，wikipedia上面有解释。
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
用Monte Carlo simulation，算法复杂都和你要求的精度有关系
比如精度要提高一位(0.1)，sampling number就要是原来的100倍，所以大致是O(n^2)
这个和算法没有什么关系，其实是numerical method，wikipedia上面有解释。
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
k*a
8 楼
算expectation的话很简单, 假设牌面积a， 桌子面积b
对于桌子的每一个点， 被一张扑克牌覆盖的概率是 a/b, 这样被52张牌至少一张覆盖
的概率是：
1 - (1 - a/b)^52
这样，expected覆盖面积是 b*[1 - (1 - a/b)^52]
对于桌子的每一个点， 被一张扑克牌覆盖的概率是 a/b, 这样被52张牌至少一张覆盖
的概率是：
1 - (1 - a/b)^52
这样，expected覆盖面积是 b*[1 - (1 - a/b)^52]
m*r
9 楼
请问， 第一种 ：一种是每次遍历之前所有的牌，看和哪些重叠。总时间n^2, 用tree
可以优化趋近于
如何 “看和哪些重叠” ？ 比较每张牌的坐标吗 ？
如何用 树 优化 能达到 n lg n , 而且 空间为1 ？
第二种：
一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
这个也要 记录下所有 牌的坐标吧 ？ 要不， 如何 知道是否在 ｇｒｉｄ 里面 ？
谢谢
可以优化趋近于
如何 “看和哪些重叠” ？ 比较每张牌的坐标吗 ？
如何用 树 优化 能达到 n lg n , 而且 空间为1 ？
第二种：
一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
这个也要 记录下所有 牌的坐标吧 ？ 要不， 如何 知道是否在 ｇｒｉｄ 里面 ？
谢谢
m*r
10 楼
如何 用 Monte Carlo simulation 来做呢 ？
能具体说说吗 ？
谢谢
【在 r*********n 的大作中提到】
: 关键字：随机
: 用Monte Carlo simulation，算法复杂都和你要求的精度有关系
: 比如精度要提高一位(0.1)，sampling number就要是原来的100倍，所以大致是O(n^2)
: 这个和算法没有什么关系，其实是numerical method，wikipedia上面有解释。
能具体说说吗 ？
谢谢
【在 r*********n 的大作中提到】
: 关键字：随机
: 用Monte Carlo simulation，算法复杂都和你要求的精度有关系
: 比如精度要提高一位(0.1)，sampling number就要是原来的100倍，所以大致是O(n^2)
: 这个和算法没有什么关系，其实是numerical method，wikipedia上面有解释。
J*9
11 楼
a1 = area of one card
a52 = a1*52
return a random number from (a1..a52)
All numbers are double.
:-)
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
a52 = a1*52
return a random number from (a1..a52)
All numbers are double.
:-)
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
t*a
12 楼
顶这个
【在 k*******a 的大作中提到】
: 算expectation的话很简单, 假设牌面积a， 桌子面积b
: 对于桌子的每一个点， 被一张扑克牌覆盖的概率是 a/b, 这样被52张牌至少一张覆盖
: 的概率是：
: 1 - (1 - a/b)^52
: 这样，expected覆盖面积是 b*[1 - (1 - a/b)^52]
【在 k*******a 的大作中提到】
: 算expectation的话很简单, 假设牌面积a， 桌子面积b
: 对于桌子的每一个点， 被一张扑克牌覆盖的概率是 a/b, 这样被52张牌至少一张覆盖
: 的概率是：
: 1 - (1 - a/b)^52
: 这样，expected覆盖面积是 b*[1 - (1 - a/b)^52]
g*s
13 楼
不知道你面的什么职位。如果是和统计相关的那应该是按其他人说的随机、概率的方法
估算。
我说的是偏graphics方向的实际coding方法。
重叠问题对于扑克类似于两个oriented bounding box的collision detection问题。
树可以用kd tree存储扑克坐标
每次记录坐标是必然的，不论用树还是grid，只不过tree的search是logn，grid的
search是1
tree
每次
【在 m****r 的大作中提到】
: 请问， 第一种 ：一种是每次遍历之前所有的牌，看和哪些重叠。总时间n^2, 用tree
: 可以优化趋近于
: 如何 “看和哪些重叠” ？ 比较每张牌的坐标吗 ？
: 如何用 树 优化 能达到 n lg n , 而且 空间为1 ？
: 第二种：
: 一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
: 这个也要 记录下所有 牌的坐标吧 ？ 要不， 如何 知道是否在 ｇｒｉｄ 里面 ？
: 谢谢
估算。
我说的是偏graphics方向的实际coding方法。
重叠问题对于扑克类似于两个oriented bounding box的collision detection问题。
树可以用kd tree存储扑克坐标
每次记录坐标是必然的，不论用树还是grid，只不过tree的search是logn，grid的
search是1
tree
每次
【在 m****r 的大作中提到】
: 请问， 第一种 ：一种是每次遍历之前所有的牌，看和哪些重叠。总时间n^2, 用tree
: 可以优化趋近于
: 如何 “看和哪些重叠” ？ 比较每张牌的坐标吗 ？
: 如何用 树 优化 能达到 n lg n , 而且 空间为1 ？
: 第二种：
: 一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
: 这个也要 记录下所有 牌的坐标吧 ？ 要不， 如何 知道是否在 ｇｒｉｄ 里面 ？
: 谢谢
r*n
14 楼
假设桌子面积为area_t，扑克总面积为area_p，那么uniformly toss a point, the
probability that the point falls into poker area is
prob = area_p/area_t
since you know area_t, you only need to compute prob, which is done using
Monte Carlo simulation.
basically, you randomly toss a point and decide whether or not it falls onto
any of the 52 cards (this is done using O(1) time), then
prob = # yes / # total tests
【在 m****r 的大作中提到】
: 如何 用 Monte Carlo simulation 来做呢 ？
: 能具体说说吗 ？
: 谢谢
probability that the point falls into poker area is
prob = area_p/area_t
since you know area_t, you only need to compute prob, which is done using
Monte Carlo simulation.
basically, you randomly toss a point and decide whether or not it falls onto
any of the 52 cards (this is done using O(1) time), then
prob = # yes / # total tests
【在 m****r 的大作中提到】
: 如何 用 Monte Carlo simulation 来做呢 ？
: 能具体说说吗 ？
: 谢谢
r*n
15 楼
nice
we can think of putting cards on a table one at time as an ergodic
stochastic process. the time average converges to the expectation when # of
cards, say m, is sufficiently large. this means
b*[1 - (1 - a/b)^m] -> b as m -> infinite
this makes sense since the total area is fixed
【在 k*******a 的大作中提到】
: 算expectation的话很简单, 假设牌面积a， 桌子面积b
: 对于桌子的每一个点， 被一张扑克牌覆盖的概率是 a/b, 这样被52张牌至少一张覆盖
: 的概率是：
: 1 - (1 - a/b)^52
: 这样，expected覆盖面积是 b*[1 - (1 - a/b)^52]
we can think of putting cards on a table one at time as an ergodic
stochastic process. the time average converges to the expectation when # of
cards, say m, is sufficiently large. this means
b*[1 - (1 - a/b)^m] -> b as m -> infinite
this makes sense since the total area is fixed
【在 k*******a 的大作中提到】
: 算expectation的话很简单, 假设牌面积a， 桌子面积b
: 对于桌子的每一个点， 被一张扑克牌覆盖的概率是 a/b, 这样被52张牌至少一张覆盖
: 的概率是：
: 1 - (1 - a/b)^52
: 这样，expected覆盖面积是 b*[1 - (1 - a/b)^52]
m*r
16 楼
About "you randomly toss a point and decide whether or not it falls onto any
of the 52 cards"
The cards can overlap partially.
How to handle this case ?
Any help would be appreciated !
onto
【在 r*********n 的大作中提到】
: 假设桌子面积为area_t，扑克总面积为area_p，那么uniformly toss a point, the
: probability that the point falls into poker area is
: prob = area_p/area_t
: since you know area_t, you only need to compute prob, which is done using
: Monte Carlo simulation.
: basically, you randomly toss a point and decide whether or not it falls onto
: any of the 52 cards (this is done using O(1) time), then
: prob = # yes / # total tests
of the 52 cards"
The cards can overlap partially.
How to handle this case ?
Any help would be appreciated !
onto
【在 r*********n 的大作中提到】
: 假设桌子面积为area_t，扑克总面积为area_p，那么uniformly toss a point, the
: probability that the point falls into poker area is
: prob = area_p/area_t
: since you know area_t, you only need to compute prob, which is done using
: Monte Carlo simulation.
: basically, you randomly toss a point and decide whether or not it falls onto
: any of the 52 cards (this is done using O(1) time), then
: prob = # yes / # total tests
r*n
17 楼
you know the center and the orientation (assuming card is rectangle) for
each card
to test whether a point falls onto a particular card is equivalent to test
whether a 2D point is within a rectangle.
one way to do this is to write down the line equations for all sides in the
form f(X,Y) = aX + bY + c = 0... and check
f_1(x, y)*f_2(x, y) <= 0 && f_3(x, y)*f_4(x, y) <= 0
here f_1 and f_2 denote the line equations of parallel sides and similarly f
_3, f_4. f_1(x, y)*f_2(x, y) <= 0 means point (x,y) is between the two
parallel sides.
you can use the above method repetitively for all 52 cards, irrespective of
how they overlap. and output true if one of the tests returns true.
ps: there may be better ways to test whether a 2D point is within a
rectangle.
any
【在 m****r 的大作中提到】
: About "you randomly toss a point and decide whether or not it falls onto any
: of the 52 cards"
: The cards can overlap partially.
: How to handle this case ?
: Any help would be appreciated !
:
: onto
each card
to test whether a point falls onto a particular card is equivalent to test
whether a 2D point is within a rectangle.
one way to do this is to write down the line equations for all sides in the
form f(X,Y) = aX + bY + c = 0... and check
f_1(x, y)*f_2(x, y) <= 0 && f_3(x, y)*f_4(x, y) <= 0
here f_1 and f_2 denote the line equations of parallel sides and similarly f
_3, f_4. f_1(x, y)*f_2(x, y) <= 0 means point (x,y) is between the two
parallel sides.
you can use the above method repetitively for all 52 cards, irrespective of
how they overlap. and output true if one of the tests returns true.
ps: there may be better ways to test whether a 2D point is within a
rectangle.
any
【在 m****r 的大作中提到】
: About "you randomly toss a point and decide whether or not it falls onto any
: of the 52 cards"
: The cards can overlap partially.
: How to handle this case ?
: Any help would be appreciated !
:
: onto
w*p
18 楼
我猜这个是和 GIS 有关职位的面试题。
在这个是一个和实际问题很像的问题。
先用模拟做出所有扑克牌的位置。
然后就是合并所有相连的几何图。（这个有专门的算法的， 不记得了。）
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
在这个是一个和实际问题很像的问题。
先用模拟做出所有扑克牌的位置。
然后就是合并所有相连的几何图。（这个有专门的算法的， 不记得了。）
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
g*e
19 楼
记录下每张扑克牌的中心坐标，角度。以及当前总覆盖面积。
每放下新的一张牌a,通过中心坐标找跟a附近的其他牌 ，用这些牌来覆盖a，算出未被
任何牌覆盖的声誉面积，更新总覆盖面积。
每放下新的一张牌a,通过中心坐标找跟a附近的其他牌 ，用这些牌来覆盖a，算出未被
任何牌覆盖的声誉面积，更新总覆盖面积。
m*r
20 楼
每张牌有四个 2 D 坐标， 如何用比较坐标的方法来确定若干张牌之间的位置关系 ？
谢谢
【在 g*******s 的大作中提到】
: 不知道你面的什么职位。如果是和统计相关的那应该是按其他人说的随机、概率的方法
: 估算。
: 我说的是偏graphics方向的实际coding方法。
: 重叠问题对于扑克类似于两个oriented bounding box的collision detection问题。
: 树可以用kd tree存储扑克坐标
: 每次记录坐标是必然的，不论用树还是grid，只不过tree的search是logn，grid的
: search是1
:
: tree
: 每次
谢谢
【在 g*******s 的大作中提到】
: 不知道你面的什么职位。如果是和统计相关的那应该是按其他人说的随机、概率的方法
: 估算。
: 我说的是偏graphics方向的实际coding方法。
: 重叠问题对于扑克类似于两个oriented bounding box的collision detection问题。
: 树可以用kd tree存储扑克坐标
: 每次记录坐标是必然的，不论用树还是grid，只不过tree的search是logn，grid的
: search是1
:
: tree
: 每次
g*s
21 楼
search separating axis theory
？
【在 m****r 的大作中提到】
: 每张牌有四个 2 D 坐标， 如何用比较坐标的方法来确定若干张牌之间的位置关系 ？
: 谢谢
？
【在 m****r 的大作中提到】
: 每张牌有四个 2 D 坐标， 如何用比较坐标的方法来确定若干张牌之间的位置关系 ？
: 谢谢
w*p
22 楼
求两个图形是否overlapping， overlapping 的面积。这个也是有专门的算法的。
不过这个是长方形容易点。
长方形A, 长方形B
你可以求A的每个点是否都在B的外侧，并且不crossB. 这样A 和 B 就是分开的。
如果A B 是overlapping, 求出每个相交的每个点。 计算出面积。 （计算面积，这个
也是有专门的几何公式）
？
【在 m****r 的大作中提到】
: 每张牌有四个 2 D 坐标， 如何用比较坐标的方法来确定若干张牌之间的位置关系 ？
: 谢谢
不过这个是长方形容易点。
长方形A, 长方形B
你可以求A的每个点是否都在B的外侧，并且不crossB. 这样A 和 B 就是分开的。
如果A B 是overlapping, 求出每个相交的每个点。 计算出面积。 （计算面积，这个
也是有专门的几何公式）
？
【在 m****r 的大作中提到】
: 每张牌有四个 2 D 坐标， 如何用比较坐标的方法来确定若干张牌之间的位置关系 ？
: 谢谢
w*p
23 楼
好奇下，这个是电面还是onsite啊。要是电面，并且没有接触过GIS的几何算法，要当
时写代码，是挺难的。
搜下， 网上有专门的GIS 的几何算法总汇。
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
时写代码，是挺难的。
搜下， 网上有专门的GIS 的几何算法总汇。
【在 m****r 的大作中提到】
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
i*1
24 楼
这个方法很困难的。
每次遍历之前的牌时，为何是n^2,应该是n吧。谁能解释一下？
还有一个问题，每次遍历，不仅仅要遍历两张牌的重叠面积，还要计算三张、四张...
的重叠面积，这样算下来，复杂度是2^n，而不是n^2.
【在 g*******s 的大作中提到】
: 你这个只能pseudo code吧，不然细节太多就变成图形学问题了。光是求两张任意角度
: 的牌并集面积就有的写了。
: 总体两种思路，都是对每一张新牌，求他和之前所有牌的并集面积。主要区别在于如何
: 找nearest neighbours
: 一种是每次遍历之前所有的牌，看和哪些重叠。总时间n^2, 用tree可以优化趋近于
: nlogn, 空间1。
: 一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
: 根据新牌的落点可以直接找出之前落在这个grid的所有牌。总时间n， 空间m，m是桌面
: 的大小。
每次遍历之前的牌时，为何是n^2,应该是n吧。谁能解释一下？
还有一个问题，每次遍历，不仅仅要遍历两张牌的重叠面积，还要计算三张、四张...
的重叠面积，这样算下来，复杂度是2^n，而不是n^2.
【在 g*******s 的大作中提到】
: 你这个只能pseudo code吧，不然细节太多就变成图形学问题了。光是求两张任意角度
: 的牌并集面积就有的写了。
: 总体两种思路，都是对每一张新牌，求他和之前所有牌的并集面积。主要区别在于如何
: 找nearest neighbours
: 一种是每次遍历之前所有的牌，看和哪些重叠。总时间n^2, 用tree可以优化趋近于
: nlogn, 空间1。
: 一种是把桌面分成2D grids。每来一张牌就根据落点register到相应的grid。这样每次
: 根据新牌的落点可以直接找出之前落在这个grid的所有牌。总时间n， 空间m，m是桌面
: 的大小。
i*1
25 楼
这个方法不对，(a1,a52)中的每一种数值的概率并不相等，而且差别很大。
a1只有一种可能。但是a26可能就多了。
【在 J**9 的大作中提到】
: a1 = area of one card
: a52 = a1*52
: return a random number from (a1..a52)
: All numbers are double.
: :-)
a1只有一种可能。但是a26可能就多了。
【在 J**9 的大作中提到】
: a1 = area of one card
: a52 = a1*52
: return a random number from (a1..a52)
: All numbers are double.
: :-)
i*1
26 楼
赞，简洁，明了。
onto
【在 r*********n 的大作中提到】
: 假设桌子面积为area_t，扑克总面积为area_p，那么uniformly toss a point, the
: probability that the point falls into poker area is
: prob = area_p/area_t
: since you know area_t, you only need to compute prob, which is done using
: Monte Carlo simulation.
: basically, you randomly toss a point and decide whether or not it falls onto
: any of the 52 cards (this is done using O(1) time), then
: prob = # yes / # total tests
onto
【在 r*********n 的大作中提到】
: 假设桌子面积为area_t，扑克总面积为area_p，那么uniformly toss a point, the
: probability that the point falls into poker area is
: prob = area_p/area_t
: since you know area_t, you only need to compute prob, which is done using
: Monte Carlo simulation.
: basically, you randomly toss a point and decide whether or not it falls onto
: any of the 52 cards (this is done using O(1) time), then
: prob = # yes / # total tests
相关阅读
本版上过去的一些帖子为什么会突然无法访问了呢问几道老题问另一道电话号码查询的题遇到完全不懂H1B的公司该怎么处理Job hunting? Books sale. Tks.最近微软是不是在狂涨工资？？回email写错单词是不是硬伤啊。申请opt的时候要定一个开始时间,大家知道最早是什么时候开始吗？帮朋友贴一个工作，BD MANAGER,湾区明年6月毕业，什么时候开始找工作比较好？请教版上各位兄弟姐妹KPMG IT advisory 发展前景如何OPT延期问题Why I am not excited about offers经典面试题到底是RECRUTER 找我还是公司招？感恩节有没有打折送offer的有没有面过blakcrock alladin & technology的？用一个offer催另一公司做hiring decision要注意什么？大家opt申请都是什么方式邮寄的同一个contract的职位,3家staff company联系