Google on campus

22691482 发表于 2014-10-31 12:37
说来话长啊。。。主要是跟面试官聊，一步步的改进时间和空间。。更注重过程吧。

random number 那题，说说你的想法。

22691482 发表于 2014-11-4 03:20
你好，，请问代码里面的segsum是干嘛的？

注释里不是说了，用来存从index i 到index j 的所有元素的和。

averillzheng 发表于 2014-11-4 03:24
注释里不是说了，用来存从index i 到index j 的所有元素的和。

maxPick[i][j] = Math.max(arr[i] + segSum[i + 1][j] - maxPick[i + 1][j],
                                    arr[j] + segSum[i][j - 1] - maxPick[i][j - 1]);

可不可以详细解释下这个递推式？

maxPick 是 从 i 到 j 可以得到的max sum 吗？
segSum[i + 1][j] - maxPick[i + 1][j] 是从i+1 到 j 另外一个玩家得到的maxSum吧？

谢谢。

averillzheng 发表于 2014-11-4 03:23
random number 那题，说说你的想法。

首先是把0到max用个数组存起来
面试官说优化空间
然后我说用个哈希表去掉bad numbers
面试官说再优化空间
然后提示1,2,3,4,5. 如果bad numbers {2,3}, 随机到3，我从3往右边走，会有什么问题。
我说4的概率会比其他大。
然后提示max - size of bad numbers 会得到什么？
然后我说可以只随机max - size of bad numbers 个数。
这个可以用两个指针，一个从0到max，一个指在bad numbers数组里面。
然后他说再优化空间
可以直接看bad numbers里面的数，得出“good numbers” 的个数，然后根据随机数返回。

22691482 发表于 2014-11-4 03:51
首先是把0到max用个数组存起来
面试官说优化空间
然后我说用个哈希表去掉bad numbers

这个题主要是怎么样弄才能使每个数出现的概率一样。

averillzheng 发表于 2014-11-4 04:21
这个题主要是怎么样弄才能使每个数出现的概率一样。

就是讨论吧。。。 直接给最优解估计面试官也会很迷茫。。

你看看我回你的那个DP解法。

22691482 发表于 2014-11-4 03:47
maxPick[j] = Math.max(arr + segSum[j] - maxPick[j],
                                    arr[j] + ...

你理解的都是对的。
maxPick[i][j]就是表示从i到j第一个player可以得到的最大的。
他可以取arr[i]也可以取arr[j]. 当他取了一个之后他就在后面的过程中成了第二个player。
所以它能得到的就是arr[i] + total sum  from (i + 1) to j - 从i +1 to j第一个player的maxPick， 或这arr[j] + total sum from i to (j - 1) - 从 i  to (j - 1)第一个player 的maxPick。 这就是那个递归的含义。

averillzheng 发表于 2014-11-4 07:01
你理解的都是对的。
maxPick[j]就是表示从i到j第一个player可以得到的最大的。
他可以取arr也可以取arr ...

我有个地方还是不太清楚。。 不好意思。。

maxPick[i][j]都是表示player1的吗？

如果是的话:total_sum[i+1,j] - maxPick[i+1,j] 应该表示的是player2的解。

那么arr[i] + player2 的解是什么意思？

22691482 发表于 2014-11-4 08:14
我有个地方还是不太清楚。。 不好意思。。

maxPick[j]都是表示player1的吗？

player1 已经取了arr【i】 或者arr【j】。
这样player1 就变成了player2. 而原来的player2 就变成了player1.

随机数的题就是用两个random就可以了。
我取max = 10， badNum = [2,3,7];
run 了我的代码1000000000 次，得到的结果是：
142863390 142859239 0 0 142869697 142870183 142844284 0 142860162 142833045
每个数都可以等概率的得到。