一亩三分地论坛

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

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

Google Pittsburgh Onsite 面经

[复制链接] |试试Instant~ |关注本帖
oldady 发表于 2016-5-17 03:21:18 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
匹村04-12面经. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

1. 给一个list[string], 一个query string,要求返回一个list[string]包括所有match的string
match rule: 非常confused, 大概意思是看大写开头的substring部分match,看例子吧:
AbCd和AbcdeCdef:结果MATCH,因为Ab和Cd都分别match了
AbCd和AzCde:不MATCH,因为Ab和Az 不match. from: 1point3acres.com/bbs
AbCd和AbdZzCdef:不MATCH,因为尽管Ab, Cd是match但是中间Zz多出来了不符合

总之这题弄清楚rule搞了好久感觉这题没有well designed或者我领悟能力太弱了.

2. 假设连续接收一个股票的价格,输入形式是tuple(timestamp, price), 其中如果price有可能是null表示要撤销上这个timestamp之前的tuple
要求设计一个算法维护三个值max price / min price / recent price

例子:
(1, 2)
(2, 5)
(1, null)
(5, 3)

结果:
min price: 3
max price: 5
recent price: 3

3. 给两个collection of intervals, A 和 B, 返回the difference interval collection (i.e. A - B)
前半部分思路参见leetcode 56 merge intervals

4. 貌似见过的题目, real time的datasets (time, value), 问如何找outliers (让写一下通过找average / median的方法)

也没怎么follow up就一人一道题,感觉难度在看过的面经里算中下的样子
求人品求祝福,希望大家都一切顺利!


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

2

查看全部评分

gmcather 发表于 2016-5-20 19:53:16 | 显示全部楼层
handsomecool 发表于 2016-5-20 11:25
具体怎么写? 要支持删除哦

三栈,Stack_A存储当前所有的值,Stack_B维护最大值,保证栈内元素递增,Stack_C维护最小值,保证栈内元素递减。当push一个元素时,除了push into Stack_A之外,满足特定条件时,还需要push into Stack_B和Stack_C, 如果元素比Stack_B的栈顶元素大,就直接push Stack_B,否则,弹栈直至栈为空或上述条件破坏。Stack_C类似的思想。 当Pop一个元素时,需要判断Stack_A的值,是不是当前最大值或者最小值,从而确定Stack_B和Stack_C有没有必要弹栈。
回复 支持 1 反对 1

使用道具 举报

gmcather 发表于 2016-5-20 19:54:02 | 显示全部楼层
handsomecool 发表于 2016-5-20 11:25
. 1point3acres.com/bbs具体怎么写? 要支持删除哦

其实,具体做法可以参考leetcode上的Min Stack
回复 支持 1 反对 1

使用道具 举报

 楼主| oldady 发表于 2016-5-20 23:57:16 | 显示全部楼层
关于第二题我觉得还是要结合stock market这个特定场景分析query pattern设计,不能只看算法复杂度吧-google 1point3acres
感觉比较合理的解法应该是结合hashmap + min/max heap + lazy style,大概想法是:

因为stock price肯定是real time stream吧,所以new price的insert操作肯定不能慢,像之前有人说用几个heap那对于每一个new price的insert/delete的操作实在是太慢了,real-time是不能满足的。所以这部分我觉得用hashmap还是很合理的,可以保证速度。其次因为min / max / recent price其实有点像OLAP吧有点delay也没事,不过只用hash map的话需要O(N)也太慢了,还是需要维护几个heap来缩小到O(logN)的。关键是,这些heap不需要那么大吧,小一点保证当天stock market的所有撤销操作可以囊括就可以了,然后当天晚上刷新这些heap保证第二天所有的null操作还是可以囊括就可以。. 1point3acres.com/bbs
. more info on 1point3acres.com
具体的实现:. From 1point 3acres bbs
主要hashmap维护所有历史股票价格,保证real-time(类似于in-memory database了),insert/delete直接操作在这个hash map
三个heap维护 min/max/recent price,但是heap size不要是所有数据,k就行保证够当天所有的撤销操作(k << N). from: 1point3acres.com/bbs
一个比较小的hashmap,用来记录当天撤销操作
其中heap和小的hashmap配合用来查询min/max/recent price, lazy style,所以heap中的node可能是已经撤销了无效的, 差不多zombie node吧

