Social Network

出处

Solution

与上题类似，首先我们考虑数据量不大的情况，即所用用户数据存储在同一部机器上。要查询两个用户之间的联系无非就是广度优先搜索。进一步地，如果数据量很大，那么我们需要用多台机器存储对象。不妨采用与上题类似的思路：引入另一层hash进行数据分流，建立对象与存储该对象的机器之间的映射。通常用户都有一个唯一的ID，我们可以利用ID的前几位数字，决定将该用户数据存放在哪台机器上。这样，广度搜索的查询流程变为：

1. 获得用户的好友ID列表
2. 根据ID获得机器
3. 访问机器获得对应的用户节点
4. 进行下一步递归

应用该方法我们需要注意一下问题：

1. 访问另一台机器的成本可能比较高，因此应该尽量把该机器上的所有相关数据一次性读取完毕。
2. 广度搜索需要记录某个节点是否已经访问过以避免循环访问，我们可以另外开辟一个哈希表记录已经访问的用户节点。
3. 注意合理地简化问题：如果两个用户之间需要多于3重关系才能联系上，我们可以把他们归类为“陌生人”。那么，我们可以将关系链限制在3重关系以内，以减少搜索成本。

Complexity

设计题

Code

设计题