给Google onsite面经添砖加瓦

第四轮的第二问是说最后还剩一整片的概率是多大嘛？

补充内容 (2016-10-16 00:40):
如果是的话那概率就是1/199吧

猫头鹰也是猫 发表于 2016-10-16 00:14
第一问应该没问题，但第二问还不大对，你看7那个例子

第二问做法和leetcode397很像：
对于当前的n如果n%2 == 0那就把n往右进一bit；
如果n%2 != 0那么分两种情况：
如果n的最后两bit是3，那么就n+1；否则的话（最后两bit是1）那么就n-1；
最后就记录下n+1或n-1的次数就好

比如对于n=7的算法是：
7 (+1)-> 8 -> 4 -> 2 -> 1 (-1) -> 0

两次+1或-1，所以答案是2

7 (最后两bit是1) -> 6

补充内容 (2016-10-16 00:44):
忽视最后一行。。。。

yxyxyx 发表于 2016-10-16 12:07
是这个意思。其实从某个角度上这题和Leetcode397很像。

我的理解是followup是如果有连续三个1后者更多就加个1，这样进位导致1的减少大于加个1带来的个数

补充内容 (2016-10-16 12:51):
oops，没看到后面内容，理解是一样的

yxyxyx 发表于 2016-10-16 12:44
第二问做法和leetcode397很像：
对于当前的n如果n%2 == 0那就把n往右进一bit；
如果n%2 != 0那么分两种 ...

赞呀！！！！

给一个iterator: 2,3,1,5,1,8… 要求写一个iterator要能return 3,3,5,8…  
why return 3,3,5,8 ?

楼主好运

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

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

意思应该是说第一个iterator的含义是2个3，1个5，1个8...

yxyxyx 发表于 2016-10-16 12:44
第二问做法和leetcode397很像：
对于当前的n如果n%2 == 0那就把n往右进一bit；
如果n%2 != 0那么分两种 ...

这个题目的确和LC397很像，但是有区别。但是都是通过贪心算法解决。个人认为@Hmoon的解法很对的，直接了当。至于你说的这种方法，存疑，感觉只记录n+1, n-1次数不对。比如说111,000,000,011。对于这个 case，答案是4，但是如果只记录加减次数，结果是3

猫头鹰也是猫 发表于 2016-10-16 12:14
第一问应该没问题，但第二问还不大对，你看7那个例子

楼主，可以解释下为什么不对吗？我没有想明白，感觉是正确的

yxyxyx 发表于 2016-10-16 12:39
第四轮的第二问是说最后还剩一整片的概率是多大嘛？

补充内容 (2016-10-16 00:40):

后来在坛子里搜了原来有这个题的面经，思路大致就是用dfs+memoization。传送门http://www.1point3acres.com/bbs/ ... 2BOnsite&page=1