亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2437|回复: 19
收起左侧

Google MTV 10/30 new grad onsite interview

[复制链接] |试试Instant~ |关注本帖
cccxfdj 发表于 2015-10-31 06:34:30 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x

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

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

3. 中国小哥, 人很nice,看上去比我还紧张一点. 问的是给一个无穷的sequence, ABCAABBCCAAAABBBBCCCC... 每次A,B,C数量double, 然后问给一个正整数n, 求第n个char是什么.
第一个是A, 第二个是B, 以此类推...-google 1point3acres
这题一开始我就想把通项公式求出来,然后分不同的sequence做,然后一直卡在一个地方. 小哥提醒先用最简单的方法, 然后写出O(n) 算法, 之后我就知道怎么优化, 用binary search
求出最后一个k 使得 3 * (pow(2, k)) < n
然后从这个数字开始搜索, 这样最好的running time 是O(log(n))
. 鍥磋鎴戜滑@1point 3 acres
4. 印度大叔, 今天就跪在这里了... 首先人比较死板,然后态度很严肃.
之后, 直接开始做题,和前面不同的是, 题目直接写纸上. 第一题是分析一串代码, 问这代码是干嘛的,然后可能有什么问题.... 规定的是10分钟, 然后我大概超时了,而且最后也没看出来seg fault在哪. 这个真是基本功问题了可能
然后出了道题, 一个2d array of char, 'X'表示不能走, " "表示草地, 给一个初始x,y 然后把所有的草除掉并回到原点. 要求的是,每走一步打印一个方向, 最后打印出所有的方向... 想到了是dfs, 但是卡在往回走的过程了... 最后没写出全部的代码, 还被大叔嘲讽了.. 其实并不太难, dfs 可以解决. 主要是题目略长,然后时间比较不够了, 这种题套模板会比较快.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

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

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

评分

6

查看全部评分

本帖被以下淘专辑推荐:

hj867955629 发表于 2015-11-5 01:59:12 | 显示全部楼层
cccxfdj 发表于 2015-11-2 07:09
3 * (2 ^ k - 1)就是求和公式
表示前k个block的char 总数
找到这个k之后

那直接让3*(2^k-1) = n,解出k就行了吧?感觉可以O(1)。。
回复 支持 1 反对 0

使用道具 举报

gorilazz 发表于 2015-10-31 14:41:48 | 显示全部楼层
写了下最后一题
  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. 1point3acres.com/bbs
  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.鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.             if not flag:
  19.                 cur = buf.pop()
  20.                 if buf:
  21.                     result.append((buf[-1][0]-cur[0], buf[-1][1]-cur[1])). more info on 1point3acres.com
  22. . 1point3acres.com/bbs
  23.         return result

  24.     def isValid(self, board, x, y):
  25.         if x<0 or x>=len(board) or y<0 or y>=len(board[0]):
  26.             return False
  27.         if board[x][y]=='x':
  28.             return False
  29.         return True


  30. sol = Solution()
  31. result = sol.printPath(["x  x", "xx  ", "x   ", "    "], 0, 1)
  32. print(result)
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

宝贝忆彼岸 发表于 2015-11-3 14:32:01 | 显示全部楼层
请问lz除草那题,是说每个草的位置只能遍历一遍还是所有的位置都只能遍历一遍,还是说没有要求啊?
回复 支持 1 反对 0

使用道具 举报

returning 发表于 2015-10-31 08:18:33 | 显示全部楼层
楼主加油
顺便问问什么叫“把所有的草除掉并回到原点.”?这题到底干啥的?
谢谢了。
回复 支持 反对

使用道具 举报

 楼主| cccxfdj 发表于 2015-10-31 09:59:50 | 显示全部楼层
returning 发表于 2015-10-31 08:18. visit 1point3acres.com for more.
楼主加油
顺便问问什么叫“把所有的草除掉并回到原点.”?这题到底干啥的?
谢谢了。

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

使用道具 举报

boaever 发表于 2015-10-31 10:33:04 | 显示全部楼层
我也碰到了那个印度大叔。。。跪了。。
回复 支持 反对

使用道具 举报

 楼主| cccxfdj 发表于 2015-10-31 12:30:36 | 显示全部楼层
boaever 发表于 2015-10-31 10:33
我也碰到了那个印度大叔。。。跪了。。
-google 1point3acres
可能印度大叔就是难吧....
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-31 14:08:29 | 显示全部楼层
cccxfdj 发表于 2015-10-31 12:30
可能印度大叔就是难吧....
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最后一题我刚写了一下,100多行代码。。不过这题蛮有意思的!!
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-31 15:20:48 | 显示全部楼层

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

使用道具 举报

gorilazz 发表于 2015-10-31 15:36:22 | 显示全部楼层
marthew777 发表于 2015-10-31 15:20
python我不太熟悉,不过我觉得你的代码,无法handle一些cases,比如, 走到死胡同后,需要走visited过的一 ...

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

使用道具 举报

marthew777 发表于 2015-10-31 15:52:01 | 显示全部楼层
gorilazz 发表于 2015-10-31 15:36
我的思路是这样的:先用dfs,在访问的过程中要把路径都用stack存下来,方便backtracking。到了某个位置, ...

多谢翻译代码,我的思路和你一样。。不过这样一想,面试的时候用python简直是cheating啊。。
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-31 16:36:33 | 显示全部楼层
marthew777 发表于 2015-10-31 15:52
多谢翻译代码,我的思路和你一样。。不过这样一想,面试的时候用python简直是cheating啊。。

我平时干活都是用的c++,为了刷题专门学的python
回复 支持 反对

使用道具 举报

returning 发表于 2015-11-1 12:48:44 | 显示全部楼层
清除掉所有的草最后回到原地,要求没有格子只visit一次吗,如果是,这是欧拉回路啊,先判断是否是欧拉回路,然后欧拉回路的解法是固定的。

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

使用道具 举报

 楼主| cccxfdj 发表于 2015-11-1 14:30:03 | 显示全部楼层
marthew777 发表于 2015-10-31 14:08
最后一题我刚写了一下,100多行代码。。不过这题蛮有意思的!!

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

使用道具 举报

头像被屏蔽
feierqi 发表于 2015-11-2 04:24:52 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| cccxfdj 发表于 2015-11-2 06:58:28 | 显示全部楼层
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:55 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| cccxfdj 发表于 2015-11-2 07:09:46 | 显示全部楼层
feierqi 发表于 2015-11-2 07:01. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
额,我还是不是很明白,你是指ABC 是一个block, AABBCC是一个block这个意思吧,那么你找到第k个block, ...

3 * (2 ^ k - 1)就是求和公式. from: 1point3acres.com/bbs
表示前k个block的char 总数
找到这个k之后
你就可以从i = 3 * (2 ^ k - 1) + 1开始, 直到i == n
回复 支持 反对

使用道具 举报

头像被屏蔽
feierqi 发表于 2015-11-2 07:18:51 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-22 12:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表