一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1544|回复: 19
收起左侧

Google MTV 10/30 new grad onsite interview

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

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

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

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

x
. visit 1point3acres.com for more.
直接上题
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, 以此类推.... 1point 3acres 璁哄潧
这题一开始我就想把通项公式求出来,然后分不同的sequence做,然后一直卡在一个地方. 小哥提醒先用最简单的方法, 然后写出O(n) 算法, 之后我就知道怎么优化, 用binary search
求出最后一个k 使得 3 * (pow(2, k)) < n
然后从这个数字开始搜索, 这样最好的running time 是O(log(n)). From 1point 3acres bbs

4. 印度大叔, 今天就跪在这里了... 首先人比较死板,然后态度很严肃.
之后, 直接开始做题,和前面不同的是, 题目直接写纸上. 第一题是分析一串代码, 问这代码是干嘛的,然后可能有什么问题.... 规定的是10分钟, 然后我大概超时了,而且最后也没看出来seg fault在哪. 这个真是基本功问题了可能
然后出了道题, 一个2d array of char, 'X'表示不能走, " "表示草地, 给一个初始x,y 然后把所有的草除掉并回到原点. 要求的是,每走一步打印一个方向, 最后打印出所有的方向... 想到了是dfs, 但是卡在往回走的过程了... 最后没写出全部的代码, 还被大叔嘲讽了.. 其实并不太难, dfs 可以解决. 主要是题目略长,然后时间比较不够了, 这种题套模板会比较快.

总结一下: 通过并不多的面试经验, 感觉印度大叔普遍都比较严肃,而且出的题目难度比较大... 中国小哥可能看你是中国人,所以题目难度就会下来, 感谢.
最后就是,基本功得好, 尤其是debug的能力, 有时候不仅仅是做算法题, 还得会分析代码.... From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres
最后希望努力的人都有好的回报!

评分

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缃
  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. more info on 1point3acres.com
  17.                     break. 鍥磋鎴戜滑@1point 3 acres
  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.         return result

  23.     def isValid(self, board, x, y):
  24.         if x<0 or x>=len(board) or y<0 or y>=len(board[0]):
  25.             return False
  26.         if board[x][y]=='x':
  27.             return False. From 1point 3acres bbs
  28.         return True 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


  29. sol = Solution()
  30. result = sol.printPath(["x  x", "xx  ", "x   ", "    "], 0, 1). 鍥磋鎴戜滑@1point 3 acres
  31. 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
楼主加油
顺便问问什么叫“把所有的草除掉并回到原点.”?这题到底干啥的?
谢谢了。

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

使用道具 举报

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

使用道具 举报

 楼主| cccxfdj 发表于 2015-10-31 12:30:36 | 显示全部楼层
boaever 发表于 2015-10-31 10:33. From 1point 3acres bbs
我也碰到了那个印度大叔。。。跪了。。

可能印度大叔就是难吧....
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-31 14:08:29 | 显示全部楼层
cccxfdj 发表于 2015-10-31 12:30. more info on 1point3acres.com
可能印度大叔就是难吧....

最后一题我刚写了一下,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多行代码。。不过这题蛮有意思的!!
-google 1point3acres
其实这题模板是subsets类似, 不清楚要不要这么多行. 就是recursion后, 再打印出相反方向即可, 这样就表示回头了.
我当时面的时候一直在纠结怎么回头, 其实recursion 完直接打印相反方向就可以了...哎
回复 支持 反对

使用道具 举报

feierqi 发表于 2015-11-2 04:24:52 | 显示全部楼层
问一下楼主第三题的binarysearch是怎么搞的,我刚才写了一下,只能loop到最后的k,然后开始找,如果按你说的binary search找3 * (pow(2, k)) < n,那你就算找到了k,如果确定现在是第几位呢?这个不是等比数列,没有求和公式吧?还是我理解错了,谢谢lz指教

补充内容 (2015-11-2 04:25):
打错了,是如何确定不是如果确定。。。
回复 支持 反对

使用道具 举报

 楼主| cccxfdj 发表于 2015-11-2 06:58:28 | 显示全部楼层
feierqi 发表于 2015-11-2 04:24
问一下楼主第三题的binarysearch是怎么搞的,我刚才写了一下,只能loop到最后的k,然后开始找,如果按你说 ...
. 鍥磋鎴戜滑@1point 3 acres
把每一次的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 06:58. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
把每一次的A,B,C看成一个block.1point3acres缃
找到k使得我们可以从n的那个character所在的block开始搜索, 而不是从第一 ...

额,我还是不是很明白,你是指ABC 是一个block, AABBCC是一个block这个意思吧,那么你找到第k个block,你如何知道它跟n的关系呢,前面的block有求和公式么?
回复 支持 反对

使用道具 举报

 楼主| cccxfdj 发表于 2015-11-2 07:09:46 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

feierqi 发表于 2015-11-2 07:18:51 | 显示全部楼层
cccxfdj 发表于 2015-11-2 07:09
3 * (2 ^ k - 1)就是求和公式
表示前k个block的char 总数. from: 1point3acres.com/bbs
找到这个k之后

哦哦,是的是的,果然数学还是差,这个求和公式我都忘了,多谢了楼主
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 22:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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