一亩三分地论坛

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

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

Google 加面(1.19)跪经

[复制链接] |试试Instant~ |关注本帖
ginues109 发表于 2016-2-13 07:05:21 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
等到了拒信悲伤地发面经……. 1point 3acres 璁哄潧
第一轮在1.5, 两人背靠背在。
第一人是三姐,很nice:
1.给两个list A和B,找出所有出现在list A,同时不出现在list B里的元素,包括重复元素。
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 2.Leetcode原题:Missing Ranges. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3.有一排停车位,只有一个empty slot,其他车位都停满了车。每一次操作,只能将某一辆
从原车位停到那个empty slot。显然每一次操作后empty slot位置就变了。
问:给定一个初始排列,以及最终排列,输出从初始到最终排列所需要的每一步step。(step i: car j move to empty slot)
第三题想到一半没时间了。没做出来

第二人是白人,就问了一道题:. 1point3acres.com/bbs
1. floodfill,给一个2维矩阵,里面每一个int代表了那个坐标位置的海拔,然后给一个水平面高度,当水平面
高度>=海拔高度的时候算作那个地方被水淹没(flooded)。现在有一艘船只能走被水淹没的地方。
问:给定一个海拔矩阵,和一个水平面高度,求船从矩阵左上角划到右下角的path。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
做这道题我全程懵逼啊T T,一乱全乱了,一个dfs递归都写不好了T T,面试官不停的no no no加叹气。
我以为跪定了。

一周后通知加面,非常开心,有戏。因为有小伙伴说加面面好通过概率就大了。
第三个人是一个白人:
1. Leetcode原题:Compare version number
2. 设计一个数据结构,实现两个操作:
insert() //插入一个元素,type就当做是int吧
returnRandom() //随机返回数据结构里的一个元素,要求每次调用时每个元素被返回的概率相同。-google 1point3acres
第二题的follow up:
实现第三个操作:
remove() //删除一个元素,并保持以上两个操作功能不变。

folloup 没想到什么好方法,我觉得他应该是需要三个操作都是O(1)才对。
最后remove还是保留了O(n)的方法时间就到了。

自认为整体还行。等了两周催了一下催来拒信T T,还专门打电话过来人工拒T T。我还是太拿衣服了。
回馈地里,祝各位拿到梦想offer T T!!

评分

3

查看全部评分

hutiankuo 发表于 2016-2-13 09:18:34 | 显示全部楼层
第一轮第三题是不是用hashmap记录下当前的当前每个数和角标,然后照着最终排列一个一个移动同时更新就行了?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-13 09:33:19 | 显示全部楼层
Pat pat。第三轮第二题似乎前几天有人post过,用hashmap+arraylist可以实现o1,arraylist存所有的hashmap的key。每次删除一个key后,将list最后一个移到删除的位置并将长度减一。第一轮第三题能不能给个具体的例子?
回复 支持 反对

使用道具 举报

malc 发表于 2016-2-13 10:58:47 | 显示全部楼层
1.1 一遍hashtable B,然后遍历A标记相同,然后再次遍历输出剩下的
1.3 先找出空位,然后从第一个开始逐个交换
2.1 recursion,DP,A*
3.2 用linked list作为结构,能用random()函数吗,把第一个数作为seed
3.3 remove node,再相应减小size 保证random值正常
不对请指正
回复 支持 反对

使用道具 举报

vivienerwen 发表于 2016-2-13 12:45:05 | 显示全部楼层
patpat!!rp 爆棚了,会有offer的!!
回复 支持 反对

使用道具 举报

mikeyangh1992 发表于 2016-2-13 14:46:31 | 显示全部楼层
LZ也是USC37分的吗,。。我也是G家三轮游。。。而且每轮题目都做出来了都把我挂了。。
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-2-14 09:29:09 | 显示全部楼层
mikeyangh1992 发表于 2016-2-13 14:46
LZ也是USC37分的吗,。。我也是G家三轮游。。。而且每轮题目都做出来了都把我挂了。。

同胞啊。狗哥难道看简历本科不是cs的吗
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-2-14 09:30:14 | 显示全部楼层
malc 发表于 2016-2-13 10:58
1.1 一遍hashtable B,然后遍历A标记相同,然后再次遍历输出剩下的
1.3 先找出空位,然后从第一个开始逐个 ...

可以用random函数
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-2-14 09:33:34 | 显示全部楼层
googlerr 发表于 2016-2-13 09:33.鏈枃鍘熷垱鑷1point3acres璁哄潧
Pat pat。第三轮第二题似乎前几天有人post过,用hashmap+arraylist可以实现o1,arraylist存所有的hashmap的 ...

第一轮第三题:. visit 1point3acres.com for more.
比如这一排停车位初始状态:
CarA CarB CarC EmptySlot CarD CarE
移动CarA会变成:
EmptySlot CarB CarC CarA CarD CarE
现在给一个最终的排列,比如:
CarE CarA EmptySlot CarC CarB CarD
就求是经过怎样的移动,变换到最终情况的。
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-2-14 09:34:13 | 显示全部楼层
vivienerwen 发表于 2016-2-13 12:45
patpat!!rp 爆棚了,会有offer的!!

wen姐加油啊!!
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-2-15 08:47:11 | 显示全部楼层
LZ加油!好offer会来的!
想请问一下第二题的船是四个方向都能走吗?
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-2-15 10:12:24 | 显示全部楼层
sheepmiemies 发表于 2016-2-15 08:47.鐣欏璁哄潧-涓浜-涓夊垎鍦
LZ加油!好offer会来的!
想请问一下第二题的船是四个方向都能走吗?

是的。
不能走斜线。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-2-15 10:26:49 | 显示全部楼层
摸摸楼主,我都是安慰自己现在受的苦都是之前不够努力的报应,也怪不得别人,年轻时候受点挫比年纪大了才经历挫折好多了...... 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

还有就是想讨教一下题目....
第三题楼主怎么想的? 能不能每次查和给的初始相不相同,如果不想同,就把当前empty和初始该empty位置上的换一下,应该最多O(N)就好吧,不知道可不可行. visit 1point3acres.com for more.

还有那个设计数据结构的,如果hashmap存key 和 index的话,如果存在重复不就没办法处理了吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 17:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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