Interview Question
- 0of 0 votes
AnswersAlyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a burgeoning social network
- vxixnxaxy October 22, 2013 in India
website. She needs to implement a new friend suggestion feature. For two friends u and v (friendship is undirected), the EdgeRank ER(u; v) can be computed in constant time based on the interest
u shows in v (for example, how frequently u views v’s profile or comments on v’s wall). Assume
that EdgeRank is directional and asymmetric, and that its value falls in the range (0; 1). A user
u is connected to a user v if they are connected through some mutual friends, i.e., u = u0 has a
friend u1, who has a friend u2, . . . , who has a friend uk = v. The integer k is the vagueness of the
connection. Define the strength of such a connection to be
k
S(p) = pie ER(u ; ui):
i=1 i-1
For a given user s, Alyssa wants to have a way to rank potential friend suggestions according to
the strength of the connections s has with them. In addition, the vagueness of those connections
should not be more than k, a value Alyssa will decide later.
Help Alyssa by designing an algorithm that computes the strength of the strongest connection
between a given user s and every other user v to whom s is connected with vagueness at most
k, in O(kE + V ) time (i.e., for every pair of s and v for v 2 V nfsg, compute the strength of the
strongest connection between them with vagueness at most k). Assume that the network has jV j
users and jEj friend pairs. Analyze the running time of your algorithm. For partial credit, give a
slower but correct algorithm. You can describe your algorithm in words, pseudocode or both.| Report Duplicate | Flag | PURGE
Algorithm