Saturday, August 13, 2016

面试题一 交通灯管理系统 | Flyne



面试题一 交通灯管理系统 | Flyne
在进入正题之前,先要知道面向对象设计中设计类时需要把握的一个重要的经验、原则:谁拥有数据,谁就对外提供操作这些数据的方法,这个经验对于交通灯系统中设计类时相当有帮助。为快速掌握这一设计原则,先来看几个例子:
①、人在黑板上画圆
1
2
3
4
Person,Blackboard,Circle
draw(){
    x,y-->radius  //则该方法位于Circle中
}
②、列车司机紧急刹车
1
2
3
4
Train,Driver
brake(){
    //则该方法位于Train中
}
③ 小球从一根绳子的一段移动到了另一端
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Rope、Ball
Class Rope{
Private Point start;
Private Point end;
Public Rope(Point start, Point end){
    This.start = start; this.end = end;
}
Public Point nextPoint(Point currentPoint){
}
}
Class Ball{
    private Rope rope;
    private Point currentPoint;
    public Ball(Rope rope, Point startPoint){
        this.rope = rope; this.currentPoint = startPoint;
    }
    public void move(){
        currentPoint = rope.nextPoint(currentPoint)
        System.out.println(“小球移动到”+currentPoint);
    }
}
④ 两块石头磨成一把石刀,石刀可以砍树,砍成木材,木材做成椅子
Stone,StoneKnife,Tree,Wood,Chair
StoneKnife sk = KnifeFactory.createKnife(Stone,Stone);
Wood wd = StoneKnife.cut(Tree);
Chair ch = ChairFactory.mkChair(Wood);
了解了面向对象中类的设计原则之后,接下来进入正题,先来看看我们的需求:
模拟实现十字路口的交通灯管理系统逻辑,具体需求如下:
  • 异步随机生成按照各个路线行驶的车辆(多个线程控制)。
    例如:
    由南向而来去往北向的车辆 —- 直行车辆
    由西向而来去往南向的车辆 —- 右转车辆
    由东向而来去往南向的车辆 —- 左转车辆
    。。。
  • 信号灯忽略黄灯,只考虑红灯和绿灯。
  • 应考虑左转车辆控制信号灯,右转车辆不受信号灯控制(抽象为常绿的灯)。
  • 具体信号灯控制逻辑与现实生活中普通交通灯控制逻辑相同,不考虑特殊情况下的控制逻辑。
    注:南北向车辆与东西向车辆交替放行,同方向等待车辆应先放行直行车辆而后放行左转车辆。
  • 每辆车通过路口时间为1秒(提示:可通过线程Sleep的方式模拟)。
  • 随机生成车辆时间间隔以及红绿灯交换时间间隔自定,可以设置。
  • 不要求实现GUI,只考虑系统逻辑实现,可通过Log方式展现程序运行结果。
首先对该系统进行画图分析:
traffic lamp system
整个系统有12条路线(S2N、S2W、E2W、E2S、N2W、N2E、……),每条路线对应一个交通灯,每个灯有红、绿两种状态(因为只有两种状态,此时状态可设计为boolean类型,true为绿灯、false为红灯),当灯为绿时,该灯对应的路线上可以有车子通过。
分析到这儿,不难看出要设计两个类,Lamp和Road。
① Lamp类
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 每个Lamp元素代表一个方向上的灯,总共有12个方向,所有总共有12个Lamp元素。
 * 有如下一些方向上的灯,每两个形成一组,一组灯同时变绿或变红,所以,
 * 程序代码只需要控制每组灯中的一个灯即可:
 * s2n,n2s
 * s2w,n2e
 * e2w,w2e
 * e2s,w2n
 * s2e,n2w(抽象)
 * e2n,w2s(抽象)
 * 上面最后两行的灯是抽象出来的,由于从南向东和从西向北、以及它们的对应方向不受红绿灯的控制,
 * 所以,可以假想它们总是绿灯。
 * @author flyne.org
 *
 */
public enum Lamp {/*每个枚举元素各表示一个方向的控制灯*/
    S2N(false,"N2S","S2W"),S2W(false,"N2E","E2W"),E2W(false,"W2E","E2S"),E2S(false,"W2N","S2N"),
    /*下面元素表示与上面的元素的相反方向的灯,它们的“相反方向灯”和“下一个灯”应忽略不计*/
    N2S(false,null,null),N2E(false,null,null),W2E(false,null,null),W2N(false,null,null),
    /*右拐路线不受红灯的控制,所以,可以假想它们总是绿灯*/
    S2E(true,null,null),E2N(true,null,null),N2W(true,null,null),W2S(true,null,null);
    //由于只考虑红、绿两种状态,此时可用boolean表示灯的状态:true为绿,false为红
    private boolean status;
    //与当前灯同时为绿的对应方向
    private String opposite;
    //当前灯变红时下一个变绿的灯
    private String next;
    private Lamp(boolean status,String opposite,String next){
        this.status = status;
        this.opposite = opposite;
        this.next = next;
    }
    public boolean getStatus(){
        return status;
    }
    public void toGreen(){
        this.status = true;
        System.out.println(name() + " lamp is green,下面总共应该有6个方向能看到汽车穿过!");
        if(opposite != null){
            Lamp.valueOf(opposite).toGreen();
        }
    }
    public void toRed(){
        this.status = false;
        if(opposite != null){
            Lamp.valueOf(opposite).toRed();
        }
    }
    public Lamp next(){
        if(next != null){
            return Lamp.valueOf(next);
        }
        return null;
    }
}
② Road类
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 每个Road对象代表一条路线,总共有12条路线,即系统中总共要产生12个Road实例对象。
 * 每条路线上随机增加新的车辆,增加到一个集合中保存。
 * 每条路线每隔一秒都会检查控制本路线的灯是否为绿,是则将本路线保存车的集合中的第一辆车移除,即表示车穿过了路口。
 * @author flyne.org
 */
