一亩三分地论坛

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

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

Google 11.09onsite热乎面经

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

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天刚面完,七上八下的,赶紧来地里报第一个全职面经,面成这样就听从上天安排吧. from: 1point3acres.com/bbs
一轮:白人大叔. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
implement一个cache, 这个 cache要求实现get(id), set(i), remove(i), cache的基本特性就是要能够保证out of date 的 cache要不停的被kick out
hashMap + 多线程(当时synchronized不会拼容我在角落默默的哭一会)
写完跟大叔聊了会人生第一轮就这么过去了

二轮:华人姐姐 + 华人哥哥(SHADOW).1point3acres缃
一进来很开心啊第一次在ONSITE遇到ASIAN FACE, 事实上这是我最糟糕的一轮,题目很简单2 SUM CLOEST, 开始写了个暴力的,然后让优化成O(N),继而就SB了,花了十多分钟才憋出来了O(N)解法,感觉俩人都踢我捏把汗
然后没啥时间了就出了个SYstem DESIGN, 很常规的MAIL SYSTEM找TOP K% IP, 提了MAP + HEAP, 在用什么HEAP有了争论, 我说MIN HEAP不断更新TOP就可以, 面试官似乎偏执于为什么我总是在讨论TOP 元素她要的是TOP K%, 我说如果当前某一IP frenquency比TOP大就REPLACE TOP 最后HEAP里的就是TOP K%,最后又说用MAX HEAP不是MIN HEAP。。我心想不对啊。。然后就时间到了

三轮:白人小哥
实现一个围棋盘里是否有 deadend的method(就是如果白子可以把黑子围住或者黑子可以把白子围住就return true),dfs, 做完被指出一个BUG改了, 然后聊了会

四轮:白人小哥(炒鸡帅,发色颜值逆天长腿。。。。)
  leetcode 原题 closest binary search tree value
  设计一个Set类实现 insert, remove, getRandom in O(1) 面经题
  leetcode 原题 encoding and decoding strings
  聊了会, 最后走得时候忍不住夸了下小哥的发色, 问在哪染的, 天生的。。。。

评分

5

查看全部评分

本帖被以下淘专辑推荐:

宝贝忆彼岸 发表于 2015-11-11 14:24:46 | 显示全部楼层
ammmmy11 发表于 2015-11-11 13:13
多线程就是因为考官要求要不停的把过期的CACHE删掉,不只是CALL INSERT或者REMOVE的时候,所以能想到的就 ...

明白了,请问lz能否分享一下多线程的代码?感谢感谢
回复 支持 1 反对 0

使用道具 举报

bill701 发表于 2015-11-11 12:03:37 | 显示全部楼层
楼主的第二题的o(n)咋想的?感觉没有思路啊TAT
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-11 12:19:09 | 显示全部楼层
请教下楼主,实现Cache这个,你用Hashmap+多线程是怎么做的?为什么要多线程?是考官要求?
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-11 12:39:24 | 显示全部楼层
bill701 发表于 2015-11-11 12:03. visit 1point3acres.com for more.
楼主的第二题的o(n)咋想的?感觉没有思路啊TAT
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个应该是sorted。复杂做不到O(n)
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-11-11 12:40):
否则做不到O(n)
回复 支持 反对

使用道具 举报

Ziyan 发表于 2015-11-11 13:06:06 | 显示全部楼层
同问 2 sum closet 给的是sorted的array吗 ?
回复 支持 反对

使用道具 举报

 楼主| ammmmy11 发表于 2015-11-11 13:10:31 | 显示全部楼层
maomaoxiong 发表于 2015-11-11 12:39
这个应该是sorted。复杂做不到O(n)

补充内容 (2015-11-11 12:40):

不好意思说错就是要先SORTED,复杂度是N+Nlogn
回复 支持 反对

使用道具 举报

 楼主| ammmmy11 发表于 2015-11-11 13:13:14 | 显示全部楼层
