一亩三分地论坛

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

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

Google NYC Onsite

[复制链接] |试试Instant~ |关注本帖
wy193777 发表于 2016-1-29 06:58:38 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - Other - Onsite |Failfresh grad应届毕业生

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

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

x
1.        给两个html解析成的树,比较其中的字符串是否相等。
比如<div>Hello World!</div>和<div>Hello <span>World</span>!</div>都包含完整的”Hello World!”, 所以返回True.. from: 1point3acres.com/bbs
假设parser会返回一棵树,先是设计返回的树节点类。然后实现如何比较。
我设计的类里面包含一个tag,记录当前节点的tag,另外一个是list,里面的元素可能是tag下的string,比如Hello,也可能是指向子节点的指针。所以<div>Hello <span>World</span>!</div>会被表示成:

                               
登录/注册后可看大图

. 鍥磋鎴戜滑@1point 3 acres
. visit 1point3acres.com for more.
我说可以分别遍历树,然后拼接字符串,再比较结果。写了个递归版本以后,问我这么写在实际使用时会有啥问题。
我说网页可能很大,会run out of stack或者run out of memory. 接着说可以用迭代器来逐个返回字符串,逐个比较,不需要复制字符串。
然后就让我写个迭代器。. from: 1point3acres.com/bbs
然后我就脑子糊了,不知道怎么不递归遍历树。一直觉得用stack不对,到我写这篇面经的时候才想明白。
总之迭代器还没写完,就结束了。


2.        第二轮,亚裔面试官题目是给一个单淘汰赛的初始对阵,一个每个队对每个队的胜率矩阵,写一个函数,能返回一个特定队伍拿冠军的几率。完全不会,面试官提示了我45分钟也没写出什么代码。.鐣欏璁哄潧-涓浜-涓夊垎鍦
3.        吃饭环节,一个工作了两年半的白人小哥。Google的食堂确实不错。
4.        这一轮是个亚洲小哥,我怀疑是中国人,考的比较简单。第一题,给一个函数String calc(String left, String operator, String right),left和right是类是“1”,“123”这样的字符串,operator是四则运算符,返回结果也被转换成字符串形式。让设计写测试输入。开脑洞想了各种case,比如一个数溢出,两个数加起来溢出,除零,以及类似“3e10”,“8.5”这样的非整数。还有“00003”这样的等等。
第二题是给两个数组,返回两个数组,第一个是只在数组一里面出现的数组,第二个是只在数组二里面出现的的数组。我说可以用frequency table,也可以排好序,然后指针比较。让我写了排好序指针比较的版本。-google 1point3acres
第三题是输出一个数组里面最长的连续增子串的长度比如[4, 1, 2, 3, 4, 6],返回就是4,因为1,2,3,4是连续的四个数字。
然后就完事儿了。
5.        最后一轮,给一个甲字形的手机数字键盘,给一个初始格子,给一个步数,然后返回最终可能在的格子有哪些。写了个DFS的版本,因为甲字形键盘然后问我复杂度。脑残,明明是3^n,我非说是n^3。最后在提示下才说对。之后问我如何优化,比如路径重复什么的。我说超过一定步数以后就没有新的路径或者终点了,所以最终是constant复杂度。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
总体来说只有第二题很难,其他的大致都做出来点,不过都不完美。十之八九过不了。
面经奉上。各位还没面的同学加油。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

农大晏如君 发表于 2016-1-31 00:00:10 | 显示全部楼层
撸主不要担心,offer正在路上!
回复 支持 反对

使用道具 举报

 楼主| wy193777 发表于 2016-1-31 11:17:22 | 显示全部楼层
想了一下第二题,写出了代码。大概思路是递归。每层递归将当前所有对阵分成左半区和右半区。对于需要胜出的队伍所在的区,返回该只队伍所在区胜出的概率。对于需要胜出的队伍不在的区,返回该区每只队伍在该区胜出的概率。然后以当前需要胜出的队伍胜出的概率分别乘以另外半区每只队伍胜出的概率和这支队对另外半区每只队赢的胜率。
  1. def single_elimination(poss, matches, num):. 鍥磋鎴戜滑@1point 3 acres
  2.     if len(matches) == 2:  # base case
  3.         if num == matches[0]:
  4.             return poss[matches[0]][matches[1]]
  5.         else:
  6.             return poss[matches[1]][matches[0]]
  7.     half = len(matches)/2
  8.     east = matches[:half] if num in matches[:half] else matches[half:]
  9.     west = matches[half:] if num not in matches[half:] else matches[:half]

  10.     # for the half that contains wanted team.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     main = single_elimination(poss, east, num)
  12.     # for the half that doesn't contains wanted team
  13.     sub = [single_elimination(poss, west, team) for team in west]
    .1point3acres缃
  14. . From 1point 3acres bbs
  15.     return sum([p * main * poss[num][t] for p, t in zip(sub, west)]). 鍥磋鎴戜滑@1point 3 acres

  16. matrix2 = [
  17.     [0.0, 0.9],. more info on 1point3acres.com
  18.     [0.1, 0.0]
  19. ]

  20. matches2 = [0, 1]. visit 1point3acres.com for more.

  21. matrix4 = [
  22.     [0.0, 0.1, 0.2, 0.3],
  23.     [0.9, 0.0, 0.4, 0.5],.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.     [0.8, 0.6, 0.0, 0.6],
  25.     [0.7, 0.5, 0.4, 0.0]
  26. ]

  27. matches4 = [0, 1, 2, 3, ]
  28. print(single_elimination(matrix2, matches2, 0))
  29. print(single_elimination(matrix2, matches2, 1))

  30. . from: 1point3acres.com/bbs
  31. print(single_elimination(matrix4, matches4, 0))
  32. print(single_elimination(matrix4, matches4, 1))
  33. print(single_elimination(matrix4, matches4, 2))
  34. print(single_elimination(matrix4, matches4, 3))
复制代码


考虑到想明白了这题其实也不难,我觉得我可以安心把到手的offer接了。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-5 06:18:38 | 显示全部楼层
问下楼主在amazon实习完然后去哪里了?
回复 支持 反对

使用道具 举报

 楼主| wy193777 发表于 2016-5-5 06:26:31 来自手机 | 显示全部楼层
最后拿到了NVIDIA的offer。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 03:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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