一亩三分地论坛

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

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

7/13 Google NY onsite 面经

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

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

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

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

x
面的是NY office, 跟大家一样,一共5轮,每轮一个面试官,基本就一个题 (可能是因为做的太慢了)
. 鍥磋鎴戜滑@1point 3 acres
1. 亚裔女生,好像是怀孕了,phd毕业。 让设计一个电梯系统。她说不是特别看重语法细节,主要还是看设计。

2. 白人大叔。 给一个RangeSet, 每一个元素都是一个interval。让你实现 addOneInterval(double upperBound, double) 和 findInterval(double n)。让平衡两个method的复杂度

3. 中国大叔。compress string和uncompress string。 比如说 aaaababa可以压缩成4[a]2[ba], 也可以是3[a]2[ab]a. 找最优压缩办法

4. 中国大叔。给一堆点,找central point. 但是我没明白是什么意思,好像是个固定算法。然后就简化成一个matrix, 里面有1和0, 找到所有点中找出中心点,这个中心点距离所有1的距离总和最小。后来又在matrix加了2,这个点是障碍不能经过
. more info on 1point3acres.com
5. 白人大叔。给一个BST和一个value, 根据value将这个BST分成两个BST

总体觉得题不算是特别奇怪特别难,可惜也没怎么准备好,都不是太会做。我感觉所有面试官人都很好,愿意交流并且指出问题。做compress string那个中国大叔,给我提示到就差说出答案了,结果我还是不会做==! 还是要继续努力才行。-google 1point3acres

还要感谢地里的面经,特别管用!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
祝大家都能拿到心怡的offer!


评分

1

查看全部评分

本帖被以下淘专辑推荐:

hxtang 发表于 2016-7-16 20:49:27 | 显示全部楼层
1 好像是经典设计题。. Waral 鍗氬鏈夋洿澶氭枃绔,
2 findInterval的意思是找所有包含double n的interval吗?听起来像是segment tree. 不过只写过int的不确定double的能不能做。还有一个比较容易但是效率也许低一点的方法是用map(或者别的平衡BST)存Interval,按Interval的左端点排,然后log时间得到lower_bound(value)之后一个个检查value是否在Interval里,直到Interval左端点>value。
3 uncompress string应该就是递归uncompress[]里的东西吧。compress感觉可能可以动态规划找到所有可以压缩的子串的最优压缩,然后递归找整个子串的最优拆分 大叔提示了什么吗? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
4 好像是leetcode原题 Best Meeting Point I/II. 第一问就是找所有1 x和y位置的中位数,第二问就是BFS.
5 似乎就是把到value的路径的结点区分为属于输出的哪个BST,然后插入左半边BST(<value)上一个结点的右结点,或右半边BST(>value)上一个结点的左结点。
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-16 21:27:58 | 显示全部楼层
4的大叔放水吧...给一堆点, 找重点, 不就是把x,y分别加起来 然后除以个数么...
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-16 21:31:39 | 显示全部楼层
2的话, 用hashheap, find是1, add是lgn
回复 支持 反对

使用道具 举报

poligun 发表于 2016-7-17 00:11:00 | 显示全部楼层
hxtang 发表于 2016-7-16 20:49
1 好像是经典设计题。
2 findInterval的意思是找所有包含double n的interval吗?听起来像是segment tree.  ...

2 的话 addInterval 要考虑新加的 Interval 是不是会与原有的 Intervals 相交。如果有相交的话, set 用 lower_bound 求出来插入位置后,还有与该位置前后的的 Intervals 判断是否相交,相交就合并。所以最坏的时间复杂度是 O(N), N 是 Intervals 个数…… 这里用 Segment Tree 感觉就好一些,(可以 argue 说只 new 新节点不释放删除的节点,等程序结束后统一释放……有点扯)
-google 1point3acres
3 貌似是 G 家老题目了。

4 就是 LC 296 和 317 了挺经典的。

5 的话其实不需要重新 build 两棵 BST。根据 Target Node 是 Parent 的左儿子还是右儿子,交替使用 Left Rotation 和 Right Rotation 把它旋转到根部,返回左右子树就行。查找+沿着 path 旋转都是 O(logn) 的复杂度。


回复 支持 反对

使用道具 举报

sophiehu 发表于 2016-7-17 00:11:32 | 显示全部楼层
谢谢楼主的热心分享
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-17 14:26:56 | 显示全部楼层
poligun 发表于 2016-7-17 00:11
2 的话 addInterval 要考虑新加的 Interval 是不是会与原有的 Intervals 相交。如果有相交的话, set 用  ...


能分享compress的解法呢 ? 看了多次没想到好的方法?
回复 支持 反对

使用道具 举报

aangel 发表于 2016-7-17 22:32:15 | 显示全部楼层
poligun 发表于 2016-7-17 00:11
2 的话 addInterval 要考虑新加的 Interval 是不是会与原有的 Intervals 相交。如果有相交的话, set 用  ...

你说的5能给出部分代码吗?尤其是left rotate和right rotate部分(貌似属于红黑树?)
回复 支持 反对

使用道具 举报

poligun 发表于 2016-7-18 04:40:02 | 显示全部楼层
aangel 发表于 2016-7-17 22:32
你说的5能给出部分代码吗?尤其是left rotate和right rotate部分(貌似属于红黑树?)

节点的左旋和右旋操作的特点是不改变节点间的 predecessor / successor 关系,原本是用于保持树的平衡,跟哪种树的类型无关(红黑、AVL 和 Treap 都可以用到)。BST 删除节点的时候,可以把这个节点旋转成叶子然后删掉,当然也有比较偷懒的方法就是找这个节点的 predecessor / successor (必然是叶子)删掉。
回复 支持 反对

使用道具 举报

poligun 发表于 2016-7-18 04:45:43 | 显示全部楼层
aangel 发表于 2016-7-17 22:32. more info on 1point3acres.com
你说的5能给出部分代码吗?尤其是left rotate和right rotate部分(貌似属于红黑树?)

好像 Wiki 的红黑树词条里就有一张比较形象的左旋右旋图。因为算法导论里讲了红黑,所以很多人比较熟悉一些……不过老一批搞竞赛的那帮然还是喜欢默写 AVL 树
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-7-18 11:45:50 | 显示全部楼层
第三轮怎么解呢?
回复 支持 反对

使用道具 举报

woshiee123 发表于 2016-7-21 07:22:04 | 显示全部楼层
hxtang 发表于 2016-7-16 20:49. 鍥磋鎴戜滑@1point 3 acres
1 好像是经典设计题。
2 findInterval的意思是找所有包含double n的interval吗?听起来像是segment tree.  ...

你好  请问第一题应该怎么做呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 00:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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