复杂度分析,
insert: O(1) + O(log K) 插入大的hashmap和几个heap,相当于O(1)了
null操作相当于delete:O(1) + O(1) 大hashmap和小hashmap
max / min / recent price查询操作:O(logK) 注意每个heap node要看下是否在小hash map里已经被记录要撤销,如果是直接discard

price market关门了晚上清理heap和小hash map,把zombie node全删了,然后扫描所有历史价格,前K个放入heap,复杂度O(logK * N)或者O(N)反正都很慢,但是在晚上无所谓了
回复 支持 1 反对 0

使用道具 举报

gmcather 发表于 2016-5-20 11:09:17 | 显示全部楼层
第二题,正解是Min/Max Stack, 为啥没人说这个呢
回复 支持 0 反对 1

使用道具 举报

 楼主| oldady 发表于 2016-5-17 03:35:46 | 显示全部楼层
纠正一下是05-12面的new grad
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-17 03:41:15 | 显示全部楼层
第四个,用俩heap那种经典解法找median?
回复 支持 反对

使用道具 举报

 楼主| oldady 发表于 2016-5-17 03:46:15 | 显示全部楼层
jiebour 发表于 2016-5-17 03:41. from: 1point3acres.com/bbs
第四个,用俩heap那种经典解法找median?

不太清楚你说的heap方法是哪种,我面试的时候上来说最简单的就是sort以后找中间数,面试官就直接让我写下最简单的了……后面也没继续follow up。用quick select的方法找中位数更快吧,这题之后没怎么讨论
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-17 03:57:30 | 显示全部楼层
第二题一个hashmap就够了吧,然后根据value需要定义不同的comparator,最近的就sort key的值找最大的.1point3acres缃

补充内容 (2016-5-17 04:01):
时间复杂度有点高,这样就搞两个max heap和一个min heap, 每次操作的复杂度可降到O(1),求问楼主是这样做的吗?
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-17 04:00:05 | 显示全部楼层
oldady 发表于 2016-5-17 03:46. 1point 3acres 璁哄潧
不太清楚你说的heap方法是哪种,我面试的时候上来说最简单的就是sort以后找中间数,面试官就直接让我写下 ...

不是说real time吗?意思说数据持续的过来?持续的更新?
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-17 04:02:07 | 显示全部楼层
第三个的话,假设A拍好序了,那么写个function,输入是A和一个interval,输出是A减去这个interval之后的结果;然后loopB,对B的每个interval调用这个function,楼主觉得如何?. From 1point 3acres bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-5-17 04:03):
一点点优化的话,就是那个function每次用binary search找应该删的位置
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-17 04:03:11 | 显示全部楼层
jiebour 发表于 2016-5-17 04:00
不是说real time吗?意思说数据持续的过来?持续的更新?

这题lc原题啊,俩heap,一大一小那道
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-17 04:04:09 | 显示全部楼层
hidden_track 发表于 2016-5-17 04:03
这题lc原题啊,俩heap,一大一小那道
. From 1point 3acres bbs
对哒。。。。。
回复 支持 反对

使用道具 举报

 楼主| oldady 发表于 2016-5-17 04:05:01 | 显示全部楼层
jiebour 发表于 2016-5-17 04:00
不是说real time吗?意思说数据持续的过来?持续的更新?

噢忘记说了,题目是有一个sliding window size的,只关注最近这一段时间内的数据
回复 支持 反对

使用道具 举报

 楼主| oldady 发表于 2016-5-17 04:09:39 | 显示全部楼层
