车版热帖:大家对买豪车怎么看

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 2885|回复: 19
收起左侧

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

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

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

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

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

x
周二周五面完google和Amazon,发面经攒人品。
直接上题:
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。
个人感受是面的一般,估计跪了。
-google 1point3acres
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部分。. 鍥磋鎴戜滑@1point 3 acres
个人感觉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,遇到重复的删除

那请问一下如果一个char出现三次呢? 出现第二次的时候就删除了, 会不会有问题?
回复 支持 反对

使用道具 举报

 楼主| dmsehuang 发表于 2015-7-28 08:05:16 | 显示全部楼层
JohnnyHuo 发表于 2015-7-28 07:52
那请问一下如果一个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 | 显示全部楼层

其实额 感觉 用queue 可以的
就是 按顺序 放进去 计数(有个 hash什么的 指向queue 的index)

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

补充内容 (2015-8-1 06:44):. from: 1point3acres.com/bbs
当然 在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一下就好了。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-4-23 06:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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