给Google onsite面经添砖加瓦

mad_air 发表于 2016-10-16 17:44
楼主好运

请问第四题第二问那个概率怎么求的啊？是直接写算式还是写代码啊？

谢谢！要写代码。整个过程可以用个二叉树来模拟，因为每天取的要么是整片要么是半片，然后每条edge的概率都可以根据当前整片和半片的比例算出来。最后要找的是到final state的所有path。

jfree811 发表于 2016-10-16 11:50
第一问是不是就是让你求二进制数上面 所以1的个数？然后follow up的解法是不是从二进制数从最右开始有多少 ...

我觉得follow up思路是这样的， 对大于2个的连续1用减法处理更好，其他情况用加法。

wtcupup 发表于 2016-10-16 16:11
给一个iterator: 2,3,1,5,1,8… 要求写一个iterator要能return 3,3,5,8…  
why return 3,3,5,8 ?

我觉得是两个3，一个5，一个8的意思

猫头鹰也是猫 发表于 2016-10-16 22:57
后来在坛子里搜了原来有这个题的面经，思路大致就是用dfs+memoization。传送门http://www.1point3acres.c ...

不太明白额，这里为啥要用memoization呢？

knight0clk 发表于 2016-10-16 22:57
楼主，可以解释下为什么不对吗？我没有想明白，感觉是正确的

嗯 大致思路应该是正确的 就是要注意从右开始把连续三个以上1简化了以后要对结果继续往前检查

william_gong 发表于 2016-10-16 23:14
不太明白额，这里为啥要用memoization呢？

相同的state会在这个tree中会多次出现，然后底下的subtree都是一样的

chestnut9919 发表于 2016-10-16 12:33
求问楼主第四题用了什么方法？用什么数据结构存的药片？

用两个int就可以了

knight0clk 发表于 2016-10-16 10:54
这个题目的确和LC397很像，但是有区别。但是都是通过贪心算法解决。个人认为@Hmoon的解法很对的，直接了 ...

不是啊，我的算法仍然是4啊
111,000,000,011 (+1) -> 111,000,000,100 (往右进两位）-> 001,110,000,001(-1) -> 001,110,000,000 (往右进7位) -> 000,000,000,111 (+1) -> 000,000,001,000 (往右进三位）-> 000,000,000,001(-1) -> 000,000,000,000

这样有4次+1或者-1，所以答案是4.

不过你倒是提醒了我一下，不知道在算这个的时候需不需要考虑integer的范围问题，比如不能用超出integer表示范围的2^n来参与运算什么的。比如说这个题目的数的类型是unsigned int, 且2^17不能参与运算，那么你那个数的结果就不是4了而应该是5.

猫头鹰也是猫 发表于 2016-10-16 10:57
后来在坛子里搜了原来有这个题的面经，思路大致就是用dfs+memoization。传送门http://www.1point3acres.c ...

恩。暴力算是一种算法。其实我感觉也可以数学算出来。下面写一下算法，不知道正确与否。。。

比如一开始有m个整片的和n个半片的，吃完之后的结果是k个整片和l个半片。

因为一次只能吃半片，所以我们可以把所有的药先全部拆成半片，那就变成了一开始有(2*m+n)个半片，吃完了剩下(2*k+l)个半片。一共吃了(2*m+n) - (2*k+l)个半片。

那么不论结果如何，所有吃法一共有C((2*m+n), (2*m+n) - (2*k+l))个。C(a, b)就是那个组合函数，从a里面挑b个。

接下来我们看整片的在吃完了之后少了几个，因为如果m和k不同的话说明至少吃过(m-k)个整片。所以吃整片（不论是否吃完）的吃法有C(m, m-k)个。
最后我们看在吃过整片之后吃了多少个半片。吃过(m-k)个整片各一次之后的半片数量是n+(m-k)，剩下了l个半片，所以半片的吃法是C(n+(m-k), n+(m-k)-l).

所以最后的概率就是

C(m, m-k) * C(n+(m-k), n+(m-k)-l) / C((2*m+n), (2*m+n) - (2*k+l))

不过这个方法没有验证过，谨慎看待。。。

谢谢楼主详细的分享，看楼主最近的面试还挺多的，祝好运啊！