小柯西 发表于 2015-11-11 12:19
请教下楼主,实现Cache这个,你用Hashmap+多线程是怎么做的?为什么要多线程?是考官要求?
-google 1point3acres
多线程就是因为考官要求要不停的把过期的CACHE删掉,不只是CALL INSERT或者REMOVE的时候,所以能想到的就是BACKGROUND RUN一个线程不断的扫HASHMAP。
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-11 14:17:59 | 显示全部楼层
ammmmy11 发表于 2015-11-11 13:13
多线程就是因为考官要求要不停的把过期的CACHE删掉,不只是CALL INSERT或者REMOVE的时候,所以能想到的就 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
过期cache是值cache在缓存进来的时候设置了一个TLL还是说全局都是同一个TLL,对于每个进来的cache只记录进入cache的时间?
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-11 14:39:02 | 显示全部楼层
我觉得第一轮的这个题坑过很多啊。。。
不知道楼主有没有看过一篇文章叫《A Beautiful Race Condition》,里面专门提到Java的HashMap不能在多线程情况下当作cache。当然文章里提到的情况和楼主碰到的不太一样,有可能楼主写的这个Cache只是供给单线程使用?
如果这个Cache是在多线程环境下使用就会有问题,问题出在HashMap满了之后进行relocate keys的这个过程。所以如果楼主只是控制了后台检查expired keys的线程与cache主线程之间的并发关系,是不够的。
. more info on 1point3acres.com
我个人觉得这题应该先和考官确认,cache是在单线程环境下使用,还是多线程?如果是多线程环境下使用,并且能passively expire(没被access的情况下expire),我想到的合理做法是用异步,写个event loop。每个iteration里检查有没有expired keys,有的话删除,然后继续处理队列里的set/get请求。在这个设计下cache应该是C/S模型。但是这么一设计整个代码量就略大了啊,我不确定45分钟能不能写完。具体设计可以参考Redis。

但如果这题大叔只是要你做设计的话,45分钟是够用的。。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-11 15:29:15 | 显示全部楼层
请问第二轮找top k是指一个mail stream找top k还是固定的一堆mail找top k?
回复 支持 反对

使用道具 举报

 楼主| ammmmy11 发表于 2015-11-11 15:36:55 | 显示全部楼层
小柯西 发表于 2015-11-11 14:17
过期cache是值cache在缓存进来的时候设置了一个TLL还是说全局都是同一个TLL,对于每个进来的cache只记录 ...
. from: 1point3acres.com/bbs
面试官说这是个OPEN question, 只要满足他提出的条件就可以, 所以我就设定了一个全局TLL, 然后面试官有关多线程的问题, 面试官倒是觉得我的想法是workable的,并没有提出你指出的那个问题, 也就是说没有考虑到hashmap满的情况,我猜想他考察的点可能不是在那边,anyway,可能真的是个坑吧。。。。。
回复 支持 反对

使用道具 举报

 楼主| ammmmy11 发表于 2015-11-11 15:43:52 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-11 15:29. Waral 鍗氬鏈夋洿澶氭枃绔,
请问第二轮找top k是指一个mail stream找top k还是固定的一堆mail找top k?

mail stream
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-11 15:55:08 | 显示全部楼层

明白了,那就是用hashmap+minheap?
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-11 20:49:46 | 显示全部楼层
楼主好~想问一下第四轮"设计一个Set类实现 insert, remove, getRandom in O(1) 面经题"是什么哈?不好意思刚来,第一次见到这道题哈~求详解~~另外请问第一题是每个元素进入cache的时候记录一个时间吗?一个back的线程扫描超过时间的就kick吗?嘿嘿 多谢。
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-12 07:01:25 | 显示全部楼层

如果是stream,还真是要用 maxheap。包含所有的元素。去最大的k个。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 08:48:33 | 显示全部楼层
maomaoxiong 发表于 2015-11-12 07:01
如果是stream,还真是要用 maxheap。包含所有的元素。去最大的k个。

请问max heap的思路是什么呢?为什么不能用minHeap来实现呀?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-12 12:45:15 | 显示全部楼层
小柯西 发表于 2015-11-11 14:39
我觉得第一轮的这个题坑过很多啊。。。
不知道楼主有没有看过一篇文章叫《A Beautiful Race Condition》, ...

TTL , not TLL
这个event loop是化多线程为单线程,event based parallel. 确实是redis的设计理念,赞一个。
这样remove expired其实跟单线程是几乎一样的,大大简化代码复杂。不过redis其实也不是纯单线程,在一些计算较重的业务时也是用常规多线程的只是封装的比较好。

这个设计基于的假设是 bound 不在 CPU业务处理上,而是在IO(network I/O or disk I/O). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-12 12:50:35 | 显示全部楼层
yjfox 发表于 2015-11-12 12:45
TTL , not TLL
这个event loop是化多线程为单线程,event based parallel. 确实是redis的设计理念,赞 ...

对啊,因为我们要做的是cache,basic assumption就是不会是一个cpu intensive的程序。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-12 13:00:38 | 显示全部楼层
小柯西 发表于 2015-11-12 12:50
对啊,因为我们要做的是cache,basic assumption就是不会是一个cpu intensive的程序。

求教大神,第一题是一定要用到多线程吗?应该怎么做呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 04:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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