面向对象设计问题要求求职者设计出类和方法，以实现技术问题或描述真实生活中的对象。这类问题可以让面试官洞悉你的编码风格——至少被认为如此。
这些问题并不那么着重于设计模式，而是意在考察你是否懂得如何打造优雅、容易维护的面向对象代码。若在这类问题上表现不佳，面试可能会亮起红灯。
如何解答面向对象设计问
对于面向对象设计问题，要设计的对象可能是真实世界的东西，也可能是某个技术任务，不论如何，我们都能以类似的途径解决。以下解题思路适用于很多问题。
步骤1：处理不明确的地方
面向对象设计（OOD）问题往往会故意放些烟幕弹，意在检验你是武断臆测，还是提出问题以厘清问题。毕竟，开发人员要是没弄清楚自己要开发什么，就直接挽起袖子开始编码，只会浪费公司的财力物力，还可能造成更严重的后果。
碰到面向对象设计问题时，你应该先问清楚，谁是使用者、他们将如何使用。对某些问题，你甚至还要问清楚“5个W1H”，也就是Who（谁）、What（什么）、Where（哪里）、When（何时）、How（如何）、Why（为什么）。
举个例子，假设面试官让你描述咖啡机的面向对象设计。这个问题看似简单明了，其实不然。
这台咖啡机可能是一款工业型机器，设计用来放在大餐厅里，每小时要服务几百位顾客，还要能制作10种不同口味的咖啡。又或者，它可能是设计给老年人使用的简易咖啡机，只要能制作简单的黑咖啡就行。这些用例将大大影响你的设计。
步骤2：定义核心对象
了解我们要设计的东西后，接下来就该思考系统的“核心对象”了。比如，假设要为一家餐馆进行面向对象设计。那么，核心对象可能包括餐桌（Table）、顾客（Guest）、宴席（Party）、订单（Order）、餐点（Meal）、员工（Employee）、服务员（Server）和领班（Host）。
步骤3：分析对象关系
定义出核心对象之后，接下来要分析这些对象之间的关系。其中，哪些对象是其他对象的数据成员？哪个对象继承自别的对象？对象之间是多对多的关系，还是一对多的关系？
比如，在处理餐馆问题时，我们可能会想到以下设计。
宴席包括很多顾客。服务员和领班都继承自员工。每一张餐桌对应一个宴席，但每个宴席可能拥有多张餐桌。每家餐馆有一个领班。
分析对象关系一定要非常小心——我们经常会作出错误假设。比如，哪怕是一张餐桌也可能包含多个“宴席”（在热门餐馆里，“拼桌”很常见）。进行设计时，你应该跟面试官探讨一下，了解你的设计要做到多通用。
步骤4：研究对象的动作
到这一步，你的面向对象设计应该初具雏形了。接下来，该想想对象可执行的关键动作，以及对象之间的关联。你可能会发现自己遗漏了某些对象，这时就需要补全并更新设计。
例如，一个“宴席”对象（由一群顾客组成）走进了“餐馆”，一位“顾客”找“领班”要求一张“餐桌”。“领班”开始查验“预订”（Reservation），若找到记录，便将“宴席”对象领到“餐桌”前。否则，“宴席”对象就要排在列表末尾。等到其他“宴席”对象离开后，有“餐桌”空出来，就可以分配给列表中的“宴席”对象。
设计模式
因为面试官想要考察的是你的能力而不是知识，大部分面试都不会考设计模式。不过，掌握单例设计模式（Singleton）和工厂方法（FactoryMethod）设计模式对面试来说特别有用，所以，接下来我们会作简单介绍。
设计模式太多了，限于篇幅，没办法在本书中一一探讨。你可以挑本专门讨论这个主题的书来研读，这对提高你的软件工程技能会大有裨益。
单例设计模式
单例设计模式确保一个类只有一个实例，并且只能通过类内部方法访问此实例。当你有个“全局”对象，并且只会有一个这种实例时，这个模式特别好用。比如，在实现“餐馆”时，我们可能想让它只有一个“餐馆”实例。
publicclassRestaurant{
privatestaticRestaurant_instance=null;
protectedRestaurant(){...}
publicstaticRestaurantgetInstance(){
if(_instance==null){
_instance=newRestaurant();}
return_instance;}}
工厂方法设计模式
工厂方法提供接口以创建某个类的实例，由子类决定实例化哪个类。实现时，你可以将创建器类（Creator）设计为抽象类型，不为工厂方法提供具体实现；或者，创建器类是实体类，为工厂方法提供具体实现。在这种情况下，工厂方法需要传入参数，代表该实例化哪个类。
publicclassCardGame{
publicstaticCardGamecreateCardGame(GameTypetype){
if(type==GameType.Poker){
returnnewPokerGame();
}elseif(type==GameType.BlackJack){
returnnewBlackJackGame();
}returnnull;}}
面试题目
8.1请设计用于通用扑克牌的数据结构。并说明你会如何创建该数据结构的子类，实现“二十一点”游戏。
8.2设想你有个呼叫中心，员工分成三个层级：接线员、主管和经理。客户来电会先分配给有空的接线员。若接线员处理不了，就必须将来电往上转给主管。若主管没空或是无法处理，则将来电往上转给经理。请设计这个问题的类和数据结构，并实现一个dispatchCall()方法，将客户来电分配给第一个有空的员工。
8.3运用面向对象原则，设计一款音乐点唱机。
8.4运用面向对象原则，设计一个停车场。
8.5请设计在线图书阅读器系统的数据结构。
8.6实现一个拼图程序。设计相关数据结构并提供一种拼图算法。假设你有一个fitsWith方法，传入两块拼图，若两块拼图能拼在一起，则返回true。
8.7请描述该如何设计一个聊天服务器。要求给出各种后台组件、类和方法的细节，并说明其中最难解决的问题会是什么。
8.8“奥赛罗棋”（黑白棋）的玩法如下：每一枚棋子的一面为白，一面为黑。游戏双方各执黑、白棋子对决，当一枚棋子的左右或上下同时被对方棋子夹住，这枚棋子就算是被吃掉了，随即翻面为对方棋子的颜色。轮到你落子时，必须至少吃掉对方一枚棋子。任意一方无子可落时，游戏即告结束。最后，棋盘上棋子较多的一方获胜。请运用面向对象设计方法，实现“奥赛罗棋”。
8.9设计一种内存文件系统（in-memoryfilesystem）的数据结构和算法，并说明具体做法。如有可行，请用代码举例说明。
8.10设计并实现一个散列表，使用链接（即链表）处理碰撞冲突。
8.9递归和动态规划
尽管递归问题五花八门，但题型大都类似。一个问题是不是递归的，就看它能不能分解为子问题进行求解。
当你听到问题是这么开头的：“设计一个算法，计算第n个……”，“编写代码列出前n个……”，“实现一个方法，计算所有……”等等，那么，这基本上就是一个递归问题。
熟能生巧！练习得越多，就越容易识别递归问题。
解决之道
递归的解法，根据定义，就是从较小的子问题逐渐逼近原始问题。很多时候，只要在f(n-1)的解法中加入、移除某些东西或者稍作修改就能算出f(n)。而在其他情况下，答案可能更为复杂
你应该双管齐下，自下而上和自上而下两种递归解法都要考虑。简单构造法对递归问题就很奏效。
自下而上的递归
自下而上的递归往往最为直观。首先要知道如何解决简单情况下的问题，比如，只有一个元素的列表，找出有两个、三个元素的列表的解法，依此类推。这种解法的关键在于，如何从先前解出来的答案，构建出后续情况的答案。
动态规划
在面试中，动态规划（Dynamicprogramming，DP）问题很少问及，原因很简单，短短45分钟的面试要解决这类问题实在太难了。就算是出色的求职者，面对这类问题通常也难有上佳表现，因此动态规划问题不适合用来评估求职者。
要是不走运，碰到了动态规划问题，你可以用跟递归问题差不多的解决方法来处理。区别在于，中间结果要“缓存”起来，以备后续使用。
动态规划法简单示例：斐波那契数列
下面举个动态规划法的简单例子。想象一下，面试官要求你实现一个程序，生成斐波纳契数列的第n项数字。听起来很简单，对吧？
intfibonacci(inti){
if(i==0)return0;
if(i==1)return1;
returnfibonacci(i-1)+fibonacci(i-2);}
这个函数要用多长时间执行？计算斐波那契数列第n项要先算出前面的n-1项。而每次函数调用又包含两次递归调用，也就是说，执行时间为O(2n)。下面的图表显示在普通台式机上的执行结果，执行时间呈指数级上升。
只要对上面的函数稍作修改，就可以将时间复杂度优化为O(N)。具体做法就是将每次调用fibonacci(i)的结果“缓存”起来。
int[]fib=newint[max];
intfibonacci(inti){
if(i==0)return0;
if(i==1)return1;
if(fib!=0)returnfib;//返回先前缓存的结果
fib=fibonacci(i-1)+fibonacci(i-2);//缓存结果
returnfib;}
在普通电脑上，之前的递归版本生成第50项斐波那契数用时可能超过一分钟，而动态规划方法只需几毫秒就能产生第项斐波那契数。当然，若采用上面这段代码，int型变量很快就会溢出。
如你所见，动态规划法没什么好怕的。只不过要缓存中间结果，比递归稍稍复杂些。解决这类问题，有个好办法就是先以一般的递归法实现，然后添加缓存部分。
递归和迭代解法
递归算法的空间效率很低。每次递归调用都会在栈上增加一层，也就是说，若算法包含O(n)次递归调用，就要使用O(n)内存。不得了！
所有的递归代码都能改为迭代式的实现，尽管有时候这么做代码会复杂得多。在一头扎入递归代码之前，先问问自己用迭代方式实现会有多难，并与面试官讨论不同解法的优劣差异。
9.1有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一个方法，计算小孩有多少种上楼梯的方式。
9.2设想有个机器人坐在X×Y网格的左上角，只能向右、向下移动。机器人从(0,0)到(X,Y)有多少种走法？
进阶假设有些点为“禁区”，机器人不能踏足。设计一种算法，找出一条路径，让机器人从左上角移动到右下角。
9.3在数组A[0...n-1]中，有所谓的魔术索引，满足条件A=i。给定一个有序整数数组，元素值各不相同，编写一个方法，在数组A中找出一个魔术索引，若存在的话。
进阶如果数组元素有重复值，又该如何处理？
9.4编写一个方法，返回某集合的所有子集。
9.5编写一个方法，确定某字符串的所有排列组合。
9.6实现一种算法，打印n对括号的全部有效组合（即左右括号正确配对）。示例输入：3输出：((())),(()()),(())(),()(()),()()()
9.7编写函数，实现许多图片编辑软件都支持的“填充颜色”功能。给定一个屏幕（以二维数组表示，元素为颜色值）、一个点和一个新的颜色值，将新颜色值填入这个点的周围区域，直到原来的颜色值全都改变。
9.8给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。
9.9设计一种算法，打印八皇后在8×8棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
9.10给你一堆n个箱子，箱子宽wi、高hi、深di。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一个方法，搭出最高的一堆箱子，箱堆的高度为每个箱子高度的总和。
9.11给定一个布尔表达式，由0、1、、
和^等符号组成，以及一个想要的布尔结果result，实现一个函数，算出有几种括号的放法可使该表达式得出result值。示例表达式：1^0
0
1期望结果：false(0)输出：1^((0
0)
1)和1^(0
(0
1))两种方式