一亩三分地论坛

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

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

google onsite 分享 mountain view

[复制链接] |试试Instant~ |关注本帖
jasusy 发表于 2015-8-21 13:49:08 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Failfresh grad应届毕业生

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

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

x
上周四去的onsite。之前过了一轮面经我分享过了。可以去我的帖子里找,应该容易找到。. more info on 1point3acres.com
一共4轮,感觉并没有地里其他面经那么难。感觉还不错,题目也都做出来了。却跪了不知道是不是跟政策和大选有关。

第一轮一个白人。开始给一共book 的class。里面有一些variable 比如string author;string title;等 叫我实现function,findbookbyauthor() and findbookbytitle(); 开始犹豫用两个hashmap会不会太占空间,跟面试官交流了一下,说没问题。那就开始写了。这个函数问题是同一个author肯能会有好多book,所以在map里面存的是一共linkedlist不是直接book。follow up一是怎么加一共排队序列,就是可能有一些人要预约这本书,再follow这个排队序列可能是有一些用户有高priority怎么处理,再follow up现在有一个rating,每本书都有评分,怎么找到所有books在给定的rating范围内。就好了。
后来你说是我总是要提醒,但是我感觉我是一写这有问题,自己还没开始检查自己的代码他就提醒我了,他不提醒我我也是会发现的嘛。。。
. 1point 3acres 璁哄潧
第二轮是个阿三, 这个我是真感觉坑。介绍一下一个项目,他自己根本没听我讲的样子,眼神游离。叫我写个function返回给定序列的所有子集。element就是integer。我开始写一个for循环n从1到n代表子集element个数,空的循环完加上,里面在调用helper返回对应个数的sub set combination。他竟然看不懂,看不懂!!!然后叫我走一遍{1,2,3}这个例子,我给他解释了好久,再加上他叫我求复杂度。。这里就浪费了十几分钟。最后他才说想用2^n的方法,就是所有子集应该是从n=0到n-1,对应的element可能加也可能不加进去,就这样迭代下去,复杂度是2^n。还说这个简单,当时还愣住了,难道真是这个简单,然后时间就到了,实际上现在想想不太对。
. From 1point 3acres bbs
第三轮还是一个白人,开始warmup问我,如果现在开会有一个人急着走,但是他电脑里有100gb的数据怎么快速practical得拷到另一个电脑上。一顿扯淡。然后就到了一题最绕的了。plus 1,但是给的数可能很长,也行有千万位,怎么处理?这题开始被自己绕住了,吧自己和面试官都整糊涂了,不过最后还是做出思路吧helper写出来了。就是没有最优化到底,你们自己想会吧,我先不说我的方法。

第四轮是最好的一轮最后给feedback也是positive。不过感觉也不是很难。先说两个文件每行里面都是一个数字,很多很多行内存可能存不下了,要求做点乘,得到结果。就是两个文件每一行相乘之后,所有这样的乘积相加。而且两个文件里面数据很parse就是很多数字是0. 开始一下子忘了parse这个条件,就说先读个一定行数,比如100行,乘了相加,完了继续读一百行,如此反复到结束。后来她提醒说很多零,我想了想,还是说没区别,因为你数据不应该一行一行读然后判断,因为从disk读很慢,读了一行,看是不是零是零就跳过,处理再读一行再处理这样太慢。如果直接读一百行然后相乘的时候判断对应行是不是零和直接不判断相乘加入结果差不多,因为乘以零和加零速度都很快。没必要ifelse。最后她说好像是的。然后说我的解决方法没有问题但是她不是这个意思。她说想让我做一个structure压缩一下数据,压缩后想还原回去也是可以的。然后我觉得这样用array,arraylist或者nodelist都可以,最后我用了nodelist,然后写代码,一阵写,followup如果两个文件不同行数,怎么处理,就结尾的时候处理一下,改代码。第二题是positive sequence 找是不是存着连续数列使得相加和等于给定target。开始直接two pointer window得到结果,属于greedy algorithm,写完了,她看感觉不对,太快了。于是followup 说如果有negative number呢,我开始说negative也行吧,后来发现不行,然后我就用dp,blabla写完code。终于结束。最后一轮面了一个多小时。不过值了。