public class Road {
    private ArrayList<String> vehicles = new ArrayList<String>();
    private String name;
    public Road(String name) {
        this.name = name;
        //模拟车辆不断随机上路的过程
        ExecutorService pool = Executors.newSingleThreadExecutor();
        pool.execute(new Runnable(){
            public void run() {
                for(int i = 0;i< 1000;i++){
                    try {
                        Thread.sleep((new Random().nextInt(10) + 1) * 1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    vehicles.add(Road.this.name + "_" + i);
                }
            }
        });
        //每隔一秒检查对应的灯是否为绿,是则放行一辆车
        ScheduledExecutorService timer = Executors.newScheduledThreadPool(1);
        timer.scheduleAtFixedRate(
                new Runnable(){
                    public void run() {
                        if(vehicles.size()>0){
                            boolean status = Lamp.valueOf(Road.this.name).getStatus();
                            if(status){
                                System.out.println(vehicles.remove(0) + " is traversing !");
                            }
                        }
                    }
                },
                1,
                1,
                TimeUnit.SECONDS);
    }
}
③ LampController类
除了Lamp和Road类,还应编写一个LampController类控制交通灯(控制当前哪个方向的灯变绿、来回切换的时间……),由于整个系统中只能有一套交通灯控制系统,所以,LampController类最好是设计成单例。
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class LampController {
    private Lamp currentLamp;
    private static LampController lc = new LampController();
    //LampController被设计成单例模式,通过getInstance()返回一个实例
    private LampController(){
        this.currentLamp = Lamp.S2N;
    }
    public static LampController getInstance(){
        return lc;
    }
    //开始运行此交通灯系统
    public void start(){
        //将当前灯变绿
        currentLamp.toGreen();
        //启动一个定时器,每隔10秒将当前灯变红,并将下一个灯变绿。
        ScheduledExecutorService timer = Executors.newScheduledThreadPool(1);
        timer.scheduleAtFixedRate(
                new Runnable(){
                    public void run() {
                        System.out.println("绿灯从" + currentLamp.name() + "-------->切换为" + currentLamp.next().name());
                        currentLamp.toRed();
                        currentLamp = currentLamp.next();
                        currentLamp.toGreen();
                    }
                },
                10,
                10,
                TimeUnit.SECONDS);
    }
}
③ LampController类
除了Lamp和Road类,还应编写一个LampController类控制交通灯(控制当前哪个方向的灯变绿、来回切换的时间……),由于整个系统中只能有一套交通灯控制系统,所以,LampController类最好是设计成单例。
01
02
03
04
05
06
07
08
09
10
11
12
13
14
public class MainClass {
    public static void main(String[] args) {
        /*产生12个方向的路线*/
        String [] directions = new String[]{
            "S2N","S2W","E2W","E2S","N2S","N2E","W2E","W2N","S2E","E2N","N2W","W2S"
        };
        for(int i=0;i<directions.length;i++){
            new Road(directions[i]);
        }
        /*产生整个交通灯系统,并开始运行*/
        LampController.getInstance().start();
    }
}
至此,交通灯系统设计完成(三个核心类:Lamp、Road、LampController)。打印结果如下:
S2N lamp is green,下面总共应该有6个方向能看到汽车穿过!
N2S lamp is green,下面总共应该有6个方向能看到汽车穿过!
E2N_0 is traversing !
S2E_0 is traversing !
S2N_0 is traversing !
E2N_1 is traversing !
N2W_0 is traversing !
S2N_1 is traversing !
N2S_0 is traversing !
W2S_0 is traversing !
S2E_1 is traversing !
S2N_2 is traversing !
绿灯从S2N——–>切换为S2W
S2W lamp is green,下面总共应该有6个方向能看到汽车穿过!
N2E lamp is green,下面总共应该有6个方向能看到汽车穿过!
E2N_2 is traversing !
S2W_0 is traversing !
S2E_2 is traversing !
N2E_0 is traversing !
N2W_1 is traversing !
S2W_1 is traversing !
S2W_2 is traversing !
N2E_1 is traversing !
S2E_3 is traversing !
W2S_1 is traversing !
…………
需要注意的是:绿灯时,车通过马路的方法是放在Road路里面的。正如本文最开始讲的一样,谁拥有数据,谁就提供对这些数据操作的方法,我们是将车辆放在Road实例的一个集合中的。
Read full article from 面试题一 交通灯管理系统 | Flyne

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts