一亩三分地论坛

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

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

Google,Snapchat面经

[复制链接] |试试Instant~ |关注本帖
luangthu 发表于 2016-10-20 02:44:46 | 显示全部楼层 |阅读模式

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

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

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

x
Google:第一轮onsite 2面:
1. 给定一个数轴[0,100],实现两个API:
void drop(int start, int width): 在[start,start+width]区域内放置一个正方形
int height(int pos):返回当前pos的高度. 1point 3acres 璁哄潧

这里后放的正方形会落在之前的正方形上(如果有overlap的话),和俄罗斯方块差不多。

Followup:1.如果数轴无限长怎么办 2.如果start, pos可以是float怎么办
2. 给定两个长度一样的数字list A B,每个list都没有重复元素。判断他们是否满足如下性质:
对任意的 0<=i,j < len(A), (A[i]-A[j]) * (B[i]-B[j]) > 0

第二轮onsite 2面:
1. a.longest consecutive path in DAG b.mean of array with min&max value removed (貌似都是面经题,不赘述了)
2. 判断一个树是不是另一个树的子树 Followup: optimize

Snapchat:
1. Machine learning:discriminative model vs generative model Coding:二维平面上判断两个矩形是否overlap(需要自己定义矩形和怎么算是overlap,corner case比较繁琐)
2. Given a stream of integers, implement these API
int check(int val): return number of numbers seen before that are less or equal to val
3. 非常普通的走迷宫题。之后让我帮他玩一个网上的regex challenge, 还是javascript...
4. XML parsing.面经题. given api nextToken()

之前准备时候看了不少面经,现正好回馈一下大家,顺便求一些积分。希望可以帮助到正在准备面试的朋友们。
GLHF

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

7

查看全部评分

本帖被以下淘专辑推荐:

cty 发表于 2016-10-20 03:53:48 | 显示全部楼层
想问下楼主判断一棵tree是不是另一棵tree的subtree是怎么做的呀?我能想到的是先serialize tree然后再看结果是否包含关系,不知道有没有更好的办法?
回复 支持 反对

使用道具 举报

1451427216 发表于 2016-10-20 04:00:59 | 显示全部楼层
cty 发表于 2016-10-20 03:53. Waral 鍗氬鏈夋洿澶氭枃绔,
想问下楼主判断一棵tree是不是另一棵tree的subtree是怎么做的呀?我能想到的是先serialize tree然后再看结 ...

可以判断两棵树是不是一样,如果不一样再分别判断左子树和又子树是不是和树identical。recrusive下去
回复 支持 反对

使用道具 举报

1370786136.1.3 发表于 2016-10-20 04:06:15 | 显示全部楼层
请问第一题中, 没有overlapped的部分会自动掉落么?
回复 支持 反对

使用道具 举报

cty 发表于 2016-10-20 04:38:24 | 显示全部楼层
1451427216 发表于 2016-10-20 04:00. Waral 鍗氬鏈夋洿澶氭枃绔,
可以判断两棵树是不是一样,如果不一样再分别判断左子树和又子树是不是和树identical。recrusive下去

that works, 但是在worst case里会比较慢,比如input的小tree的所有node都是同一个值,还可以优化吗?
回复 支持 反对

使用道具 举报

 楼主| luangthu 发表于 2016-10-20 06:03:19 | 显示全部楼层
cty 发表于 2016-10-20 04:38
that works, 但是在worst case里会比较慢,比如input的小tree的所有node都是同一个值,还可以优化吗?

当时面试官是用他这个思路引导我的。最后他说如果一个tree有1M个node,另一个只有四个,这样的话可以怎么优化么?我的说法是每个节点存一下该节点对应的subtree的节点个数。他觉得OK。
回复 支持 反对

使用道具 举报

 楼主| luangthu 发表于 2016-10-20 06:03:57 | 显示全部楼层
1370786136.1.3 发表于 2016-10-20 04:06
请问第一题中, 没有overlapped的部分会自动掉落么?

不会的。和俄罗斯方块一样。
回复 支持 反对

使用道具 举报

1peter 发表于 2016-10-20 06:41:50 | 显示全部楼层
cty 发表于 2016-10-20 04:38
that works, 但是在worst case里会比较慢,比如input的小tree的所有node都是同一个值,还可以优化吗?

如果题目没有给任何前提条件,不断地recrusion应该是唯一的办法。所以我很好奇lz所说的optimization的限定条件是什么
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-10-20 06:50:52 | 显示全部楼层
1peter 发表于 2016-10-20 06:41
如果题目没有给任何前提条件,不断地recrusion应该是唯一的办法。所以我很好奇lz所说的optimization的限 ...

