一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1236|回复: 2
收起左侧

Google 11.23 intern 面经

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

2015(10-12月) 码农类 硕士 实习@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步骤应该更好).. visit 1point3acres.com for more.
然后follow-up 问我query太多怎么办,我说可以把query存在HDFS 用map-reduce去做,(然后花了15分钟问我map reduce细节应该咋做。。真是给阿三跪了)...

2轮(应该是个白人大叔)
1.给一系列选举 (某一时间选了某人).. From 1point 3acres bbs
class vote {
     String candiate;
     int timstamp;. 鍥磋鎴戜滑@1point 3 acres
}
比如
timestamp    candidate. From 1point 3acres bbs
1      X
2        Y.鐣欏璁哄潧-涓浜-涓夊垎鍦
3       Y
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 4       Z. 鍥磋鎴戜滑@1point 3 acres
5       Z
6        Z. From 1point 3acres bbs
然后再给出一个时间搓,问这个时间搓之前哪个选举人得票最高。。(这个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 一样 面试官说不行). from: 1point3acres.com/bbs

我的做法是 根据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璁哄潧

 楼主| nash142857 发表于 2015-11-25 04:20:13 | 显示全部楼层
(为啥要审核的。。。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-12 08:58:01 | 显示全部楼层
linkedList是自己定义Node来一个linked list?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-14 16:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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