Google intern 1月6日 hangout视频面试（两轮）

kazi16 发表于 2016-1-8 04:11
1. When we copy a block of data from main memory to the cache, where exactly should we put it?
2. H ...

恕我用中文了~
其实他没问这么细，就是给了这么一个setup看我怎么应变。我觉得并不是考对cache的理解。

dengke 发表于 2016-1-9 06:22
第一先sort以后，扫一遍找到小于钱数的最大数值，存起来。
然后放两个指针在开头和这个位置上，相互靠近移 ...

嗯我觉得你给的做法应该是最好的。

我当时用binary search写的还是遍历整个数组所以还是O(nlogn)的算法。

那个随机数问题。。如果已经有生成1-8的方法了，那生成1-7是不是把输出8的情况discard掉就好了？。。这样剩下7个数也是等概率的

dengke 发表于 2016-1-9 06:42
那个随机数问题。。如果已经有生成1-8的方法了，那生成1-7是不是把输出8的情况discard掉就好了？。。这样剩 ...

是的。。。是我太笨了。。

To generate 1 ~ 7 with probability of each number being 1/7, we can apply the results of generating 1 ~ 8 except that we simply rethrow the coins when we get 8. With geometric series, it can be proved that the probability is exactly 1/7.

第一题 觉得是多重背包问题， 有人同意吗？

1- 7 应该就是用前面1-8 然后如果是8 就重新扔3次。

第一题应该就是sort，然后两个指针一头一尾向中间靠就行了吧，时间复杂度是O(nlgn)

第一期quick sort+two points，再拿一个constant space记录距离目标最接近的值，如果扫的过程从大于目标扫到了小于目标且距离超过最接近的值，则直接return。