可以先把两个树的深度算出来。这样能知道小tree 如果在大tree里的话,根结点在大tree第几层
然后只要遍历那一层的结点,对每个结点检查下面的子树是不是等于小tree就好

时间上不多于扫两遍大tree+扫一遍小tree
回复 支持 反对

使用道具 举报

cty 发表于 2016-10-20 07:04:40 | 显示全部楼层
1peter 发表于 2016-10-20 06:41
如果题目没有给任何前提条件,不断地recrusion应该是唯一的办法。所以我很好奇lz所说的optimization的限 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
brute force recursion是O(mn)的,tree serialization只要O(m + n), geeksforgeeks
回复 支持 反对

使用道具 举报

cty 发表于 2016-10-20 07:10:45 | 显示全部楼层
luangthu 发表于 2016-10-20 06:03
当时面试官是用他这个思路引导我的。最后他说如果一个tree有1M个node,另一个只有四个,这样的话可以怎么 ...

嗯啊,这么做就优化到linear了,祝楼主早日收到这两家的offer!
回复 支持 反对

使用道具 举报

cty 发表于 2016-10-20 07:13:34 | 显示全部楼层
楼主知道目前snapchat new grad的headcount情况吗?我还在跟hr约onsite时间,想推晚一点不知道行不行
回复 支持 反对

使用道具 举报

1peter 发表于 2016-10-20 08:40:41 | 显示全部楼层
cty 发表于 2016-10-20 07:04
brute force recursion是O(mn)的,tree serialization只要O(m + n), geeksforgeeks
. from: 1point3acres.com/bbs
那个我看了,在不加任何前提的条件下我认为是错误的,
      4
  1      2
2  3   3  1

     1
  2
3-google 1point3acres

如果你写出两个的inorder 和preorder可以看到第二棵树的array都在第一棵树中,但第二棵树显然不是subtree of 第一棵树。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
correct me if I'm wrong.
回复 支持 反对

使用道具 举报

samuelling 发表于 2016-10-20 08:52:11 | 显示全部楼层
1peter 发表于 2016-10-19 16:40
那个我看了,在不加任何前提的条件下我认为是错误的,
      4
  1      2
. from: 1point3acres.com/bbs
那个办法太麻烦,实际情况是只需要对tree进行一个preorder/inorder/postorder就可以了。只不过这里你要记录下null节点,因为3, null, 4和3, 4, null表示的不是一个子树。说白了就是serialize binary tree。
回复 支持 反对

使用道具 举报

木易wen 发表于 2016-10-20 09:28:44 | 显示全部楼层
请问lz第一题follow up怎么做的?我想用interval但感觉实现起来有点麻烦
回复 支持 反对

使用道具 举报

cty 发表于 2016-10-20 09:52:02 | 显示全部楼层
1peter 发表于 2016-10-20 08:40. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
那个我看了,在不加任何前提的条件下我认为是错误的,
      4-google 1point3acres
  1      2

你是对的,貌似是没有duplicates的情况下才能geeksforgeeks上那么做?

Thanks for pointing that out!
回复 支持 反对

使用道具 举报

1peter 发表于 2016-10-20 10:14:39 | 显示全部楼层
cty 发表于 2016-10-20 09:52
你是对的,貌似是没有duplicates的情况下才能geeksforgeeks上那么做?

Thanks for pointing that out!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
其实链接里也说了,即使没有duplicate这样也这能找出t 是不是另一个树的一部分,不能保证是子树。geeksforgeeks 的文章里就有例子
回复 支持 反对

使用道具 举报

zmz0305 发表于 2016-10-20 10:26:11 | 显示全部楼层
同问LZ, 第一题掉正方形的follow up怎么做的?
回复 支持 反对

使用道具 举报

 楼主| luangthu 发表于 2016-10-21 04:49:30 | 显示全部楼层
木易wen 发表于 2016-10-20 09:28
请问lz第一题follow up怎么做的?我想用interval但感觉实现起来有点麻烦

我当时也是说的interval,最后时间不是很够了他只让我说了一下思路,并没有实现。
回复 支持 反对

使用道具 举报

 楼主| luangthu 发表于 2016-10-21 04:50:06 | 显示全部楼层
zmz0305 发表于 2016-10-20 10:26
同问LZ, 第一题掉正方形的follow up怎么做的?
. 鍥磋鎴戜滑@1point 3 acres
同楼上。我当时说用interval来表示吧,最后时间不是很够了他只让我说了一下思路,并没有实现。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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