use*_*090 10 algorithm data-structures
我偶然发现的另一个有趣的访谈问题 -
为非常大的社交网络(Facebook,LinkedIn等)设计数据结构？
另外,设计一个算法来显示两个人之间的连接或路径(例如me-> foo-> bar-> rob-> ron)
小智 5
我可能会考虑一些不同的无向图,可能存储为稀疏邻接矩阵.至于找到两个人之间的最短路径,由于边缘成本是一致的,我会考虑进行双向搜索.
基本上,以每个人为中心的同心圆出去,其中每个圆圈都是他自己,然后是他的朋友,然后是朋友的朋友等,在每个步骤测试两个圆圈中是否有人.沿着从你发现的第一个人向每个人的中心走的路径,你找到了最短的路径.
您可以尝试其他最短路径算法,但一般来说,大多数最短路径算法只能给出距离而不是实际路径.