google onsite最后轮的题

onsite最后一轮的面试题。其他轮都没啥发的必要就不发了。题目是这样的 给

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

同。不算难，但是我对概率的不太擅长

小A要当码农 发表于 2017-2-4 04:39
assume 每个长方形不重叠。 先按照面积（建一个prefix sum数组）， 随机得到一个矩形。 再按照那个矩形的长 ...

能解释一下 这句话什么意思不？
“先按照面积（建一个prefix sum数组）， 随机得到一个矩形”

小A要当码农 发表于 2017-2-4 04:39
assume 每个长方形不重叠。 先按照面积（建一个prefix sum数组）， 随机得到一个矩形。 再按照那个矩形的长 ...

如果所有长方形面积的总和是 n，随机取个i，然后找这个i在prefix sum数组里的index，请问是这样吗？

assume 每个长方形不重叠。 先按照面积（建一个prefix sum数组）， 随机得到一个矩形。 再按照那个矩形的长和宽随机得到一个点。

小A要当码农 发表于 2017-2-4 04:39
assume 每个长方形不重叠。 先按照面积（建一个prefix sum数组）， 随机得到一个矩形。 再按照那个矩形的长 ...

我问了最优解 思路是这样没错，但是随机每个矩阵得到的概率是不一样的。再填这一部就好

304671127 发表于 2017-2-4 04:50
我问了最优解 思路是这样没错，但是随机每个矩阵得到的概率是不一样的。再填这一部就好

对呀  得到每个矩阵的概率跟矩阵的面积呈正比

小A要当码农 发表于 2017-2-4 04:52
对呀  得到每个矩阵的概率跟矩阵的面积呈正比

不是正比， 是反比。面积越大，选到这个矩形的概率就越小。。

补充内容 (2017-2-4 04:55):
对不起 我错了 是正比。

304671127 发表于 2017-2-4 04:55
不是正比， 是反比。面积越大，选到这个矩形的概率就越小。。

补充内容 (2017-2-4 04:55):

嗯嗯  楼主其他还面了啥题呀？

小A要当码农 发表于 2017-2-4 04:39
assume 每个长方形不重叠。 先按照面积（建一个prefix sum数组）， 随机得到一个矩形。 再按照那个矩形的长 ...

没懂　生成什么样presum, 怎么得到一个矩形呢？

对的～～～～

如果长方形会覆盖，那么是不是用这个思路：
把所有点放进hashset，这样重复的点就会被滤掉，同时把不重复的点放进一个array。
这样就统计出了有多少不重复的点(比如n个)，然后就取0....n-1之间的随机数，然后去array里取出来即为结果。

补充内容 (2017-2-4 18:22):
如果既覆盖又是double型，那这个方法就行不通了