一亩三分地论坛

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

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

google 电面

[复制链接] |试试Instant~ |关注本帖
tinatina 发表于 2015-10-2 09:10:00 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
觉得google电面真的没有题库可言,看了很多帖子,感觉都是面试官自己选的题。所以对于我这种还没有融会贯通的人来说,应该是挂了……
面试官听着像美国人,上来问了个名字,然后就出题了。说web server会一直收到increment,请implement三个函数:getLastMinute(),getLastHour(),getLastDay(),分别返回last minute, last hour, last day中的increment的个数
lz技术渣,并不知道什么是increment,也完全不知道要干什么……就问有什么input吗,他说 都没有input
然后我就说先定义一个类class Increment,property包括minute, hour, day (我觉得既然函数包含这些,那它肯定有这些属性吧). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后建一个stack<Increment>,来了往里放,getLastMinute()的时候,往外拿

然后他说,需要放Increment吗,你为什么要建这个类,我说因为之后用起来方便,看着也更formal
他说 你再想想,比如放long之类的数字,我说,那可以直接建三个stack,分别用Class Date.getMinute()之类的,分别放minute, hour, day
他又说,increment是有timestamp的
然后……悲剧的是,我完全不知道timestamp到底是个神马,虽然听过……哎,活该悲剧,继续好好学习java吧
我就说 我不熟timestamp,他说 是存1970年以来的second,我就说那我需要先把它转化为day, hour, minute
他又说 需要吗……
我想想有说 好像不需要,可以用getTimestamp()得到当前的时间,然后stack.pop(),如果getTimestamp() - stack.pop() <= 59,那就count++,最后返回count. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
他说那getLastHour(), getLastDay()差不多吗,我说对,getLastHour就是getTimestamp() - stack.pop() <= 3599;
然后就问了下时间 空间复杂度什么的. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


他接着说,可是量很大,一分钟可能有上百万 上亿的increment,
我说不然可以用bucket,每个bucket为一分钟,这一分钟之内来的都存在这里
他说可以,那这个的时间 空间复杂度呢
我说,这样查找getLastMinute,只需要O(1);空间复杂度的话, 比如对于一天来说,只需要建一个24*60那么大的array就行了


然后他就说时间差不多了……有啥问题吗,recruiter会再联系你的


挂了电话,冷静一下,才发现,算是挺简单的题目,可我java基础学的太差,又太紧张,太没自信。不过已然这样了,我也只能想 我目前这水平,onsite也只是去被虐的. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


发出来记录一下吧,也祝各位找工顺利,加油!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

donnice 发表于 2015-10-2 09:51:12 | 显示全部楼层
一上来就问web server还是厉害
回复 支持 反对

使用道具 举报

地里小马甲 发表于 2015-10-2 11:08:26 | 显示全部楼层
我的思路是用链表(可能要双向链表)来存, 每个节点表示为(timestamp, count) , timestamp精确到minute,查找从尾部开始查找,定期从头开始清理过期的。。。不知道这样reasonable不。。。
回复 支持 反对

使用道具 举报

 楼主| tinatina 发表于 2015-10-2 11:22:41 | 显示全部楼层
donnice 发表于 2015-10-2 09:51. From 1point 3acres bbs
一上来就问web server还是厉害

一开始完全没有理解他要我做什么,,感觉这儿耽误了很多时间
回复 支持 反对

使用道具 举报

 楼主| tinatina 发表于 2015-10-2 11:27:01 | 显示全部楼层
地里小马甲 发表于 2015-10-2 11:08. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我的思路是用链表(可能要双向链表)来存, 每个节点表示为(timestamp, count) , timestamp精确到minute,查找 ...

我现在想想,重点好像不是怎么存这些increment,毕竟数据量太大,是怎么统计。
有同学说 如果知道每天会产生的average increment,比如5万,可以直接跳到5万那儿,然后往它的左右找
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-2 11:29:44 | 显示全部楼层
这题我觉得先得问清楚一点:getLastMinute()到底返回的是哪个时间范围内的increment数。
-google 1point3acres
比如我在开始计时后3分20秒 = 200秒时调用了getLastMinute(),那么我应该返回的是140秒~200秒之间(即调用函数前的60秒)的increment数,还是120秒~180秒(即调用函数时间先近似到整数分钟,然后再前溯60秒)?这两者是有很大差别的。而且如果是前者的话,就不能用楼主说的bucket的方法了。看面试官的态度,可能本意是后者,但我觉得还是问清楚比较好。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主的第一种方法,也可以改进为二分法查找。十亿的increment也就最多30次比较。
回复 支持 反对

