一亩三分地论坛

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

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

google 11.23intern 电面

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

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

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

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

x
1轮 (倒霉地碰到了阿三,听的耳朵难受). Waral 鍗氬鏈夋洿澶氭枃绔,
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.给一系列选举 (某一时间选了某人).. 1point 3acres 璁哄潧
class vote {
     String candiate;
     int timstamp;
}
比如
timestamp    candidate
1      X
2        Y
3       Y.鏈枃鍘熷垱鑷1point3acres璁哄潧
4       Z
5       Z. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
6        Z
然后再给出一个时间搓,问这个时间搓之前哪个选举人得票最高。。(这个function只call一次)
我就遍历数组时间搓 <= given timstamp, 用hashmap 存每个candidate出现count,取最高的返回就好
. From 1point 3acres bbs
follow up, 如果要得到最高的k个呢。。
。。感觉面的跟一面那个一样(用个min_heap维护就好). 鍥磋鎴戜滑@1point 3 acres
.鐣欏璁哄潧-涓浜-涓夊垎鍦
继续follow up, 输入是 Vote [] votes, String []candidates.. . 鍥磋鎴戜滑@1point 3 acres
比如 votes 如上述,candidaes = ['Y','X'],要问存不存在一个timestamp 使得当前timestamp下candidate排名根给的candidates数组吻合
比如candidates = ['Y','X'] 返回就是timestamp 3 (timestamp 2有歧义,Y和X 一样 面试官说不行)
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我的做法是 根据timestamp sort votes first, 用hashmap 维护count 然后将当前timestamp下的hashmap输出到数组 排序跟candidates比较。。
但是写完了就发现自己傻逼了。。每次排序都是mlog(m) (m是candidates的size)....最后跟他说可以用一个bst维护(candidate, count)的pair(comparator根据count 比较). more info on 1point3acres.com
这样插入更新都是log(m), inorder traverse得到排序结果, O(m), 复杂度就少了一个log(m)....

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

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

评分

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
话说lz有消息了吗?我是24号面的还没消息。。。

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

使用道具 举报

stormy1991 发表于 2015-12-3 00:40:46 | 显示全部楼层

我也是,加油加油!马上就有消息了!!!
回复 支持 反对

使用道具 举报

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

补充内容 (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数组吻合  .1point3acres缃

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

是的。从1开始。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-11 11:18:10 | 显示全部楼层

这写成代码还是有些复杂啊。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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