hidden_track 发表于 2016-5-17 03:57
第二题一个hashmap就够了吧,然后根据value需要定义不同的comparator,最近的就sort key的值找最大的

补充 ...
-google 1point3acres
这题我觉得应该是考察trade off的能力看不同query pattern吧,毕竟不知道null操作占比多不多。我最开始说用priority queue后来发现直接hash map就够了,这样非null的操作都是O(1),null的操作一般情况下也是O(1), 如果不幸撤销的正好是min/max/recent中的一个就需要重新扫描整个hash table就要O(n)了但是相信这种操作很少
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-17 04:13:44 | 显示全部楼层
oldady 发表于 2016-5-17 04:09
这题我觉得应该是考察trade off的能力看不同query pattern吧,毕竟不知道null操作占比多不多。我最开始说 ...

每次新来一个值不要sort一边吗?复杂度应该是nlogn吧
回复 支持 反对

使用道具 举报

 楼主| oldady 发表于 2016-5-17 04:14:37 | 显示全部楼层
jiebour 发表于 2016-5-17 04:02
第三个的话,假设A拍好序了,那么写个function,输入是A和一个interval,输出是A减去这个interval之后的结 ...

没仔细想,但这样似乎很繁琐。我是排序以后直接从左到右扫A / B,可能出现overlapping的情况一共有4种case(没有olverlapping的情况是2种),每一种分别作相应处理,感觉面试官似乎要的是case by case的分析能力
回复 支持 反对

使用道具 举报

 楼主| oldady 发表于 2016-5-17 04:17:53 | 显示全部楼层
hidden_track 发表于 2016-5-17 04:13
每次新来一个值不要sort一边吗?复杂度应该是nlogn吧

新来的tuple直接看当前的state: min / max / recent需不需要更新就信,O(1)
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-17 04:24:16 | 显示全部楼层
oldady 发表于 2016-5-17 04:05
噢忘记说了,题目是有一个sliding window size的,只关注最近这一段时间内的数据

貌似还是可以开俩heap,只是复杂度变成了N*K
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-17 04:26:11 | 显示全部楼层
oldady 发表于 2016-5-17 04:14
没仔细想,但这样似乎很繁琐。我是排序以后直接从左到右扫A / B,可能出现overlapping的情况一共有4种cas ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
A/B是啥意思?
另外排序是AB都拍?还是直拍一个?
回复 支持 反对

使用道具 举报

 楼主| oldady 发表于 2016-5-17 04:39:41 | 显示全部楼层
jiebour 发表于 2016-5-17 04:26
A/B是啥意思?. from: 1point3acres.com/bbs
另外排序是AB都拍?还是直拍一个?

A和B分别预处理sort + merge以后

while (iA < len(A) and iB < len(B)):
    分别处理各种A[iA] 和 B[iB]的overlapping case(4种)或者没有overlapping的case(2种). From 1point 3acres bbs
while loop ends后如果A还没走完就全要了,B还没走完就全忽略了
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-17 04:55:49 | 显示全部楼层
oldady 发表于 2016-5-17 04:39. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
A和B分别预处理sort + merge以后

while (iA < len(A) and iB < len(B)):

sounds awesome!!!
回复 支持 反对

使用道具 举报

simonwoo 发表于 2016-5-17 17:09:16 | 显示全部楼层
oldady 发表于 2016-5-17 04:09
. From 1point 3acres bbs这题我觉得应该是考察trade off的能力看不同query pattern吧,毕竟不知道null操作占比多不多。我最开始说 ...

null是撤销一个还是很多个,如果是很多个的话怎么会O(1),应该是O(N)吧?

我觉得这题最麻烦就是这个null操作
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-17 19:39:05 | 显示全部楼层
楼主啥叫diff bwt intervals ? 比如 A: (1,2) (5,6) (9,10)  B: (1,6)  then diff = (3,4) ?. more info on 1point3acres.com

补充内容 (2016-5-17 19:42):
懂了, diff应该是 (3,4) (9,10)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 17:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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