May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2449|回复: 11
收起左侧

问一道google的design题

[复制链接] |试试Instant~ |关注本帖
cocaptainco 发表于 2016-1-31 07:25:06 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
从朋友那里听来的一道设计题,给定一个闹钟的class,到一定的时间会执行dosth() 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
class alarm{
    const timer t;
    void dosth();
}
让你设计一个 manager的class,能够实现 add一个alarm,并且当时间到alarm设定到的时间的时候trigger它. 问怎么设计。请问大家有啥好的想法?
我想到的是.1point3acres缃
class manager{
   list<alarm> curlist; //sorted
   timer global_timer;
  void check_set();
   void addalarm();
}
addalarm保证按sorted的添加到curlist里面,然后check_set可以是个loop一直checktimer,从头开始找所有的到达时间的alarm trigger它,但是如果多线程就会遇到需要lock的情况,请问大家有没有啥好的想法?

评分

1

查看全部评分

本帖被以下淘专辑推荐:

ryb 发表于 2016-1-31 08:01:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我的想法是单线程,timechecker每次和curlist的第一个element比较,如果时间到了就alarm(),然后把第一个元素poll出来。curlist是一个double linked list
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2016-1-31 08:40:01 | 显示全部楼层
关注一亩三分地微博:
Warald
ryb 发表于 2016-1-31 08:01
我的想法是单线程,timechecker每次和curlist的第一个element比较,如果时间到了就alarm(),然后把第一个元 ...

多谢,如果要考虑poll的时候正好有element加进来,那就是不是就得有个mutex lock?不然可能会出现漏掉某个head。
这题延伸的就问到了多线程加的问题,想到的也就是比如说可以maintain 多个list,这样add和remove就不用同时操作一个,在某一点在combine起来
回复 支持 反对

使用道具 举报

aywizard 发表于 2016-1-31 09:29:41 | 显示全部楼层
你这个是用Java写吗?
void addalarm() 写成 void synchronized addalarm() 不就好了?
回复 支持 反对

使用道具 举报

Teness 发表于 2016-1-31 09:30:57 | 显示全部楼层
我觉得直接设计一个alarm manager的singleton管理吧。然后加thread safe的add/delete就可以了
回复 支持 反对

使用道具 举报

ryb 发表于 2016-1-31 09:48:30 | 显示全部楼层
cocaptainco 发表于 2016-1-30 16:40
多谢,如果要考虑poll的时候正好有element加进来,那就是不是就得有个mutex lock?不然可能会出现漏掉某 ...

恩 如果是java的话可以使用synchronize 关键字:

class Alarm extends Thread{
    private Queue<Integer> curList;
    public void addAlarm(int value){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        synchronized(Alarm.class) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            //insert alarm to queue;
        }
    }
    private void checkAlarm(){
        synchronized(Alarm.class) {
            //check the first element in queue;
        }
    }.鏈枃鍘熷垱鑷1point3acres璁哄潧
    public void run() {
  //checkAlarm on each second
 }
}

这样的话 对queue的操作就是阻塞式的了。楼上说的singleton感觉可有可无吧,毕竟不是这题的考点。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-1 15:50:27 | 显示全部楼层
用一个priority queue存闹钟时间,再用一个map<Time, ArrayList>存每个时间的闹钟
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-10 06:59:12 | 显示全部楼层
surface这个post, 求idea.
. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-7 03:39:16 | 显示全部楼层
没看懂,这个是设置每个线程的sleep时间吗?
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-8 08:58:00 | 显示全部楼层
请问是电面吗?
回复 支持 反对

使用道具 举报

Ulu2005 发表于 2016-3-13 13:02:24 | 显示全部楼层
不是很懂,alarm这个class里的timer怎么用?对Java不是很熟 = =
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-3 06:28:52 | 显示全部楼层
是不是一个priority queue就够了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 05:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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