神秘莫测的狗狗虚拟表演

匿名用户 发表于 2020-10-05 19:14:10
我的解法是这样的，如果用random，那么随机地生成一个0到1之间的数，如果这个数小于等于p，就返回true，否则就返回false。

现在问题是，如何用这个0.5/0.5概率的method去生成

完全不知道如何从数学角度去理解这个方法 但是看上去很对 😂 感谢 受教了

谷歌面试是用什么面试呢，google docs吗，还是换了

匿名者 发表于 2020-10-6 10:14
我的解法是这样的，如果用random，那么随机地生成一个0到1之间的数，如果这个数小于等于p，就返回true， ...

LZ能不能详细讲讲为什么这个解法就能generate一个random number出来呢？已给LZ加米啦！

匿名者 发表于 2020-10-6 10:14
我的解法是这样的，如果用random，那么随机地生成一个0到1之间的数，如果这个数小于等于p，就返回true， ...

感觉好像理解了LZ的意思。看这样理解是不是更好理解一点:
假设我们要用这个func去generate一个0-15之间的数，因为这里面有16个数，2^4=16，所以我们就call这个func4次，每call这个func就形成一个bit，所以我们就有1/16的可能是0000，0110，1111...正好过来就是16个数字，所以就可以random [0-15]。这个题目是一个[0,1]的double，所以要先把这个p先转换成binary pb。double在java中是64bits的，所以这个binary pb也就最多64bits，所以最多call那个function 64次，每次形成一个0或者1的bit，最后形成的这个数是否比pb小，如果是则return true，否则return false。

匿名者 发表于 2020-10-6 14:25
谷歌面试是用什么面试呢，google docs吗，还是换了

码code的话用的是他们自己的，好像只有syntax highlight，不记得有没有autocomplete了。不是谷歌doc
视频的话用的是谷歌meet
系统设计的话说是可以用google drawing

litJordan 发表于 2020-10-6 15:17
感觉好像理解了LZ的意思。看这样理解是不是更好理解一点:
假设我们要用这个func去generate一个0-15之间 ...

对的紫薯紫薯紫薯

匿名者 发表于 2020-10-6 12:55
这个方法应该很多，只要一个round trip能回来就行。我用的直接就是serialize每个edge，然后存在一个list ...

请问楼主
1. 你说先给了两种graph表示方式，没想错的话我猜是(String, neighbors[])和用matrix表示所有边这两种，最后面试官让你用第二种是指哪一种？是(String, neighbors[])这种么？就是想知道你做的时候input是啥形式。
2. 你说“serialize每个 edge”是什么意思？
3. 因为是单向的所以要把node里面的string一起serialize啥意思？

ND0406 发表于 2020-10-6 09:15
第二轮第一题…我想了半天想不明白如何写，楼主能给个思路吗？
比如17.3%的概率的该如何获取？

我看到这个问题有一个很蠢的想法。(1)如果p <= 0.5  Math.random() < 2 * p 我就去call Method A.  大于我就直接return false. 这样返回 true的概率就是 2 * p / 2 = p. (2) 如果p > 0.5 我就 2 * (1 - p)的概率 call Method A,  剩下的直接return true. 不知道方法可行不可行?

请问楼主第一题图可以是用 map 表示邻接表吗 还是说面试官要求是每个 node 都是 custom Node class （类似于 TreeNode)。如果用 map 表示是不是比较容易实现。

其实第二题做binary search的同时随机，最后判断随机值和binary search的结果相比大还是小就好了吧。
试了一下，跑10万次之后区平均值，还挺准的。