May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2936|回复: 21
收起左侧

Google 15 Fall SDE Internship Phone Interview

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

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

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

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

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

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


感觉第二轮铁定跪了, 祝大家面试正常发挥吧. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


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

评分

1

查看全部评分

hulahu 发表于 2015-8-8 07:13:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主加油。 http://www.geeksforgeeks.org/reservoir-sampling/
回复 支持 1 反对 0

使用道具 举报

laurie洁 发表于 2015-8-6 06:12:09 | 显示全部楼层
关注一亩三分地微博:
Warald
昨天刚刚面过这题~
意思应该是从非常大的一个文件中等概率的挑出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行~. 1point3acres.com/bbs
由于事先不知道一共有多少行,所以 ...

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

使用道具 举报

laurie洁 发表于 2015-8-6 12:38:56 | 显示全部楼层
jiebour 发表于 2015-8-6 12:16
还是没懂哎,什么叫等概率挑出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. visit 1point3acres.com for more.
请问LZ,第二题该如何解决?

补充内容 (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不知道有多大。
注意定义

补充内容 (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”,也就是说算法对“任意(有限)长的序列”都有效,而不是说对“无限长的序列”有效。
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-7 12:42:36 | 显示全部楼层
stellari 发表于 2015-8-7 10:44
要真是“无穷长的序列的话”,任何算法也无法结束啊。我想这里面试官的意思其实是“indefinite”,也就是 ...

水塘抽样的无穷 可以认为是内存不能全部cache
回复 支持 反对

使用道具 举报

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

. Waral 鍗氬鏈夋洿澶氭枃绔,还没,我明年夏天毕业
回复 支持 反对

使用道具 举报

 楼主| 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
请问LZ,第二题该如何解决?. 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2015-8-6 14:23):
.鏈枃鍘熷垱鑷1point3acres璁哄潧
其实我后来网上找了代码之后发现代码量很简单,主要是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”,也就是 ...
. From 1point 3acres bbs
她是直接ctrl + v copy 道google doc中的,并非口述。。。。。是infinite
回复 支持 反对

使用道具 举报

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

P.S. 我没记错的话这个position是我六月初投的,貌似六月下旬就close了,new grad的话可以直接投full time吧
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-27 10:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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