Interview questions: union find solutions
最近在学习Coursera上的Algorithms, Part I,其每个week除了正常的Programming Assignment外还有面试问题.由于面试问题没有提交评分要求,想来在blog这里分享解决方案应该是没有违反honor code的.故这篇blog将是Algorithms面试问题题解系列的第一篇.
Queston 1
原题引用如下:
Social network connectivity. Given a social network containing N members and a log file containing M timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be MlogN or better and use extra space proportional to N.
Read full article from Interview questions: union find solutions
No comments:
Post a Comment