一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1591|回复: 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

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

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

3. 中国小哥, 人很nice,看上去比我还紧张一点. 问的是给一个无穷的sequence, ABCAABBCCAAAABBBBCCCC... 每次A,B,C数量double, 然后问给一个正整数n, 求第n个char是什么.-google 1point3acres
第一个是A, 第二个是B, 以此类推...
这题一开始我就想把通项公式求出来,然后分不同的sequence做,然后一直卡在一个地方. 小哥提醒先用最简单的方法, 然后写出O(n) 算法, 之后我就知道怎么优化, 用binary search
求出最后一个k 使得 3 * (pow(2, k)) < n. visit 1point3acres.com for more.
然后从这个数字开始搜索, 这样最好的running time 是O(log(n)). visit 1point3acres.com for more.

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

总结一下: 通过并不多的面试经验, 感觉印度大叔普遍都比较严肃,而且出的题目难度比较大... 中国小哥可能看你是中国人,所以题目难度就会下来, 感谢.
最后就是,基本功得好, 尤其是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):. 鍥磋鎴戜滑@1point 3 acres
  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]
    . from: 1point3acres.com/bbs
  12.                 if self.isValid(board, n_x, n_y) and not (n_x, n_y) in visited:
  13.                     result.append(d)
    . 1point 3acres 璁哄潧
  14.                     buf.append((n_x, n_y))
  15.                     visited.add((n_x, n_y))
  16.                     flag = True
  17.                     break
  18.             if not flag:. 鍥磋鎴戜滑@1point 3 acres
  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':.1point3acres缃
  27.             return False
  28.         return True


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

评分

1

查看全部评分

求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

使用道具 举报

 楼主| cccxfdj 发表于 2015-10-31 09:59:50 | 显示全部楼层
returning 发表于 2015-10-31 08:18
楼主加油
顺便问问什么叫“把所有的草除掉并回到原点.”?这题到底干啥的?.1point3acres缃
谢谢了。
. visit 1point3acres.com for more.
就是空地表示草 需要traverse 每个有草的人pos 最后回到原地
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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

最后一题我刚写了一下,100多行代码。。不过这题蛮有意思的!!
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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. more info on 1point3acres.com
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 完直接打印相反方向就可以了...哎
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

.鐣欏璁哄潧-涓浜-涓夊垎鍦补充内容 (2015-11-2 04:25):-google 1point3acres
打错了,是如何确定不是如果确定。。。
回复 支持 反对

使用道具 举报

 楼主| cccxfdj 发表于 2015-11-2 06:58:28 | 显示全部楼层
feierqi 发表于 2015-11-2 04:24
问一下楼主第三题的binarysearch是怎么搞的,我刚才写了一下,只能loop到最后的k,然后开始找,如果按你说 ...
. 1point3acres.com/bbs
把每一次的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
找到k使得我们可以从n的那个character所在的block开始搜索, 而不是从第一 ...

额,我还是不是很明白,你是指ABC 是一个block, AABBCC是一个block这个意思吧,那么你找到第k个block,你如何知道它跟n的关系呢,前面的block有求和公式么?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| 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 总数. from: 1point3acres.com/bbs
找到这个k之后. more info on 1point3acres.com
你就可以从i = 3 * (2 ^ k - 1) + 1开始, 直到i == n
回复 支持 反对

使用道具 举报

feierqi 发表于 2015-11-2 07:18:51 | 显示全部楼层
cccxfdj 发表于 2015-11-2 07:09-google 1point3acres
3 * (2 ^ k - 1)就是求和公式
表示前k个block的char 总数
找到这个k之后
. From 1point 3acres bbs
哦哦,是的是的,果然数学还是差,这个求和公式我都忘了,多谢了楼主
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-23 23:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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