Google MTV 10/30 new grad onsite interview

直接上题
1. 中国小哥, 人很nice.问的题目leetcode 原题 merge intervals, 这题其实我没做过,今天第一次见, 在小哥帮助下完成了, 然后问了关于sort function的应用(c++)
大家可以复习一下sort struct, 这个我没答出来. 然后问了quick sort, merge sort, 谁更稳定

2. 美国白人大叔, 人非常好, 挂着笑容. 这次是design question, 给了一段代码分析广告系统和账户, 要求指出问题.其实这题只要对oo design有所了解就可以

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

比较不够了, 这种题套模板会比较快.

总结一下: 通过并不多的面试经验, 感觉印度大叔普遍都比较严肃,而且出的题目难度比较大... 中国小哥可能看你是中国人,所以题目难度就会下来, 感谢.
最后就是,基本功得好, 尤其是debug的能力, 有时候不仅仅是做算法题, 还得会分析代码...

最后希望努力的人都有好的回报!

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

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

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

写了下最后一题

1. class Solution:
   
2.     def printPath(self, board, x, y):
   
3.         buf = [(x,y)]
   
4.         visited = set(buf)
   
5.         result = []
   
6.         dir = [(-1,0), (1,0), (0,-1), (0,1)]
   
7.         while buf:
   
8.             cur = buf[-1]
   
9.             flag = False
   
10.             for d in dir:
    
11.                 n_x, n_y = cur[0]+d[0], cur[1]+d[1]
    
12.                 if self.isValid(board, n_x, n_y) and not (n_x, n_y) in visited:
    
13.                     result.append(d)
    
14.                     buf.append((n_x, n_y))
    
15.                     visited.add((n_x, n_y))
    
16.                     flag = True
    
17.                     break
    
18.             if not flag:
    
19.                 cur = buf.pop()
    
20.                 if buf:
    
21.                     result.append((buf[-1][0]-cur[0], buf[-1][1]-cur[1]))
    
22. 
    
23.         return result
    
24. 
    
25.     def isValid(self, board, x, y):
    
26.         if x<0 or x>=len(board) or y<0 or y>=len(board[0]):
    
27.             return False
    
28.         if board[x][y]=='x':
    
29.             return False
    
30.         return True
    
31. 
    
32. 
    
33. sol = Solution()
    
34. result = sol.printPath(["x  x", "xx  ", "x   ", "    "], 0, 1)
    
35. print(result)

复制代码

楼主加油
顺便问问什么叫“把所有的草除掉并回到原点.”？这题到底干啥的？
谢谢了。

returning 发表于 2015-10-31 08:18
楼主加油
顺便问问什么叫“把所有的草除掉并回到原点.”？这题到底干啥的？
谢谢了。

就是空地表示草 需要traverse 每个有草的人pos 最后回到原地

我也碰到了那个印度大叔。。。跪了。。

boaever 发表于 2015-10-31 10:33
我也碰到了那个印度大叔。。。跪了。。

可能印度大叔就是难吧....

cccxfdj 发表于 2015-10-31 12:30
可能印度大叔就是难吧....

最后一题我刚写了一下，100多行代码。。不过这题蛮有意思的！！

gorilazz 发表于 2015-10-31 14:41
写了下最后一题

python我不太熟悉，不过我觉得你的代码，无法handle一些cases，比如, 走到死胡同后，需要走visited过的一些点从而寻找可能的其他的路直到无路可走，而你并没有打印出来这些往回走的movements，不过这并不难处理；还有，草可能并无法全部清楚，这时你应该退出给个通知还有多少草被堵住了；当草全部清楚后，还要重返原始的起点，返回的路可以是原路返回，也可以是shortest path，反正case多了去了~~

marthew777 发表于 2015-10-31 15:20
python我不太熟悉，不过我觉得你的代码，无法handle一些cases，比如, 走到死胡同后，需要走visited过的一 ...

我的思路是这样的：先用dfs，在访问的过程中要把路径都用stack存下来，方便backtracking。到了某个位置，如果它的邻居都被访问过没法往下走了，那就把它从stack里pop，然后那就按照原路返回退回到上一个位置（也就是当前stack的top），这一步就在循环的最后一部分实现了。

gorilazz 发表于 2015-10-31 15:36
我的思路是这样的：先用dfs，在访问的过程中要把路径都用stack存下来，方便backtracking。到了某个位置， ...

多谢翻译代码，我的思路和你一样。。不过这样一想，面试的时候用python简直是cheating啊。。