优步系统设计

How to design an excel

根据看到的面经,这题会分两个侧重点来问,当然get和set是最基本的, 1, 重点要处理各个cell之间的dependency,比如cell(1,3)是用公式算出来的cell(1,3)=cell(0,0)+cell(0,1)+cell(0,2),我会用两层哈希表表示整个表格(unordered_map> workbook),然后每个Cell中保存一个unordered_set parents;(所有计算当前Cell需要依赖的cells,上例就是cell(0,0),cell(0,1)和cell(0,2)) 和 unordered_set children; (所有依赖这个Cell通过公式计算出来的cells),每次改变cell的值就要对children和parents做相应的改变; 2, 重点是要处理add或delete一整行或一整列,我会用2d数组,vector> workbook, add的话就直接append,delete行的话就直接erase对应的行,delete列的话就根据列下标,对每行进行erase,好写,但是效率有点低,如果大家有更好的想法,可以一起讨论下。

首先这的想法可能是用一个2darray,但是我们我们不知道初始的大小,所以我们可以用list of list,这样的话还是会要用到多余的空间。即使这些空间没有存数据。所以最好的办法是用HashMap<Integer, HashMap> 来实现,这样的话我们就只会记录写过data的cell了。

还有一个问题是dependency,因为我们在excel里要实现cell(1,3)=cell(0,0)+cell(0,1)+cell(0,2),所以当cell(0,0) 变化的时候,我们要update cell(0,0). 所以每个map需要记录depend他的值(有点像observer pattern里的register,比如说cell(0,0)就要存一个Set,记录所有depend他的Cell (比如Cell(0,1)就要记录Cell(1,3)是他的children,另外要有detection,dependency不能有cycle,这个可以用DFS来做。

另外如果是删除或者添加一整行/列,这个可能就不好做,因为行只要删除对应的那个行就可以,但是列的话只能一个一个删除了。为了加快速度我们可以让每个cell都记录一下他的上面和下面的列(在插入这个新cell的时候update),这样的话删除的话就我们就只需要删除一个linkedlist了,但是这样的话插入就需要遍历所有的行,需要遍历所有的cell。如果我们用TreeMap的话,会更快,但是如果修改或者删除的话就是O(logN)而不是O(1)的复杂度了。

还有follow up问题是如果存其他数据,比如说image,甚至audio或者video的话,我们就只存一个url或者是path,等读取的时候我们再从file system或者CDN里面去读取。

如果这个document还放到网上去共享的话,那当user1在修改某个cell的时候,需要给cell加一个锁,可以用mutex来实现,具体就是在edit的时候要调用mutex.aquire(),操作完以后要调用mutex.release();这样可以保证不会有同时的两个人去access同样的data,当然mutex是multithread用的,而不是网上共享用的。但是同样的道理,我们可以用一个atomic的bit给每个cell来加锁和解锁(比如说这个bit可以放到redis里面的某个key,因为redis是single threaded,所以可以保证所有操作都是atomic的。

Mutex和semaphore的区别,mutex相当于是只有0和1的semaphore,但是要注意一点mutex的加锁和解锁是只能由同一个thread进行的。而semaphore的加和减是可以由不同thread执行,所以mutex用于加锁而semaphore用于协调几个thread的执行。

设计题2: 让我设计一个 Netflix/Spotify, follow up 很多 比如如何限制同一个用户多处登录不能同时看一个资源,如何实现根据用户的网速调整清晰度,怎么热门推荐等等。

对于设计登录系统,首先我们先要设计基本的login系统,首先支持Register/login,就需要一个基本的用户表,如果要支持更复杂一点的登录系统,包括verification,ban,inactive,removed,就需要一个status来记录每个user的状态。

如果还要支持用户可以从多个设备登录,不同的设备会有不同的session id, 但是却有相同的user——id,如果不想要同一个用户可以在多个设备上播放同样的资源,我们就要记录每个用户每个session正在play的资源,然后保证每个session不能play相同的song_ID或者video_id。如果要根据网络速度调整清晰度,我们就需要先测量网络的情况,让client端ping一下服务器,根据收到的ping再向服务器请求不同清晰度的资源。资源本身不应该存在服务器上,可以存在离客户端很近的CDN上。

然后要看播放器的类型,如果是app的话,这个app会需要向DNS server请求我们服务器的地址,然后我们服务器向clientload网页(如果是从浏览器的话,如果是app的话,就不需要load网页,直接去请求源地址就可以了)。然后网页再加载播放器(flash或者HTML5的), 最后再请求源地址,源地址应该是放在附近的CDN上面的,所以很快。

接下来是推荐系统,假设问怎么样设计一个推荐系统,推荐给用户Top10 most frequent played。最简单的用MinHeap,把所有的play过的video或者audio都记录一个frequency,这个记录可以放在内存里(可以是cluster的这种比如redis)这样便于快速的更新和存取。我们希望这个工作放在worker里做,这样可以不影响整个系统的through put。当worker完成了工作以后,就可以Update所有的client,这个工作也可以由一个worker来做,这里我们可以用push也可以用pull,也可以两者相结合,push的话只需要push给在线用户,pull的话对于刚上线的用户来更新最新结果。

外排序就是假设内存不够用,那么我们就将所有的数据分成小块,然后每个小块都可以放进内存里排序,排好了序的这些小块再进行merge sort。就得到了所有数据的排序结果。

还有一个follow up就是因为有很多用户在同时播放视频文件,有可能同时有很多人在看同一个视频,那么这个视频的freq就会有很多+1,怎么样保证所有的+1都记录下来呢?我们可以用一个aggregator,专门记录这种update,等update到了一定的数量或者一定时间做一次batch的update。

3.如何设计一个Uber。
首先登陆系统也是一样的设计。

而作为rider,我们需要找到当前所在的地方的附近所有的drivers,假设drivers的location都是已经存好的放在数据库里并且是不变的,我们要做一个这样的查找也是非常麻烦的。因为即使driver_id, X, Y 都是index过的,我们要查找X在某个limit之内和Y在某个Limit之内,也需要遍历所有的X和Y才能找到我们需要的driver。

有两种解决这个问题的办法,
一种叫做GeoHash
http://www.cnblogs.com/LBSer/p/3310455.html
只要把整个地图分成小块,然后给每个Point of Interest(也就是Driver)assign一个GeoHash,那么相同的GeoHash值就是在附近的。要处理边界问题,我们除了当前location的GeoHash,也处理周围的8个GeoHash的所有POI,这样就cover了边界情况了,另外这些所有的找出来的点我们再重新计算到当前location的距离,然后去掉一些离开比较远的。这样就找到了结果

一种叫做R Tree,其实是一种B Tree在二维上的拓展,我们把每个地图分成多个小方块,然后每个小方块里又有更多的小方块,这种RTree用来处理面或者线的问题更好,处理点的问题用GeoHash更好。
http://blog.csdn.net/v_july_v/article/details/6530142

作为Driver,我们可能需要push 一些Event(比如说有大型的音乐会啊之类的,我们同样也只想push到event附近的driver那里。

How to design a real time system: Driver每4秒update一次位置和速度方向信息,怎么样保证他们都被收到并且存下来呢。我们可以用一个distrubuted message Queue,类似kafka,producer把内容写到messageQueue来,我们的server有很多worker从message Queue里面拿到数据并且分析数据,然后记录下来,供rider来使用。有一个问题是如果我们把所有的这些都放在同一个地方,就会很拥挤,而大部分的Uber的ride都是在同一个城市里的,而且我们要求实时计算,所以delay可能会很严重,所以我们可以把这些数据都分成不同的shard,相同的城市可以用一个shard,这样的好处就是大部分的Uber Ride应该是同城市的,而down side是如果是cross city的话就会比较expensive,还有一点就是小城市和大城市的traffic差距很多,所以我们可以把很多小城市组合在一起。

设计一个black jack的游戏
首先我们要有牌
[language=”java”]
class Card {
int suit;
int value;
boolean face; //facing up or down
}

class Deck {
List cardList;
initDeck();
}

class CardBox {
List cardList;

void Shuffle();
void AppendDeck();
Card popCard();
}

Gamer() {
int gamer_id;
String name;
double money;
List handCards;
Strategy strategy;

void nextStep(); //we could call this makeDecision too, but it only calls corresponding makeDecision in the strategy.
CalculateHandScore();
AddCard();
ShowHand();
}

Player extends Gamer() {
List actionList; //record actions
Strategy playerStrategy = new PlayerStrategy(ActionList); //player strategy is based on the handcard and actionList(including dealer’s handcard);

Fold();
RecordAction(Action);
}

Dealer extends Gamer() {
CardBox cardBox;
int gameState;
Strategy dealerStrategy = new DealerStrategy(handCard); //dealer strategy only based on the handcard.

Reset();
DeclareWinner();
Run();
}

Interface Strategy {
void makeDecision(){};
}

PlayerStrategy implements Strategy() {
//decision should be made base on these
List actionList;
List handCard;
@Override
void makeDecision(){};
}

DealerStrategy implements Strategy() {
List handCard
@Override
void makeDecision(){};
}

Action() {
int id;
int type;
int time;
String info;
}

GameRoom() {
Dealer dealer;
List playerList;

init();
JoinPlayer();
LeavePlayer();
}

[/language]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s