一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
sheepmiemies 发表于 2016-3-19 06:03:10 | 显示全部楼层 |阅读模式

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

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

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

x
LZ选的Seattle position,准时收到电话,听声音像是个很nice的白人小哥。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

开场让我自我介绍,聊了个project,然后出题。

题目:
input 是一个游戏的后台log (可以自己定义结构):. 1point 3acres 璁哄潧
(1) update log,每条记录是 (time, player, role),比如 (2016 March 11 13:10 UTC, 'mark', 'knight')
(2) play log,没条记录是(time,player),比如 (2016 March 12 12:10 UTC, 'mark')


output是每个role出现的次数。

面试过程:. Waral 鍗氬鏈夋洿澶氭枃绔,
问清楚input&output,说input结构可以自己定义。我的回答是把所有update建一个 per-user map,update list按序存成数组。每次读play log,按player找到update list,然后binary search。时间NlogL, N是play log长度,L是per-user update list 的最大长度。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
快写完的时候,小哥说可以先不写binary search 容易错,我们先linear scan。。。小哥一直很nice应该不是BS我。。。写完给我提了一个小bug然后问了下test case。
. 1point3acres.com/bbs
总结:
自我介绍加聊project大概六七分钟的样子,clear question和说解法也是六七分钟,十五分钟边说边写完了之后,说完test cases就只有七八分钟了,小哥说差不多还是留几分钟那我们就进入提问环节吧。
感觉写的速度一般,不快不慢,说话不够简洁浪费了点时间,都需要多练啊。。。求过!
. 鍥磋鎴戜滑@1point 3 acres


补充内容 (2016-4-10 00:05):
补充一下,output是要用play log去找每个role的 登陆次数

评分

1

查看全部评分

a27400 发表于 2016-3-19 11:59:07 | 显示全部楼层
好棒!我也投的seattle  说不定以后可以一起玩耍啊
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-3-19 13:16:26 | 显示全部楼层
a27400 发表于 2016-3-19 11:59
好棒!我也投的seattle  说不定以后可以一起玩耍啊

哈哈,当然好啊!叶神肯定没问题!我正在挣扎 LOL
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-3-20 07:11:34 | 显示全部楼层
避免引起歧义解释下。。update表示某个时刻某个玩家切换了角色,play log表示某个时刻某个玩家登陆了游戏,也就是要用play log的时间找该玩家play 的role,然后统计次数,登陆一次就算一次
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-3-20 07:36:47 | 显示全部楼层
再举个例:play log里有4条记录,mark 3条,jack 1条,mark玩过两次wizard一次knight (切换角色反应在update log里),jack玩过一次wizard,所以wizard一共3次,knight一次
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-1 05:10:28 | 显示全部楼层
请问楼主出结果了吗?
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-4-1 12:06:34 | 显示全部楼层
bobzhang2004 发表于 2016-4-1 05:10
请问楼主出结果了吗?

在约onsite
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-1 12:14:30 | 显示全部楼层
.鏈枃鍘熷垱鑷1point3acres璁哄潧
是面后几天的结果呢?
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-1 13:50:31 | 显示全部楼层
我同学投西雅图职位的也是这道题呃
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-1 13:53:16 | 显示全部楼层
是每次用play log的player 的time去binary search,找到他之后的role,角色加一次吧?
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-4-1 23:14:29 | 显示全部楼层
bobzhang2004 发表于 2016-4-1 12:14
是面后几天的结果呢?

还挺快的,周五面的,第二周周一就通知了
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-4-1 23:16:06 | 显示全部楼层
cx00001 发表于 2016-4-1 13:53
是每次用play log的player 的time去binary search,找到他之后的role,角色加一次吧?

这么巧!是的,扫一遍play log的记录,用每个记录的时间做binary search,从update log里找到对应role加一次。
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-5 08:43:05 | 显示全部楼层
我是不是哪里理解错了
用每一个role作为key建一个hash map, 然后一条条直接读update log,数每个role出现的次数不就可以知道了?为什么还需要play log?原谅我弱弱的理解能力。。。
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-4-9 23:22:46 | 显示全部楼层
为什么要BS? 两个Map 像foreign key的设计不行吗 <player, role> <role,count>  没明白LZ的bs用来干嘛
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-4-9 23:41:39 | 显示全部楼层
cx00001 发表于 2016-4-1 13:50
我同学投西雅图职位的也是这道题呃

擦原来是你!
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-4-9 23:43:12 | 显示全部楼层
Alice0701 发表于 2016-4-5 08:43
我是不是哪里理解错了
用每一个role作为key建一个hash map, 然后一条条直接读update log,数每个role出现 ...

不好意思没说清楚,统计的次数是基于play log的,也就是每个role登陆了多少次

补充内容 (2016-4-9 23:45):
如果只需要update,play log也就没必要存在了
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-4-9 23:44:24 | 显示全部楼层
陈润鹏 发表于 2016-4-9 23:22
为什么要BS? 两个Map 像foreign key的设计不行吗    没明白LZ的bs用来干嘛

不好意思没说清楚,统计的次数是基于play log的,也就是每个role登陆了多少次,但是你得知道每个人登陆的时候用的是哪个角色, 需要去查update log, 因为一个玩家可能换了很多个role
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-10 00:02:20 | 显示全部楼层
sheepmiemies 发表于 2016-4-9 23:43
不好意思没说清楚,统计的次数是基于play log的,也就是每个role登陆了多少次

补充内容 (2016-4-9 23:45 ...
. 鍥磋鎴戜滑@1point 3 acres
原来是这样 现在明白啦 谢谢楼主!
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-4-10 04:32:17 | 显示全部楼层
好傻逼 应该猜到就是你 这名字太个人特色了
回复 支持 反对

使用道具 举报

csh130 发表于 2016-4-10 05:23:56 | 显示全部楼层
我也投的西雅图的那个 马上电面...  是不是这个题几率很大呀
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 11:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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