聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2361|回复: 8
收起左侧

google 11.23intern 电面

[复制链接] |试试Instant~ |关注本帖
nash142857 发表于 2015-11-25 09:09:22 | 显示全部楼层 |阅读模式

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

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

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

x
1轮 (倒霉地碰到了阿三,听的耳朵难受)
1.初始化给一个数组[1,2,2,3,4],再给一个数x, 球从数组random pick一个数y, y <=x 的概率。。这个function会被call很多次。
       A: 排序,每次调用二分上界就好。
2.给一个String [] queries, 一系列query,球里面top 1 % popular(出现次数)的queries.
       我是用hashmap 扫一遍得到count,然后用一个min_heap 维护1%个数的queries.(快排的quick-find步骤应该更好).
然后follow-up 问我query太多怎么办,我说可以把query存在HDFS 用map-reduce去做,(然后花了15分钟问我map reduce细节应该咋做。。真是给阿三跪了)...

2轮(应该是个白人大叔)
1.给一系列选举 (某一时间选了某人).
class vote {
     String candiate;
     int timstamp;
}
比如
timestamp    candidate
1      X
2        Y
3       Y. from: 1point3acres
4       Z. From 1point 3acres bbs
5       Z
. 1point 3acres 论坛6        Z
然后再给出一个时间搓,问这个时间搓之前哪个选举人得票最高。。(这个function只call一次)
我就遍历数组时间搓 <= given timstamp, 用hashmap 存每个candidate出现count,取最高的返回就好

follow up, 如果要得到最高的k个呢。。
。。感觉面的跟一面那个一样(用个min_heap维护就好)

继续follow up, 输入是 Vote [] votes, String []candidates..
比如 votes 如上述,candidaes = ['Y','X'],要问存不存在一个timestamp 使得当前timestamp下candidate排名根给的candidates数组吻合
比如candidates = ['Y','X'] 返回就是timestamp 3 (timestamp 2有歧义,Y和X 一样 面试官说不行). 围观我们@1point 3 acres

我的做法是 根据timestamp sort votes first, 用hashmap 维护count 然后将当前timestamp下的hashmap输出到数组 排序跟candidates比较。。
但是写完了就发现自己傻逼了。。每次排序都是mlog(m) (m是candidates的size)....最后跟他说可以用一个bst维护(candidate, count)的pair(comparator根据count 比较)
这样插入更新都是log(m), inorder traverse得到排序结果, O(m), 复杂度就少了一个log(m)....

最后面完了发现,,既然O(m)....直接用个linkedList维护就好了,每次increment的时候做一个插入排序的插入操作就好(linkedlist维护是有序的)..

总之感觉面的一般,一面被阿三follow up问醉了。。二面最后这题写的也不好。球host match QAQ. 1point3acres

评分

1

查看全部评分

bobzhang2004 发表于 2015-12-2 06:52:41 来自手机 | 显示全部楼层
query太多应该是说要rate limitor吧?
回复 支持 反对

使用道具 举报

 楼主| nash142857 发表于 2015-12-2 23:56:50 | 显示全部楼层
bobzhang2004 发表于 2015-12-2 06:52
query太多应该是说要rate limitor吧?

这样的啊。为啥呢?
回复 支持 反对

使用道具 举报

stormy1991 发表于 2015-12-3 00:13:41 | 显示全部楼层
话说lz有消息了吗?我是24号面的还没消息。。。
回复 支持 反对

使用道具 举报

 楼主| nash142857 发表于 2015-12-3 00:31:09 | 显示全部楼层
stormy1991 发表于 2015-12-3 00:13. 1point 3acres 论坛
话说lz有消息了吗?我是24号面的还没消息。。。

没呢。。虚死了
回复 支持 反对

使用道具 举报

stormy1991 发表于 2015-12-3 00:40:46 | 显示全部楼层
.本文原创自1point3acres论坛
我也是,加油加油!马上就有消息了!!!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-3 00:58:32 | 显示全部楼层
存不存在一个timestamp 使得当前timestamp下candidate排名根给的candidates数组吻合  . Waral 博客有更多文章,

补充内容 (2015-12-3 00:59):
还没写完。。这个timestamp必须是要从1开始的吗可以是 比如重 2-5这种吗?
回复 支持 反对

使用道具 举报

 楼主| nash142857 发表于 2015-12-3 01:15:25 | 显示全部楼层
bobzhang2004 发表于 2015-12-3 00:58
存不存在一个timestamp 使得当前timestamp下candidate排名根给的candidates数组吻合  

补充内容 (2015-12- ...

是的。从1开始。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-11 11:18:10 | 显示全部楼层
nash142857 发表于 2015-12-3 01:15. 围观我们@1point 3 acres
是的。从1开始。
. 围观我们@1point 3 acres
这写成代码还是有些复杂啊。。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 14:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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