As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center提供指导。
9年前关闭。
我偶然发现的另一个有趣的面试问题-
为大型社交网络(Facebook，LinkedIn等)设计数据结构？
另外，设计一种算法来显示两个人之间的联系或路径(例如me-> foo-> bar-> rob-> ron)
9年前关闭。
我偶然发现的另一个有趣的面试问题-
为大型社交网络(Facebook，LinkedIn等)设计数据结构？
另外，设计一种算法来显示两个人之间的联系或路径(例如me-> foo-> bar-> rob-> ron)
最佳答案
我可能会考虑某种形式的无向图，可能将其存储为稀疏邻接矩阵。至于找到两个人之间的最短路径，由于边缘的成本是一致的，因此我将考虑进行双向搜索。
基本上，以每个人为中心的同心圆外出，每个圆都是人本人，然后是他的 friend ，然后是他的 friend friend ，等等，在每一步中测试两个圈子中是否有人。沿着从找到的第一个人向内到每个人的中心的路径，您已经找到了最短的路径。
您可以尝试其他最短路径算法，但是通常，大多数最短路径算法仅给出距离而不是实际路径。
关于algorithm - 面试问题: Data structure for a large social network，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4129691/