一亩三分地论坛

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

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

Google LA onsite 面筋

[复制链接] |试试Instant~ |关注本帖
mc422 发表于 2016-11-23 16:24:00 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
上周五在Google LA office 面的。可能不太有太多同学去 LA office onsite。还是分享出来大家看看吧
1. 不记得太多了,有一道 Leetcode 17。
. visit 1point3acres.com for more.
2. 开放性题目。面试官在黑板上画了一个迷宫,用bar做边界和隔板。有隔板的地方不能通过,从一个方向走只有碰到隔板和边界才会停下来。让设计一个算法找出起始点到终点的path。上来先说用什么来数据结构来保存迷宫信息,我说用hashtable,面试官说OK。之后我说这题需要用DFS来求解,面试官问用什么方法,说了半天才知道他想问我可以把迷宫当成graph。让后把example化成了graph的形式,让我写了dfs的算法。之后有讨论了DFS和BFS在这个问题上的优缺点,我说DFS找一条路径较快,他不认同。这轮总体答的优点僵。

3. 设计一个class,用array来保存整数。比如1829保存为[1, 8, 2, 9 ], 再写一个increment 的方法,往里面加数字。第二题让我写 一个 2D matrix, reverse each row。

4. 设计一系列函数(is_used(), set_used(), release_used(), next_available()),用来保存所有被占用的电话号码。我说用hashset保存占用的号码。面试官说ok,Follow up:找next_available需要 o(N), 如何improve。我说可以设计把所有号码段分成K个区域,用一个array来存已经使用的号码个数,这样在找next available时一个先找一个没用完的区域,在往里找,达到O(N/K), 如果每个号码区域再向下分sub 区域,最终能达到 O(nlogn), 面试官说可以。Follow up 说如果希望next_available达到O(1),   需要怎么做。一开始说用两个hashset分别存 used and unused 号码,但被面试官点破说hashset找任意element也需要O(N). 说可以用hashtable 加 linkedlist的数据结构,面试官说可以。之后说还有10分钟,让我写了leetcode 的spiral matrix,10分钟内写完

5. Find relative in archive. 给你一系列child -> parents 关系的dict (A - > (mother1, father1), B -> (mother2, father2), mother2 -> (mother3, father3)),写一个method,决定两个人是否有关系relative。先问我什么数据结构,我说用tree,面试官说可以,我画图设计时发现不行(两个node一个有相同的child),说该用graph,面试官说可以。之后写了个DFS的算法找各自的ancestry,让后比较。写完后面试官问可以怎么改进,我说可以用BFS同时search两个人,让后再每一轮BFS时比较,面试官说可以,写了代码。

总体来说LA office的面试还属于比较简单的,没太多难题,主要在于和面试官交流。LA office虽然比MTV比小不小,但离Santa Monica沙滩很近(据说就两条街),大约7動office,基本设施gym也都有。准备面试时基本靠地里涮面积,现在也来出份力。希望自己能拿到offer,地里朋友也加油。

本帖被以下淘专辑推荐:

stevelee1012 发表于 2016-11-23 16:37:43 | 显示全部楼层
第二題基本上是edge length 為1的graph. Shortest path 經典解法是bfs
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-24 08:10:24 | 显示全部楼层
第四题 可以hashtable加queue 第五题 直接union find   dfs bfs 你这样做太复杂
回复 支持 反对

使用道具 举报

chengbaokun 发表于 2016-11-24 09:54:33 | 显示全部楼层
请问下LZ关于第五题,LZ的做法是对两个点分别做搜索,然后得到两堆node,然后比较着两堆node有没有重复的吗?
回复 支持 反对

使用道具 举报

laiguojiuhao 发表于 2016-11-28 06:19:04 | 显示全部楼层
zyoppy008 发表于 2016-11-24 08:10
第四题 可以hashtable加queue 第五题 直接union find   dfs bfs 你这样做太复杂
. visit 1point3acres.com for more.
请问一下Union-find 为什么会更简单呢?也是level up的找吧应该
回复 支持 反对

使用道具 举报

stevelee1012 发表于 2016-11-28 07:47:05 | 显示全部楼层
Union find 快不少
回复 支持 反对

使用道具 举报

xiangjn_alex 发表于 2016-11-28 11:19:30 | 显示全部楼层

求问大神 如何用union find 来做呀
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-28 13:15:06 | 显示全部楼层
xiangjn_alex 发表于 2016-11-28 11:19
求问大神 如何用union find 来做呀
. Waral 鍗氬鏈夋洿澶氭枃绔,
同问。
觉得LZ的解法是很直接的想法
回复 支持 反对

使用道具 举报

 楼主| mc422 发表于 2016-11-29 02:45:50 | 显示全部楼层
chengbaokun 发表于 2016-11-24 09:54
请问下LZ关于第五题,LZ的做法是对两个点分别做搜索,然后得到两堆node,然后比较着两堆node有没有重复的吗 ...

对,基本就是这个解法
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 04:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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