一亩三分地论坛

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

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

Google 15 Fall SDE Internship Phone Interview

[复制链接] |试试Instant~ |关注本帖
neethan 发表于 2015-8-6 05:33:05 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
在网上自己有投递,之后有找朋友refer了一下,不知道是哪个过的。约了两轮的phone interview,听口音应该都是中国人,第一轮一个男工程师,第二轮一个女工程师,第一轮简单交流了项目。两轮差别还挺大的

第一轮题目比较简单。
给一个unsigned Integer in String type. plus one and return the result as String. 之后Follow up是变成signed,传入的可能为正也可能为负数。. Waral 鍗氬鏈夋洿澶氭枃绔,
. visit 1point3acres.com for more.
第二轮感觉自己直接跪了,工程师没问项目经验直接给问题,然后感觉上她之前也没准备,电话通了两分钟后直接从题库Ctrl + C 过来了一道题, 完全没搞懂是什么意思,是没接触过的概念
Given a infinite stream of number, return a random element with equal probability. 然后她直接给了我方法头:public int getRandom(int[] arr) {} 对这题完全没概念,跟她确认了半天直接写了一个random出一个index的方法,然后她就说感觉不对,说我对题的理解可能有问题,然后余下的几乎所有时间就再跟她确认题目,但是可能因为本身准备不充分对概念理解也有偏差,加上面试官一直不肯多说。感觉这题是跪了
最后结束的时候问我之前有没有接触过reservoir sampling 我说没有,她说你可以回去查查。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. visit 1point3acres.com for more.
感觉第二轮铁定跪了, 祝大家面试正常发挥吧.1point3acres缃


补充内容 (2015-8-8 05:25):.1point3acres缃
=====================
昨天和HR发邮件argue了一下,比较幸运,她今天回复说可以再给我安排一次面试,希望这次能发挥好一点吧

评分

1

查看全部评分

hulahu 发表于 2015-8-8 07:13:01 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

laurie洁 发表于 2015-8-6 06:12:09 | 显示全部楼层
昨天刚刚面过这题~
意思应该是从非常大的一个文件中等概率的挑出N行~
由于事先不知道一共有多少行,所以要每扫一行adjust前面已经挑出的行的概率~
回复 支持 反对

使用道具 举报

bluestarwing 发表于 2015-8-6 06:40:15 | 显示全部楼层
LZ毕业了吗?不知道已经毕业的能不能投呀
回复 支持 反对

使用道具 举报

zzpnm003 发表于 2015-8-6 11:03:58 | 显示全部楼层
请问第一题是什么catch, 是不许用库,自己把string变整数吗?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-6 12:16:31 | 显示全部楼层
laurie洁 发表于 2015-8-6 06:12. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
昨天刚刚面过这题~
意思应该是从非常大的一个文件中等概率的挑出N行~
由于事先不知道一共有多少行,所以 ...

还是没懂哎,什么叫等概率挑出N行?
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-8-6 12:38:56 | 显示全部楼层
jiebour 发表于 2015-8-6 12:16
-google 1point3acres还是没懂哎,什么叫等概率挑出N行?

比如在扫了M行的时候已经挑出了N行~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
那么再扫M+1行的时候,就需要考虑要不要选最后一行,同时怎么样adjust之前的N行使他们的概率由N/M变成N/(M+1)
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-8-6 13:04:15 | 显示全部楼层
请问LZ,第二题该如何解决?

补充内容 (2015-8-6 14:23):
http://www.cnblogs.com/buptLizer/archive/2012/04/08/2437416.html
这个办法好像可以 好像很简单的样子
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-6 13:20:19 | 显示全部楼层
确定面试官说的是“return a random element”,而不是“return K unique numbers randomly”么?如果只是返回一个随机值的话,确实用随机数发生器随机返回一个元素就好了。如果要返回K个,这时才涉及reservoir sampling。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-7 02:45:20 | 显示全部楼层
laurie洁 发表于 2015-8-6 12:38
比如在扫了M行的时候已经挑出了N行~
那么再扫M+1行的时候,就需要考虑要不要选最后一行,同时怎么样adju ...

数组一共5个数,四个四,一个一,你怎么adjust?
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-7 06:17:44 | 显示全部楼层
f1371342385 发表于 2015-8-5 21:04
请问LZ,第二题该如何解决?
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-8-6 14:23):