使用道具 举报

lemonie 发表于 2015-10-2 13:05:36 | 显示全部楼层
3.75......... jobfair 白投了==
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-2 15:30:16 | 显示全部楼层
stellari 发表于 2015-10-2 11:29
这题我觉得先得问清楚一点:getLastMinute()到底返回的是哪个时间范围内的increment数。
. more info on 1point3acres.com
比如我在开始计 ...

请问一下,这题能不能用一个24*60的数组,循环记录每分钟的increment数,然后调用last的时候,直接统计相关内容?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-2 20:44:48 | 显示全部楼层
坐看云起 发表于 2015-10-2 15:30
请问一下,这题能不能用一个24*60的数组,循环记录每分钟的increment数,然后调用last的时候,直接统计相 ...

所以我才说得先问清楚需求才能做啊。如果题目中的lastXXX系列函数都是要求“精确到分钟”,这样可以;但如果是要“精确到秒”,24*60就不行了,得用24*3600。

你说面试官为啥说timestamp是“1970年来的秒数”呢?也许他已经暗示了要“精确到秒”了。
回复 支持 反对

使用道具 举报

 楼主| tinatina 发表于 2015-10-2 21:03:15 | 显示全部楼层
stellari 发表于 2015-10-2 20:44
所以我才说得先问清楚需求才能做啊。如果题目中的lastXXX系列函数都是要求“精确到分钟”,这样可以;但 ...

对,你说了这个 我才想起来应该问清楚这个要求的,我却没有问…
如果从实时往前倒一分钟,应该就要用24*3600,如果只是last minute,可以用24*60
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-2 21:14:46 | 显示全部楼层
tinatina 发表于 2015-10-2 21:03
对,你说了这个 我才想起来应该问清楚这个要求的,我却没有问…
如果从实时往前倒一分钟,应该就要用24* ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是啊,如果lastMinute是“上一个整数分钟”,而不是“当前时间之前60秒”的话。按照这个逻辑,lastDay也应该是“前一个整天”,而不是“当前时间之前24小时”啊。那样的话,就需要最多记录两天,也就是48 x 60分钟的内容了。所以嘛,我觉得遇到这种情况一定要先问清楚,最好能让他给例子。我看好多面经都是做到最后才发现写出的结果和面试官的本意相左。
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-2 23:41:01 | 显示全部楼层
感觉问题好抽象,看了讨论才大概理解是个什么意思,然而感觉还是只能说个思路,这种题代码怎么写?
回复 支持 反对

使用道具 举报

 楼主| tinatina 发表于 2015-10-2 23:51:09 | 显示全部楼层
又见紫风铃 发表于 2015-10-2 23:41. visit 1point3acres.com for more.
感觉问题好抽象,看了讨论才大概理解是个什么意思,然而感觉还是只能说个思路,这种题代码怎么写?

是啊,所以时间基本上都花在弄清楚题目意思上了,代码几乎没怎么写……
感觉这题的重点是思路,可能你的想法和交流更重要吧
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-3 00:07:45 | 显示全部楼层
tinatina 发表于 2015-10-2 23:51
是啊,所以时间基本上都花在弄清楚题目意思上了,代码几乎没怎么写……
感觉这题的重点是思路,可能你的 ...

下周要面了表示好虚。。。
回复 支持 反对

使用道具 举报

 楼主| tinatina 发表于 2015-10-3 11:24:09 | 显示全部楼层
又见紫风铃 发表于 2015-10-3 00:07
下周要面了表示好虚。。。

祝你好运啦,不要紧张 自信一点
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-3 20:38:15 | 显示全部楼层
tinatina 发表于 2015-10-3 11:24. 1point 3acres 璁哄潧
祝你好运啦,不要紧张 自信一点

恩,谢谢楼主!也祝楼主好运啦!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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