Google MTV 10/30 new grad onsite interview

marthew777 发表于 2015-10-31 15:52
多谢翻译代码，我的思路和你一样。。不过这样一想，面试的时候用python简直是cheating啊。。

我平时干活都是用的c++，为了刷题专门学的python

清除掉所有的草最后回到原地，要求没有格子只visit一次吗，如果是，这是欧拉回路啊，先判断是否是欧拉回路，然后欧拉回路的解法是固定的。

补充内容 (2015-11-1 13:09):
sorry, 这是汉密尔顿图，不是欧拉，只能dfs算吧。。。。。够复杂的。

marthew777 发表于 2015-10-31 14:08
最后一题我刚写了一下，100多行代码。。不过这题蛮有意思的！！

其实这题模板是subsets类似, 不清楚要不要这么多行. 就是recursion后, 再打印出相反方向即可, 这样就表示回头了.
我当时面的时候一直在纠结怎么回头, 其实recursion 完直接打印相反方向就可以了...哎

feierqi 发表于 2015-11-2 04:24
问一下楼主第三题的binarysearch是怎么搞的，我刚才写了一下，只能loop到最后的k，然后开始找，如果按你说 ...

把每一次的A,B,C看成一个block
找到k使得我们可以从n的那个character所在的block开始搜索, 而不是从第一个block开始搜索, 这样就把running time缩短为O(log n)了.

feierqi 发表于 2015-11-2 07:01
额，我还是不是很明白，你是指ABC 是一个block， AABBCC是一个block这个意思吧，那么你找到第k个block， ...

3 * (2 ^ k - 1)就是求和公式
表示前k个block的char 总数
找到这个k之后
你就可以从i = 3 * (2 ^ k - 1) + 1开始, 直到i == n

请问lz除草那题，是说每个草的位置只能遍历一遍还是所有的位置都只能遍历一遍，还是说没有要求啊？

cccxfdj 发表于 2015-11-2 07:09
3 * (2 ^ k - 1)就是求和公式
表示前k个block的char 总数
找到这个k之后

那直接让3*(2^k-1) = n,解出k就行了吧？感觉可以O(1)。。