Social Network
出处
Solution
与上题类似,首先我们考虑数据量不大的情况,即所用用户数据存储在同一部机器上。要查询两个用户之间的联系无非就是广度优先搜索。进一步地,如果数据量很大,那么我们需要用多台机器存储对象。不妨采用与上题类似的思路:引入另一层hash进行数据分流,建立对象与存储该对象的机器之间的映射。通常用户都有一个唯一的ID,我们可以利用ID的前几位数字,决定将该用户数据存放在哪台机器上。这样,广度搜索的查询流程变为:
- 获得用户的好友ID列表
- 根据ID获得机器
- 访问机器获得对应的用户节点
- 进行下一步递归
应用该方法我们需要注意一下问题:
- 访问另一台机器的成本可能比较高,因此应该尽量把该机器上的所有相关数据一次性读取完毕。
- 广度搜索需要记录某个节点是否已经访问过以避免循环访问,我们可以另外开辟一个哈希表记录已经访问的用户节点。
- 注意合理地简化问题:如果两个用户之间需要多于3重关系才能联系上,我们可以把他们归类为“陌生人”。那么,我们可以将关系链限制在3重关系以内,以减少搜索成本。
Complexity
设计题
Code
设计题