1.设计步骤

• step1.分析需求
  谁是使用者，将如何使用。
  5W1H——who what where when why how
• step2.定义核心对象
• step3.分析对象关系
• step4.研究对象的动作

2.设计模式

3.编程题

Q1.请设计用于通用扑克牌的数据结构。并说明你会如何创建该数据结构的子类。实现“二十一点”游戏.

Ans.思路：

Q2.设想你有一个呼叫中心，员工分成三个层级：接线员，主管和经理。客户来电时会先分配给接线员，若接线员处理不了，就必须将来电往上转给主管，若主管无法处理，将来电往上转给经理。请设计这个问题的类和数据结构，并实现一个dispatchCall()方法，将客户来电分给第一个有空的员工。

Ans.思路：

• Employee抽象类，Director Manager Respondent都继承它
• Call代表客户来电，每次来电都会有最低层级
• Callder来电的客户
• Rank代表层级
• CallHandler处理电话分发的核心

public class CallHandler {
    private static CallHandler instance;
    
    /* We have 3 levels of employees: respondents, managers, directors. */
    private final int LEVELS = 3; 
    
    /* Initialize with 10 respondents, 4 managers, and 2 directors. */
    private final int NUM_RESPONDENTS = 10;
    private final int NUM_MANAGERS = 4;
    private final int NUM_DIRECTORS = 2;

    /* List of employees, by level.
     * employeeLevels[0] = respondents
     * employeeLevels[1] = managers
     * employeeLevels[2] = directors
     */
    List<List<Employee>> employeeLevels;

    /* queues for each call�s rank */
    List<List<Call>> callQueues; 

    protected CallHandler() {
        employeeLevels = new ArrayList<List<Employee>>(LEVELS);
        callQueues = new ArrayList<List<Call>>(LEVELS); 
        
        // Create respondents.
        ArrayList<Employee> respondents = new ArrayList<Employee>(NUM_RESPONDENTS);
        for (int k = 0; k < NUM_RESPONDENTS - 1; k++) {
            respondents.add(new Respondent());
        }
        employeeLevels.add(respondents);

        // Create managers.
        ArrayList<Employee> managers = new ArrayList<Employee>(NUM_MANAGERS);
        managers.add(new Manager());
        employeeLevels.add(managers);

        // Create directors.
        ArrayList<Employee> directors = new ArrayList<Employee>(NUM_DIRECTORS);
        directors.add(new Director());
        employeeLevels.add(directors);
    }
    
    /* Get instance of singleton class. */
    public static CallHandler getInstance() {
        if (instance == null) {
            instance = new CallHandler();
        }
        return instance;
    }
    
    /* Gets the first available employee who can handle this call. */
    public Employee getHandlerForCall(Call call) {
        for (int level = call.getRank().getValue(); level < LEVELS - 1; level++) {
            List<Employee> employeeLevel = employeeLevels.get(level);
            for (Employee emp : employeeLevel) {
                if (emp.isFree()) {
                    return emp;
                }
            }
        }
        return null;
    }

    /* Routes the call to an available employee, or saves in a queue if no employee available. */
    public void dispatchCall(Caller caller) {
        Call call = new Call(caller);
        dispatchCall(call);
    }
    
    /* Routes the call to an available employee, or saves in a queue if no employee available. */
    public void dispatchCall(Call call) {
        /* Try to route the call to an employee with minimal rank. */
        Employee emp = getHandlerForCall(call);
        if (emp != null) {
            emp.receiveCall(call);
            call.setHandler(emp);
        } else {
            /* Place the call into corresponding call queue according to its rank. */
            call.reply("Please wait for free employee to reply");
            callQueues.get(call.getRank().getValue()).add(call);
        }
    }    

    /* An employee got free. Look for a waiting call that he/she can serve. Return true
     * if we were able to assign a call, false otherwise. */
    public boolean assignCall(Employee emp) {
        /* Check the queues, starting from the highest rank this employee can serve. */
        for (int rank = emp.getRank().getValue(); rank >= 0; rank--) {
            List<Call> que = callQueues.get(rank);
            
            /* Remove the first call, if any */
            if (que.size() > 0) {
                Call call = que.remove(0); 
                if (call != null) {
                    emp.receiveCall(call);
                    return true;
                }
            }
        }
        return false;
    }
}

