一亩三分地论坛

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

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

问一道google的design题

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

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

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

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

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| cocaptainco 发表于 2016-1-31 08:40:01 | 显示全部楼层
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写吗? . 1point3acres.com/bbs
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. 1point3acres.com/bbs
多谢,如果要考虑poll的时候正好有element加进来,那就是不是就得有个mutex lock?不然可能会出现漏掉某 ...

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

class Alarm extends Thread{. Waral 鍗氬鏈夋洿澶氭枃绔,
    private Queue<Integer> curList;
    public void addAlarm(int value){. more info on 1point3acres.com
        synchronized(Alarm.class) {
            //insert alarm to queue;
        }
    }
    private void checkAlarm(){
        synchronized(Alarm.class) {
            //check the first element in queue;-google 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.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

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就够了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 11:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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