传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2933|回复: 13
收起左侧

Twitter 电面

[复制链接] |试试Instant~ |关注本帖
fordreamzju 发表于 2015-9-12 05:38:58 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Twitter - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
前几天面了Twitter 目测是悲剧了。题目比较生疏,希望有大神讨论下最优解。
自己设计一个data structure,支持以下两个函数:
void set(String event, long timestamp);.1point3acres缃
int getCount(Granularity, String event, long startTime, long endTime);
就是说我们首先记录很多个事件发生的时间,存在某种Data structure里面,然后通过getCount这个function我们可以计算出在某段时间间隔内[startTime, endTime],某个事件发生了多少次。同时这个函数还支持多种Granularity,包括Week, day, hour.
简单来讲 我觉得就是要实现一个支持range search的map。现场讲了用<String, linkedList> 和 <String, BST>的思路,最后让写了BST。用Java写BST我也是醉了。尤其在我写的过程中面试官不停地追问我如果数据量很大,List放不下,查询时间很慢等等要怎么办。总之最后没写完,又瞎说了说用TreeMap类的思路balabala。. Waral 鍗氬鏈夋洿澶氭枃绔,

怒求RP。

评分

3

查看全部评分

Linzertorte 发表于 2015-9-12 06:00:09 | 显示全部楼层
range search的话, C++ map本身就是一个红黑树,有lower_bound, upper_bound
回复 支持 1 反对 0

使用道具 举报

Linzertorte 发表于 2015-9-12 06:01:06 | 显示全部楼层
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-9-12 08:27:26 | 显示全部楼层
是不是不让直接用TreeMap呢?
回复 支持 反对

使用道具 举报

emmarong 发表于 2015-9-22 08:06:58 | 显示全部楼层
请问楼主面的是哪个职位啊,感觉题目很偏啊,是不是面试官问的和面的职位相关啊?

补充内容 (2015-9-22 08:09):
祝楼主顺利通过电面!
回复 支持 反对

使用道具 举报

douya 发表于 2015-9-28 02:00:13 | 显示全部楼层
谢谢楼主分享,新题目啊。楼主过了吗?twitter full time要几轮电面啊?
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-9-28 04:06:10 | 显示全部楼层
Linzertorte 发表于 2015-9-12 06:00
range search的话, C++ map本身就是一个红黑树,有lower_bound, upper_bound

大神!!!!!!!!!!!!!
回复 支持 反对

使用道具 举报

lianguasth 发表于 2015-9-30 09:29:35 | 显示全部楼层
这种不是应该说B-Tree么?多的话直接放到硬盘里。。虽然严重怀疑当场写一个B-Tree是几个意思
回复 支持 反对

使用道具 举报

lianguasth 发表于 2015-9-30 22:10:32 | 显示全部楼层
查了一下似乎是用 hashMap<event, TreeMap>
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-7 09:48:39 | 显示全部楼层
我会用segment tree,每个node维护一个hashtable,key是某种事件,value是出现的次数。但是用segment tree坏处是,不容易随着时间线向右扩展。所谓的不同granularity,也就是说最底层node维护的时间大小不同,要么是一个小时的数据,要么是一周的数据,查询的时候精度也只需要到那个地步。但是segment tree坏处在于不容易随着时间线扩展,但是不光是segment tree,其他的bst之类的也不好扩展吧。
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-19 14:02:47 | 显示全部楼层
returning 发表于 2015-12-7 09:48
我会用segment tree,每个node维护一个hashtable,key是某种事件,value是出现的次数。但是用segment tree ...

求问意思是按照时间分线段么?那时间慢慢增加。。。树要怎么变形= =
回复 支持 反对

使用道具 举报

returning 发表于 2016-1-24 14:30:55 | 显示全部楼层
sevensevens 发表于 2016-1-19 14:02
求问意思是按照时间分线段么?那时间慢慢增加。。。树要怎么变形= =
-google 1point3acres
准确的说应该是上面那个人说的b tree, 不是segement tree
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-26 06:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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