Google Onsite

fenghao 发表于 2017-8-20 17:20
第二题跟reserve sampling方法类似，但是需要给出最后观察到的哪个小朋友跟妈妈说的概率吧？要不怎么求啊？

第二题是道树的遍历问题， 不是reserve sampling。 一个小朋友可以给一个或者多个小朋友传递信息， 所以给reserve sampling没关系的。。。

edyyy 发表于 2017-8-20 22:48
第三题我画了个图，退了个公式没看出来短期内有个结果，然后搜了下居然是conjecture??!!!!恩，坑爹啊
http ...

没有， 不需要证明的， 这题的数学背景很浓， 但是我们只需要算下某个数是不是可以出现循环或者到1， 这题不是很难， 可能我表述不好， 不好意思哈

rgc588 发表于 2017-8-21 10:01
第二问好像是给个数看是否这个数会出现循环(记不太清了， 但是问题很简单不难）楼主在面试中证明了这个么？

不需要证明的

hackenkreuz 发表于 2017-8-21 02:46
感谢LZ分享！第二题还是有些疑问。

补充内容 (2017-8-21 02:48):

你的思路是对的， 但是每个同学和几个同学说了，是知道的， 就是相当于整个树的结构是知道的。

round2, a同学给bcd 3个同学传话, a同学给bcd3个同学传的话需要是一致的吗, 全真全假, 还是可以是一些真一些假?

天道酬勤 发表于 2017-8-22 07:53
round2, a同学给bcd 3个同学传话, a同学给bcd3个同学传的话需要是一致的吗, 全真全假, 还是可以是一些真一 ...

我感觉是一些真一些假吧

knight0clk 发表于 2017-8-22 08:04
我感觉是一些真一些假吧

全真全假不太好做, 一些真一些假这题就没意思了. 只要保证最后一层叶子节点(同学)满足母亲看到的序列, root是true, 中间所有的节点可以随意assign true和false, 一共有2^t中排列方式.

天道酬勤 发表于 2017-8-22 08:17
全真全假不太好做, 一些真一些假这题就没意思了. 只要保证最后一层叶子节点(同学)满足母亲看到的序列, ro ...

按楼主说的，应该是全真或全假。你感觉全真全假应该怎么做？我搞不太明白。。。是不是要枚举最后一层孩子的可能说谎情况，然后一层一层考虑，如果这是一个valid情况，把所有情况都算一遍，然后求说谎不说谎的概率？

software engineer不带方向吧