10.2 How would you design the data structures for a very large social network like Facebook or Linkedln? Describe how you would design an algorithm to show the connection, or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You).
这道题让我们实现大型社交网站的数据结构，首先用户类Person需要包含好友和其他的一些信息，而且大型网站一般可能会有上百万的用户，我们一般不可能把所有的数据都存在一台机器上，所以我们在查找好友时，需要先查找好友所在的机器，再在机器上查询好友，每个好友或机器都有自己的编号，为了快速查找，均使用了哈希表来建立映射，参见代码如下：
class Person { public: Person(int id): _personID(id) {} int getID() { return _personID; } void addFriend(int id) { _friendIDs.push_back(id); } private: vector<int> _friendIDs; int _personID; }; class Machine { public: unordered_map<int, Person*> _persons; int _machineID; Person* getPersonWithID(int personID) { if (_persons.find(personID) == _persons.end()) { return nullptr; } return _persons[personID]; } }; class Server { public: unordered_map<int, Machine*> _machines; unordered_map<int, int> _personToMachineMap; Machine* getMatchineWithId(int machineID) { if (_machines.find(machineID) == _machines.end()) { return nullptr; } return _machines[machineID]; } int getMachineIDForUser(int personID) { if (_personToMachineMap.find(personID) == _personToMachineMap.end()) { return -1; } return _personToMachineMap[personID]; } Person* getPersonWithID(int personID) { if (_personToMachineMap.find(personID) == _personToMachineMap.end()) { return nullptr; } int machineID = _personToMachineMap[personID]; Machine *machine = getMatchineWithId(machineID); if (machine == nullptr) return nullptr; return machine->getPersonWithID(personID); } };
本文转自博客园Grandyang的博客，原文链接：大型社交网站的数据结构[CareerCup] 10.2 Data Structures for Large Social Network ，如需转载请自行联系原博主。
