一亩三分地论坛

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

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

Google summer intern phone interview 11/04/2016

[复制链接] |试试Instant~ |关注本帖
LanceZZZ 发表于 2016-11-12 12:19:31 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 本科 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
2016年11月4日 G电面 两轮back to back 本人大三在读 找2017暑期实习
一个周了,G方面还没有给消息,不知道是什么情况。

第一个面试官只问了一道大题,内容大致如下:

给你一个一维array,标明一个区域内的山峦起伏(比如0位置上是1就代表这个地方的地面高度为1),然后再给你一个int 代表海平面(比如说这个数是4的话就代表海平面高度是4,因此之前讲的高度为3的地面实际就相当于海拔高度-3)。这样图中就会生成几个连续的水体,如图:

google-phone1

google-phone1


求:将图中几个连续的水体各自的大小记下来,并return为一个array。

第一道题只需要把array走一边,然后用几个变量顺着记一下就可以了。


然后面试官讲这道题follow up了一下,说有可能在某个地方,大洋底部,可能会有一个drain hole,会抽干周围所有的水(假设那个地方就是一个吸水的黑洞)。同样,让你把连续水体的size生成并且return回来。如图:. 1point 3acres 璁哄潧
google-phone2-min.jpg
这个第二道题最后思路是这样,建立一个array写sea_level,这样海平面不是一个固定值而是一个随位置不一样的数。initialize 海平面为那个固定值,然后根据每一个drain hole把海平面抽到适当的位置,然后再把类似第一题的走一遍的写法重新跑一遍。


第一轮面试结束。

第二轮面试是这样的:
                       
Q1.Write a function: given a vector of numbers, find out the 2 smallestelements.
基本上来说第一题就是找一串数当中最小的两个。
只要控制好condition就可以了,不多解释。

Q2.Moving Window Average

{1, 2, 3 ,4 ,5…}
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Givenwindow parameter 3, {1, 1.5, 2, (2+3+4/3,...}

solutionsol(3);
sol.GetValue(1);-> 1
sol.GetValue(2);-> 1.5

sol.GetValue(3);-> 2

第二题地里面以前出现过,让你写一个class,其中的GetValue() function返回从这个往前k次call的平均数。用类似rotated array的方法即可做。

希望这一篇面经对大家有帮助。

. 鍥磋鎴戜滑@1point 3 acres



补充内容 (2016-11-13 04:27):
第一轮第二个那个follow up的思路我是想说这样的:首先有一个sea_level_array = [5,5,5,5,5,5,5,5,5,5,5],然后在根据底下的黑洞来防水,最后形成一个sea_level_array = [5,5,4,4,3,2,0,3,4,5,5],然后再套用第一题

评分

1

查看全部评分

本帖被以下淘专辑推荐:

jiongjiongyoush 发表于 2016-11-12 12:42:05 | 显示全部楼层
没太懂第一题followup lz写的思路. more info on 1point3acres.com
能讲下如果按图中的情形是怎么做的么
回复 支持 反对

使用道具 举报

zhenjieruan 发表于 2016-11-12 13:10:11 | 显示全部楼层
我觉得第一题 followup 的话可不可以这么做,扫那个terrain 的 vector, 遇到-1就把海平面设为0然后左右扫,遇到的山如果比当前海平面高就把山当做当前海平面,直到遇到和初始海平面一样高的山停下,因为水不会漫过去.所以第二题给的那个 [1,5,1,4,3,2,-1,3,4,5,6] 得出的海平面就会就会变成[5,5,4,4,3,2,0,3,4,5,5]然后用第一题的算法根据新的海平面 vector 跑一边.
回复 支持 反对

使用道具 举报

 楼主| LanceZZZ 发表于 2016-11-13 04:28:17 | 显示全部楼层
jiongjiongyoush 发表于 2016-11-12 12:42
没太懂第一题followup lz写的思路
能讲下如果按图中的情形是怎么做的么

见补充内容
回复 支持 反对

使用道具 举报

 楼主| LanceZZZ 发表于 2016-11-13 04:29:38 | 显示全部楼层
zhenjieruan 发表于 2016-11-12 13:10
我觉得第一题 followup 的话可不可以这么做,扫那个terrain 的 vector, 遇到-1就把海平面设为0然后左右扫,遇 ...

基本上是这样。只是有一点关于复杂度的问题:如果你左右扫到了另外一个黑洞,就不要再继续扫了,这样的话可以把时间复杂度控制在O(n)
回复 支持 反对

使用道具 举报

jiongjiongyoush 发表于 2016-11-13 04:29:44 | 显示全部楼层

感谢~~~~
回复 支持 反对

使用道具 举报

challenge2016 发表于 5 天前 | 显示全部楼层
G家给消息了吗?
回复 支持 反对

使用道具 举报

 楼主| LanceZZZ 发表于 3 天前 | 显示全部楼层

十动然拒
回复 支持 反对

使用道具 举报

xxxxx56789 发表于 3 天前 | 显示全部楼层

啊,lz答这么好
回复 支持 反对

使用道具 举报

JoshISEE 发表于 3 天前 | 显示全部楼层
第二题能讲具体点吗?如果getValue返回前k个数的平均值,为什么不记录前k个数的和呢?还有array是sorted的吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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