字节跳动算法一面非典型面经

（👇🏻可以当故事看，估计不会有下一个这样的选手了博君一笑）

开场自我介绍没几句就直接问题目：
圆上任意取三个点，求形成钝角三角形的概率。

拿到题目略懵，开了画图跟小哥说是1/8（直接取平均了）。小哥表示质疑这个解法，我思路跳转到积分。

双重积分太久没用过了有点卡，纠结挺久算出的结果还是1/8。小哥没看出式子错哪里了又看不到我具体计算过程，大概有点无语（毕竟他知道我的不是正确答案），而我觉得两个既然刚好合上了大概就是对的了（捂脸）。

小哥提醒我可能算错了。我深知自己计算能力巨菜，看了看时间还有25分钟就我表示“算了我们写个模拟生成的验证一下吧”。小哥略质疑代码能不能写完不过还是同意了。

于是就开始现场写模拟...写完直接跑，发现math里函数名写错和random函数名写错（写代码老查api的选手...），改完模拟1000次算出733。

这时小哥大概如释重负（毕竟这个数学巨差的同学终于看起来要接近答案了...用词不当）而我再次一脸懵逼。努力找代码中的问题，怀疑弧度角度出错，验证以后发现不是。然而代码其他部分太清晰了看起来就没问题...

卡了一下小哥问我会不会就是正解...想了想表示对代码比对计算自信多了就只能坚定代码是对的（摔）。跑100000次跑了几次结果都在75000附近..

试探着问0.75是不是正解，小哥表示是的。又问正常解法是什么（从我提出代码模拟他十分惊奇来看我大概是第一个这么做的人了）,回答限制条件下的规划问题。画图画了画，真的是...显然3/4

然后就结束了一面...问了有没有下一轮表示有，小哥挺开心的留我在原地挣扎...

有什么教训吗大概是有的hhh
1. 要练好计算不要像楼主这样不断出错
2.要认真看面经避免我这种warm up题目解完全程（预想中他应该问点ml啊挂）

这里有一个超级简单又可以generalize的方法。
三点在一个半圆里的概率可以想象成：先确定一点， 另两点在由第一个点顺时针方向形成的半圆里面，所以概率是 (1/2) ^2；现在我们有3个点，有三种形成半圆的做法，并且是mutually exclusive的，那么总概率就是3 * (1/2) ^2 = 3/4.

https://sbjoshi.wordpress.com/2009/10/04/puzzle-semi-circle-covering-n-points/

这个没有必要积分呀，先把圆分成两个半圆，想做钝角三角形，必然三个点要在同一个半圆内，这样概率就是1/2 * 1/2 * 1/2 = 1/8。

补充内容 (2020-3-14 02:03):
我这个是错误的。不要看这个。

jerry4013 发表于 2020-3-13 18:52
这个没有必要积分呀，先把圆分成两个半圆，想做钝角三角形，必然三个点要在同一个半圆内，这样概率就是1/2  ...

这个思路可以麻烦再解释一下吗？比如有A, B, C 三个点，A假设已经取定，条件概率能不能表达这个问题？

https://blog.csdn.net/qq_18055167/article/details/82924726  这个是后来面试官提到的方法。挺迷惑的，我觉得这个方法非常有道理...而且代码写出随机模拟三个点也是0.75,

子轩不语 发表于 2020-3-13 19:21
这个思路可以麻烦再解释一下吗？比如有A, B, C 三个点，A假设已经取定，条件概率能不能表达这个问题？
...

看了答案，我那个说法是错的。我只是直觉上觉得三个点在圆的一侧的概率应该是1/8，但其实是要考虑概率空间的问题。。。

能想到模拟也是很厉害了😂

Pi分之一乘以[(1-(theta/2Pi))的关于theta的从0到Pi的积分]=3/4

粗略积分算一下就行了，A先定下来了，然后就是定B,C的问题。
定B的时候我发现A跟B的圆心角是x度的时候，那锐角三角形的概率就是x/360.
那从AB圆心角从1度到180度加起来就是(1/360 + 2/360 + 3/360 + ... + 180/360) = 45， 除以180就是1/4了。

2019emmaemma 发表于 2020-3-14 02:34
这里有一个超级简单又可以generalize的方法。
三点在一个半圆里的概率可以想象成：先确定一点， 另两点在 ...

这个思路很好，简单来说：

如果都在一个半圆1/2，100%钝角 1/2
如果各在一个半圆1/2，50%钝角 1/4

所以最终就是3/4

DYDEMIMEI 发表于 2020-3-13 23:43
Pi分之一乘以[(1-(theta/2Pi))的关于theta的从0到Pi的积分]=3/4

画了个图感觉这个解法有道理。可以假设一个点固定，\theta是第二个点与第一个点之间的夹角。那么第三个点可以形成钝角三角形的概率是 （2 \pi - \theta）/ \theta。非常感谢