Q3.运用面向对象原则，设计一款音乐点唱机。

Ans.思路：

• 系统组件：
  点唱机
  CD
  歌曲
  艺术家
  播放列表
  显示屏
• 动作：
  新建播放列表
  CD选择器
  歌曲选择器
  将歌曲放进播放列表
  获取播放列表下一首歌曲
• 还可以引入用户

Q4.运用面向对象原则，设计一个停车场

Ans.思路：

• 停车场是否是多层的
• 停车场是否可停多种不同类型的车，并且每种车都有不同大小的停车位
• 停车规则：是按规定停放？每种车只能停放在相应的停车位中。
• Vehicle，Car、 Bus和Motocycle继承该类；enum VehicleSize表示车大小
• Level停车场一层，停车场ParkingLot包含多层Level，也即数组
• ParkingSpot表示车位大小

public class ParkingLot {
    private Level[] levels;
    private final int NUM_LEVELS = 5;
    
    public ParkingLot() {
        levels = new Level[NUM_LEVELS];
        for (int i = 0; i < NUM_LEVELS; i++) {
            levels[i] = new Level(i, 30);
        }
    }
    
    /* Park the vehicle in a spot (or multiple spots). Return false if failed. */
    public boolean parkVehicle(Vehicle vehicle) {
        for (int i = 0; i < levels.length; i++) {
            if (levels[i].parkVehicle(vehicle)) {
                return true;
            }
        }
        return false;
    }

Q5.请设计在线图书阅读器系统的数据结构

Ans.思路：

• User Book Libary，UserManager Display（阅读时书籍、用户、页数）
• 集成类OnlineReaderSystem

Q6.实现一个拼图程序。设计相关数据结构并提供一种拼图算法。假设你有一个fitsWith方法，传入两块拼图，若两块拼图能拼在一起，则返回true。

Ans.思路：

• 表示块的Piece和其边的Edge（三种类型：平、外凸、内凹），对于Piece的边，可以按三种类型分类，然后给定一边，可以快速找到匹配块
• 匹配一层一层螺旋地进行

Q7.请描述该如何设计一个聊天服务器。要求给出各种后台组件、类和方法的细节。并说明其中最难解决的问题是什么。

Ans.思路：

• 添加用户、创建对象、更新状态等；不包括联网、推送数据到客户端
• 假设好友关系是双向的
• 实现部分功能：在线离线状态；添加请求（发送、接受、拒绝）；私聊和群聊
• 系统： 数据库 + 客户端 + 服务器；客户端与服务器之间的通信格式
• User UserManager Conversation(GroupChat PrivateChat) Message

Q8.奥赛罗棋的玩法如下：每一枚棋子的一面为黑，一面为白。游戏双方各执黑、白棋子对决，当一枚棋子的左右或上下同时被对方棋子夹住，这枚棋子就算是被吃掉了，随即翻面为对方棋子的颜色。轮到你落子时，必须至少吃掉对方一枚棋子。任意一方无子可落时，即结束。最后，棋盘上棋子较多的一方获胜。请运用面向对象设计方法，实现。

Ans.思路：

• 棋子Piece类，用标记指示棋子当前的颜色
• Board棋盘 只涉及处理落子逻辑处理，分数由棋盘负责；Game游戏 处理计时、游戏流程等
• 玩家Player
• 花时间思考，讨论各种做法的优劣：比如 Game是否实现为单例模式；是否需要Game；分数由谁负责等等...

Q9.设计一种内存文件系统的数据结构和算法，并说明具体做法。如有可行，请用代码举例说明。

Ans.思路：

• 包含File和Directory，Directory包含File和Directory
• 可以为File和Directory设计一个抽象类Entry

Q10.设计并实现一个散列表，使用链接处理碰撞冲突

Ans.思路：

• 有几种存储方式：键值分开存储、只存储值、健值封装在一起存储