anyway,最后还是decline了。恩,看来得继续刷题,刷个跟熟练就好了。
给大家分享,希望有用。本人已经伤不起。。。。疗伤去了。


评分

3

查看全部评分

本帖被以下淘专辑推荐:

Williamslg 发表于 2015-8-22 02:59:44 | 显示全部楼层
jasusy 发表于 2015-8-22 02:10
我当时看到是array,string类的就想到dp了,感觉蛮简单。至于hashmap怎么做能仔细说一下吗?我一下没想到 ...

hashtable的思路是:假设数组是nums[] 维护变量sum 表示从index = 0 到 index = i 的sum,并存到hashtable里,第i + 1个数来的时候更新一下sum += nums[i + 1] , 然后去hashtable里找 key =sum - target,因为hashtable里存的是之前的nums[0],nums[0..1]... nums[0..i]的这些分段和,所以如果有发现里面有sum - target的话,那sum - target = sum of num[0] to num[x], 那就说明 x +1到 i + 1的和为 target.没有的话就把sum存在hashable里,继续往下走。
LZ这个大数加1的方法很不错啊,上一组20有进位就直接用结果,没有进位就保留原来的,结束。给的数是positive的话,进位只发生在数字为9的情况,但是如果数字是100000000.....0000009, 其实只更改最后的09,没必要计算所有的,不知道能不能针对这个来进一步优化一下
回复 支持 4 反对 0

使用道具 举报

cszeus 发表于 2015-12-29 06:10:21 | 显示全部楼层
第三轮难道不是把硬盘留下?换到目标电脑上?
回复 支持 3 反对 0

使用道具 举报

Williamslg 发表于 2015-8-22 01:21:47 | 显示全部楼层
1,3轮LZ能详细说说嘛,完全摸不到头脑?第四轮的第二题是不是可以不用DP,用一个hashtable存cumulative sum,每次更新sum之后,check一下sum - target是否在hashtable内
回复 支持 1 反对 0

使用道具 举报

starriver 发表于 2015-8-21 17:14:04 | 显示全部楼层
lz第四轮压缩是什么意思啊?是读进来压缩了再输出么?
能不能详细讲一下解法?~
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-22 01:54:57 | 显示全部楼层
starriver 发表于 2015-8-21 01:14
lz第四轮压缩是什么意思啊?是读进来压缩了再输出么?
能不能详细讲一下解法?~

也很简单,不是很parse很多0吗,读进来用node表示的时候,一个node里面有val,和num,表示几个连续的数据就好了,如果连续几十个0,用一个node表示就省很多空间。
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-22 02:10:52 | 显示全部楼层
Williamslg 发表于 2015-8-21 09:21
1,3轮LZ能详细说说嘛,完全摸不到头脑?第四轮的第二题是不是可以不用DP,用一个hashtable存cumulative su ...

我当时看到是array,string类的就想到dp了,感觉蛮简单。至于hashmap怎么做能仔细说一下吗?我一下没想到,因为是里面随意连续数列的和,没想到怎么处理。. more info on 1point3acres.com
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第三轮warmup就是相当于怎么最快从一台laptop数据拷到另一台/多台电脑上。
. 鍥磋鎴戜滑@1point 3 acres
无敌长数加以我一开始被硬件里面的adder混淆了很久,因为那里有个P,G模型,你搜索tree adder design应该能搜到对应的东西,可惜我忘了推导n就推不出来。但是实际这里加一敲代码没有理论那么麻烦。最后硬着头皮敲代码去。

最简单的方法就是,把所有数据分割成20位一份,async执行加一保存在array里,注意可能会产生21位。意思就是如果上一个20位传过来一个一,我可以直接给出一个这20位加一的结果,不需要再算20位相当于用一个时间单位取代了原来要的20个时间单位。因为我们所有的20位都是在一开始(第一个20位)在算的时候就算了。所以最后时间复杂度应该是:20位块个数+20。

再optimize一下就是(但是没有optimize时间到了),怎么确定这个取20位以一块。也许是50,针对不同长度取个最优值。另外如果还是20位,还可以这样想,我20位不一定要20个时间单位,我可以像上一级分出20位一样,我这里20位分成5个4位!这样20位时间就成了9.

再回到原数串,我可以不用一下子都分好,我也许可以2分法,开始分成两部分,再两部分里面再分,最后到一个最优的小块。这个有点难,我没整明白怎么实现。求大家讨论。

不知道有没有讲清楚
回复 支持 反对

使用道具 举报

hackenkreuz 发表于 2015-10-18 02:25:32 | 显示全部楼层
请问LZ第三轮那个warmup的解答,搞不清楚拷贝数据还能怎么样,难道是把数据分割开来考到多台电脑上
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-7 01:29:22 | 显示全部楼层
感谢lz分享,我觉得第二轮的那个阿三好坑,感觉lz用DFS算法的时间复杂度应该也是O(n^2)吧,只是表达方法不同而已,实质是一样的呀。。。。还有那个第四轮两个parse的文件相乘,压缩的话,能不能直接用一个array表示1所在的位置,0直接忽略掉呢?
回复 支持 反对

使用道具 举报

jinzheyu 发表于 2015-11-15 04:41:59 | 显示全部楼层
楼主拿到HR提供的4轮面试各个的feedback了吗?方便分享一下吗?谢谢。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-8 10:19:47 | 显示全部楼层
楼主第一题就是hashmap<Book, Set<Author>> hashMap<Author, Set<Books>>?
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-29 05:31:30 | 显示全部楼层
我觉得面试结果跟政策 跟大选 跟阿三关系不大吧...主要还是看实力。
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-12-29 14:12:38 | 显示全部楼层
randomusername 发表于 2015-12-28 13:31
我觉得面试结果跟政策 跟大选 跟阿三关系不大吧...主要还是看实力。

哥,不要这样,我不是大神,说自己能稳过的,要看运气的。
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-12-29 14:14:05 | 显示全部楼层
jinzheyu 发表于 2015-11-14 12:41
楼主拿到HR提供的4轮面试各个的feedback了吗?方便分享一下吗?谢谢。

一半一半吧,好久了。现在已经有东家,以后有机会在试了。
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-12-29 14:14:23 | 显示全部楼层
bobzhang2004 发表于 2015-12-7 18:19.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主第一题就是hashmap hashMap?
. more info on 1point3acres.com
太久了,已经忘了,哈哈
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-12-29 14:21:55 | 显示全部楼层
hackenkreuz 发表于 2015-10-17 10:25
请问LZ第三轮那个warmup的解答,搞不清楚拷贝数据还能怎么样,难道是把数据分割开来考到多台电脑上

我不知道,现在感觉就是扯。要更现实一点做法。我觉得让我现在说我就说这种问题不是技术问题。如果知道有急事要提早走就应该早点提出来然后早点把数据拷出来。反之如果是突然发生的事情比如家里有人出事了或者怎么样也不需要用电脑,电脑就留这里好了,以后要用给寄过去。或者干脆就慢慢拷贝,就10几分钟而已。真是连十几分钟都等不了的急事,还是突然发生的,还有要用电脑的,这是时间安排的问题,用技术解决感觉纠错了,这个人也可以解雇了。
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-29 14:44:41 | 显示全部楼层
jasusy 发表于 2015-12-29 14:12
哥,不要这样,我不是大神,说自己能稳过的,要看运气的。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
恩恩 我懂..运气是很重要滴... 但我觉得印度人总是被黑 有时候其实就是面试的人自己做不好 想成被黑 或者做好了又意淫印度人要害他...... 这样好像有点不对
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-1-20 13:37:05 | 显示全部楼层
cszeus 发表于 2015-12-29 06:10
第三轮难道不是把硬盘留下?换到目标电脑上?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你不去google就是google的损失!!!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-26 00:51:42 | 显示全部楼层
第二轮就是leetcode subset?
回复 支持 反对

使用道具 举报

sphenx 发表于 2016-1-26 03:28:58 | 显示全部楼层
阿三扮演就是来黑人的角色,如果安排一个国人兄弟,结果会不同
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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