文章里是一个loop从k到N, N应该是不能无穷大的,否则没法结束了。这里是infinite stream 没法用这种方法
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-8-7 10:16:33 | 显示全部楼层
jasusy 发表于 2015-8-7 06:17
文章里是一个loop从k到N, N应该是不能无穷大的,否则没法结束了。这里是infinite stream 没法用这种方法

Reservoir Sampling:从N个数中随机抽取k个元素,保证每个元素被选中的概率相等,N不知道有多大。. From 1point 3acres bbs
注意定义
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-8-7 10:17):
在文章的第一行
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-7 10:44:22 | 显示全部楼层
jasusy 发表于 2015-8-7 06:17
文章里是一个loop从k到N, N应该是不能无穷大的,否则没法结束了。这里是infinite stream 没法用这种方法

要真是“无穷长的序列的话”,任何算法也无法结束啊。我想这里面试官的意思其实是“indefinite”,也就是说算法对“任意(有限)长的序列”都有效,而不是说对“无限长的序列”有效。.1point3acres缃
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-7 12:42:36 | 显示全部楼层
stellari 发表于 2015-8-7 10:44.1point3acres缃
要真是“无穷长的序列的话”,任何算法也无法结束啊。我想这里面试官的意思其实是“indefinite”,也就是 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
水塘抽样的无穷 可以认为是内存不能全部cache
回复 支持 反对

使用道具 举报

 楼主| neethan 发表于 2015-8-8 05:14:33 | 显示全部楼层
bluestarwing 发表于 2015-8-6 06:40
LZ毕业了吗?不知道已经毕业的能不能投呀

还没,我明年夏天毕业
回复 支持 反对

使用道具 举报

 楼主| neethan 发表于 2015-8-8 05:15:29 | 显示全部楼层
zzpnm003 发表于 2015-8-6 11:03
请问第一题是什么catch, 是不许用库,自己把string变整数吗?

没让用parseInt,我是直接toCharArray的
回复 支持 反对

使用道具 举报

 楼主| neethan 发表于 2015-8-8 05:19:21 | 显示全部楼层
f1371342385 发表于 2015-8-6 13:04. from: 1point3acres.com/bbs
请问LZ,第二题该如何解决?

补充内容 (2015-8-6 14:23):

其实我后来网上找了代码之后发现代码量很简单,主要是reservoir sampling这个concept和思想不太懂。这题就是给Reservoir Sampling做一个modify, k = 1, 每次call的时候,当前长度为n的话,random出来一个1 - n的数,如果是n就返回最后这个,如果不是(1 - (n - 1))就返回上次的那个。这个是我查到的解答,但是我还是多少有点晕,k的那个算法我倒是明白了,但是这个k = 1 的情况还是有点晕
回复 支持 反对

使用道具 举报

 楼主| neethan 发表于 2015-8-8 05:21:15 | 显示全部楼层
stellari 发表于 2015-8-6 13:20
确定面试官说的是“return a random element”,而不是“return K unique numbers randomly”么?如果只是 ...

确定,是主要an element。是modified reservoir sampling,是 k = 1的情况, 因为stream嘛,所以每次call的时候长度都会变,如果梅西都是random的话会导致总体来看前面元素被取出的概率变大。
回复 支持 反对

使用道具 举报

 楼主| neethan 发表于 2015-8-8 05:22:43 | 显示全部楼层
jasusy 发表于 2015-8-7 06:17
文章里是一个loop从k到N, N应该是不能无穷大的,否则没法结束了。这里是infinite stream 没法用这种方法

没有吧,infinite其实就是说总体的长度未知或者无穷,主要是想表达说每次你call这个方法的时候这个流的长度都会变的意思吧
回复 支持 反对

使用道具 举报

 楼主| neethan 发表于 2015-8-8 05:23:47 | 显示全部楼层
stellari 发表于 2015-8-7 10:44 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
要真是“无穷长的序列的话”,任何算法也无法结束啊。我想这里面试官的意思其实是“indefinite”,也就是 ...

她是直接ctrl + v copy 道google doc中的,并非口述。。。。。是infinite
回复 支持 反对

使用道具 举报

 楼主| neethan 发表于 2015-8-8 05:26:27 | 显示全部楼层
bluestarwing 发表于 2015-8-6 06:40
LZ毕业了吗?不知道已经毕业的能不能投呀
. from: 1point3acres.com/bbs
P.S. 我没记错的话这个position是我六月初投的,貌似六月下旬就close了,new grad的话可以直接投full time吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 05:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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