OOD

OK家人们，明天就是微软面试，所以我今天开始看OOD。我做得对吗。

写在前面：怎么做OOD

题面基本上就是让你design一个小东西，然后具体的specs要你自己问出来。

比如说让设计一个Restaurant。那你得问：能堂食吗？能外卖吗？etc.

假设仅限堂食。

列出核心对象

餐厅人：Owner, Waiter

客户：Guest, Party(一群Guest)

餐厅物：Table, Meal, (Reservation?)

客户物：Order

审查对象间关系

继承？比如Owner和Waiter是不是可以抽象成Employee？

一对多？一对一？比如一个Table只能有一个Party，但一个Party可以在多张Table？

从Use-Case入手测试

比如一个Party到达restaurant，其中一个Guest问有没有多的Table，Owner开始在Reservation找是不是所有Table都booked，如果不是就assign一个空桌子。然后开始点餐(Order) blah blah。

Puzzle

类似于传统的拼图。假设已经给定了一个fitsWith()函数，可以check两条边是不是fit。

首先做一些假设（或者可以问面试者）：有三种边（平的，凸的，凹的）？保证有解？

然后列出核心对象：

• 首先是Edge，有三种边。可以用一个enum表示。
• 然后是Piece，有四个Edge。可以用hashmap存每个方向上edge的类型。
• 最后是Puzzle。储存所有的Pieces。

这边解拼图的话就一个个试，从左上角一列一列把pieces填进去。每个新填入的piece都要match和它相邻的pieces的对应edge。其实不是很efficient，但也无所谓了。

Circular Array

这个和61b的arraylist实现有点像，但这里要支持rotate(int shiftRight)操作。该操作会让数组中所有元素向右平移shiftRight个单位。

其实只要维护一个“数组开始”的index就可以。

Chat Server

微软面试题：Deck of Cards

微软面试题：设计推特图片的缓存系统

设计cache，基本就是hashmap+eviction。可以参照LRU。