一亩三分地论坛

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

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

[找工就业] 0721 google面经&0724 amazon面经

[复制链接] |试试Instant~ |关注本帖
dmsehuang 发表于 2015-7-27 00:35:10 | 显示全部楼层 |阅读模式

2015(7-9月)-[]EE硕士+3个月-1年 - 内推| 码农类全职@Google其他

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

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

x
周二周五面完google和amazon,发面经攒人品。. 1point3acres.com/bbs
直接上题:
google onsite:
round 1: 给一个二维矩阵,每个格子填充着某一种颜色。给定起点格子,如果与之相连接的格子有相同颜色的话,就认为是一个blob,求这个blob的周长。BFS顺利答出。
round 2: 给一个binary tree,父节点和其子节点可以作差,求这个差值最大。传递父节点的最大值下去用递归解决就好,但是有一些edge case没有考虑到,在面试官的提示下才修改过来。
round 3: 写BST的iterator,leetcode原题,这一面真的面得很差,面试官都没笑过,自己也写得有bug。
round 4: database方面的设计,用户可以post message,用户可以follow别的用户,每个用户的主页就是其follow的用户post的message,有点类似于instagram。
个人感受是面的一般,估计跪了。

amazon onsite:
round 1: 给一个load balancer,怎么去handle用户对于amazon image server的30K per second的请求。第一轮就system design的确有点蒙,面得一般般。
round 2: hr面,纯粹聊project。
round 3: 给出一个string,要求找出第一个unique的character,例如abcdefabcd,应该返回e(虽然f也是唯一的,但不是第一个)。2 passes很容易做出来,用个map就好。follow up是要求1 pass做出来,使用doubly linked list + map就可以。
round 4: populate next right pointers in each node II,做过,就慢慢写代码。
round 5: merge k sorted list, LRU, quick sort的partition部分。
个人感觉amazon面得还不错,应该可以吧。

anyway,希望能够有offer。

评分

2

查看全部评分

hulahu 发表于 2015-7-27 01:00:15 | 显示全部楼层
round 3: 给出一个string,要求找出第一个unique的character,例如abcdefabcd,应该返回e(虽然f也是唯一的,但不是第一个)。2 passes很容易做出来,用个map就好。follow up是要求1 pass做出来,使用doubly linked list + map就可以。 ==》 用linkedHashMap ? 因为它是有续的。
回复 支持 反对

使用道具 举报

 楼主| dmsehuang 发表于 2015-7-27 02:25:38 来自手机 | 显示全部楼层
用linkedlistmap应该也可以,但我不是很熟悉。反正就是遇到新的char就append到list的tail,遇到重复的删除
回复 支持 反对

使用道具 举报

xiaoc10 发表于 2015-7-28 07:36:45 | 显示全部楼层
占个坑。待会再来看。
回复 支持 反对

使用道具 举报

JohnnyHuo 发表于 2015-7-28 07:52:37 | 显示全部楼层
dmsehuang 发表于 2015-7-27 02:25
用linkedlistmap应该也可以,但我不是很熟悉。反正就是遇到新的char就append到list的tail,遇到重复的删除
. from: 1point3acres.com/bbs
那请问一下如果一个char出现三次呢? 出现第二次的时候就删除了, 会不会有问题?
回复 支持 反对

使用道具 举报

 楼主| dmsehuang 发表于 2015-7-28 08:05:16 | 显示全部楼层
JohnnyHuo 发表于 2015-7-28 07:52. more info on 1point3acres.com
那请问一下如果一个char出现三次呢? 出现第二次的时候就删除了, 会不会有问题?

当时和面试官讨论过,如果map的value允许null,第二次出现的时候就只把value改为null而不是从map里面删除,也就是就用null表示曾经出现,但是已经删除了。如果不允许使用null去标记的话,还得加个set去判断哪些character曾经出现过并且已经删除了。
回复 支持 反对

使用道具 举报

zhangpaopao 发表于 2015-8-1 02:05:34 | 显示全部楼层
请问楼主, amazon round 3, 可以直接用queue吗? double linked list 的优势在哪里呢?
回复 支持 反对

使用道具 举报

zhangpaopao 发表于 2015-8-1 02:06:11 | 显示全部楼层
请问楼主, amazon round 3, 可以直接用queue吗? double linked list 的优势在哪里呢?
回复 支持 反对

使用道具 举报

 楼主| dmsehuang 发表于 2015-8-1 04:26:06 | 显示全部楼层
zhangpaopao 发表于 2015-8-1 02:06
请问楼主, amazon round 3, 可以直接用queue吗? double linked list 的优势在哪里呢?

用queue的话删除就不是o(1)了,用doubly linked list和map相结合删除可以是o(1)。
回复 支持 反对

使用道具 举报

chuxidemeng 发表于 2015-8-1 04:35:27 | 显示全部楼层
LZ是new grad吗?是OA完onsite?谢谢LZ
回复 支持 反对

使用道具 举报

 楼主| dmsehuang 发表于 2015-8-1 05:20:45 | 显示全部楼层
chuxidemeng 发表于 2015-8-1 04:35
LZ是new grad吗?是OA完onsite?谢谢LZ

没,已经工作一年了,这次是跳槽。
回复 支持 反对

使用道具 举报

zhangpaopao 发表于 2015-8-1 06:15:18 | 显示全部楼层
dmsehuang 发表于 2015-8-1 04:26
用queue的话删除就不是o(1)了,用doubly linked list和map相结合删除可以是o(1)。

谢谢楼主!
回复 支持 反对

使用道具 举报

larry_cn 发表于 2015-8-1 06:43:29 | 显示全部楼层
. more info on 1point3acres.com
其实额 感觉 用queue 可以的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
就是 按顺序 放进去 计数(有个 hash什么的 指向queue 的index)

最后 queue pop 到只有 一个是 count是1 就可以了  

补充内容 (2015-8-1 06:44):
当然 在queue 里每个 字符最多只能 出现一次
回复 支持 反对

使用道具 举报

@南岸的风 发表于 2015-8-3 01:38:15 | 显示全部楼层
请问楼主Google round2 如果input 是null 或者只有一个node,应该返回什么呢?多谢!
回复 支持 反对

使用道具 举报

 楼主| dmsehuang 发表于 2015-8-3 03:25:21 | 显示全部楼层
@南岸的风 发表于 2015-8-3 01:38
请问楼主Google round2 如果input 是null 或者只有一个node,应该返回什么呢?多谢!

我直接说throw exception。
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-8-27 03:41:56 | 显示全部楼层
LZ能具体说说amazon round1 system design你是怎么答的吗
回复 支持 反对

使用道具 举报

ohshire 发表于 2015-8-27 04:16:56 | 显示全部楼层
楼主能不能讲讲G家round1那题,周长是怎么求的?感觉格子数量和面积很好求,但周长的话,如果blob是不规则图形咋办?
回复 支持 反对

使用道具 举报

 楼主| dmsehuang 发表于 2015-8-27 13:07:42 | 显示全部楼层
ohshire 发表于 2015-8-27 04:16
楼主能不能讲讲G家round1那题,周长是怎么求的?感觉格子数量和面积很好求,但周长的话,如果blob是不规则 ...

假设已经计算好的周长是L,然后发现一个新的相连的格子,计算和原本的L的接触的边,假设接触的边有K条,那么新的周长就是L+4-K。反正BFS一下就好了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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