一亩三分地论坛

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

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

Dropbox电面 09/16

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

2016(7-9月) 码农类 硕士 全职@Dropbox - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚面完的Dropbox电面,对面是个美国小哥
上来他先自我介绍一下,然后就直接开始做题了。。。没给我自我介绍的机会。。。
-google 1point3acres
题目是hit counter,我刷过,但是记得不太清楚最优解法的细节了,于是问了下
1. 一秒钟可能hit多次吗?
2. 要不要考虑多线程情况.鏈枃鍘熷垱鑷1point3acres璁哄潧

先说了一个naive的存time再二分查找边界的。

小哥说能不能再给力一点啊,我就边想边说了下常数存储的方法。小哥对我的解法(和演技)比较满意,然后很快就写完了。

小哥继续问怎么test,我说了几个case,不过需要sleep,小哥表示你在逗我吗,unit test你sleep 5分钟?我说那你就fake一下timestamp嘛,要么传进去,要么用mockito fake一下。小哥说OK
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
小哥继续问那现在我们搞multi-threading,怎么办
. visit 1point3acres.com for more.
我说
1. 加全局锁,两个方法加上synchronized
2. event queue。封装方法调用,把命令放到queue上,然后server在另一端不断地取task执行,这样解耦了consumer和producer,异步化方法调用. from: 1point3acres.com/bbs
3. ConcurrentHashMap来代替数组,因为log是读少写多,只需要在getHit的时候加锁. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
4. 如果只有固定的几个admin,那就固定给一个ConcurrentHashMap,用admin ID当key,内层就可以HashMap了,因为admin们不会影响别人
5. 在4的基础上,如果admin并不是一定要全局的数据(可以只做些sampling),那可以用ThreadLocal,完全抛弃锁。
. From 1point 3acres bbs

小哥说OK,挺好的。你问我问题吧。

后面没啥了,不过小哥提到他以前是一个startup的,被Dropbox收购了,他一开始很迷茫。。。我表示感同身受。。。

评分

2

查看全部评分

RobinSwift 发表于 2016-9-22 17:58:20 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

RobinSwift 发表于 2016-9-22 18:02:01 | 显示全部楼层
"event queue。封装方法调用,把命令放到queue上"
Could you help explaining what is event queue, and how to encapsulate? What does it mean of "把命令放到queue上"?

补充内容 (2016-9-22 18:36):
Do you mean for the scenario of how the admin use it? So on the UI, you will use event queue for multiple admins?
回复 支持 反对

使用道具 举报

howeflguap 发表于 2016-9-27 04:36:18 | 显示全部楼层
请问楼主对你提出的每个多线程解法都需要写出可以跑通测试的完整解吗?那时间岂不是非常紧张?
回复 支持 反对

使用道具 举报

 楼主| wcyz666 发表于 2016-9-27 04:41:19 | 显示全部楼层
howeflguap 发表于 2016-9-27 04:36
请问楼主对你提出的每个多线程解法都需要写出可以跑通测试的完整解吗?那时间岂不是非常紧张?

说说想法就可以了。不过这些应该也都不难实现

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| wcyz666 发表于 2016-9-27 04:42:41 | 显示全部楼层
RobinSwift 发表于 2016-9-22 18:02. from: 1point3acres.com/bbs
"event queue。封装方法调用,把命令放到queue上"
Could you help explaining what is event queue, and h ...

就是相当于producer想log就放一条信息在queue上,consumer就是不断取消息执行
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-30 11:16:35 | 显示全部楼层
请问这题怎么用O1啊,我看网上的LEETCODE答案都是用一个QUEUE,不段POLL前面的,把超过5分钟的都POLL出去,然后看有多少个
回复 支持 反对

使用道具 举报

 楼主| wcyz666 发表于 2016-9-30 11:25:21 | 显示全部楼层
liurudahai 发表于 2016-9-30 11:16
请问这题怎么用O1啊,我看网上的LEETCODE答案都是用一个QUEUE,不段POLL前面的,把超过5分钟的都POLL出去, ...

Leetcode高票就是O(1),用一个长度为300的数组
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-10-17 09:16:09 | 显示全部楼层
liurudahai 发表于 2016-9-30 11:16
请问这题怎么用O1啊,我看网上的LEETCODE答案都是用一个QUEUE,不段POLL前面的,把超过5分钟的都POLL出去, ...

用queue的话 平均的也是o1吧
回复 支持 反对

使用道具 举报

howeflguap 发表于 2016-10-18 02:49:28 | 显示全部楼层
shiloh00 发表于 2016-10-17 09:16
用queue的话 平均的也是o1吧

单线程同步的话取决于每一秒钟允许点击的次数?这个数字没有上界的话应该不能算常数复杂度。异步的话需要讨论消费者处理过程中失败导致申请必须被重新压回消息队列的情况(并且这种情况下不能轻易丢掉五分钟前的元素,否则二次申请的结果会出错),仅当单机失败率有确定的上界,而且消费者数量上限已知(自动向上扩展的不就不行),才能算是常数时间复杂度。丢盒子的面试官引导的讨论一层一层递进还挺深入的,可能会看佛楼阿普最终挂在第几层讨论上来决定是否通过以及录取级别。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 21:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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