A related discussion is available here. http://stackoverflow.com/questions/1556451/how-do-sites-like-linkedin-efficiently-display-1st-2nd-3rd-level-relationship-nex
On Sep 13, 8:37 pm, Don <[email protected]> wrote: > I think your statement about A->B->C leads people to believe that the > depth is 2. If we know depth is 2, we just scan A's friends and C's > friends looking for a match, which is B. > If we don't know the length of the path, we might want to start > searching from A and C at the same time and look for a friend common > to both search trees. > Don > > On Sep 13, 9:57 am, JITESH KUMAR <[email protected]> wrote: > > > > > > > > > Depth is not mentioned, it can be any. > > This question was asked from me in the telephonic interview of DE Shaw. > > The interviewer told me reduce space complexity. > > > On Tue, Sep 13, 2011 at 6:18 PM, MeHdi KaZemI > > <[email protected]>wrote: > > > > I think applying BFS is good, what's the problem with space? Isn't the > > > depth gonna be at most 2 ? > > > If we suppose the depth is gonna be at most 2, then suppose we want the > > > path from A to C, > > > A has 500 friends and each of his/her friends has 500 friends too, so we > > > have to visit 500*500 nodes to find the path, am I right? > > > > On Tue, Sep 13, 2011 at 5:11 PM, Karan Thakral > > > <[email protected]>wrote: > > > >> bfs > > > >> On Tue, Sep 13, 2011 at 5:59 PM, JITESH KUMAR <[email protected]> wrote: > > > >>> I guess you have misunderstood the problem. > > >>> We are not concerning about the length of path. We just have to find the > > >>> path. > > >>> But in the efficient way. suppose first person is having 500 friends and > > >>> each of them again is having 500 friends each. > > >>> Applying BFS will take a lot of space. > > > >>> On Tue, Sep 13, 2011 at 5:48 PM, veera reddy > > >>> <[email protected]>wrote: > > > >>>> finding the shortest path between A and C nodes , gives required > > >>>> solution . > > >>>> We can use dijkstra's algorithm to find the shortest path .. > > > >>>> On Tue, Sep 13, 2011 at 5:43 PM, JITESH KUMAR > > >>>> <[email protected]>wrote: > > > >>>>> Suppose you are visiting someone's profile in fb or linkedin, you get > > >>>>> to know how you are connected to that person. > > >>>>> e.g. Suppose you are visiting C's profile. you get a suggestion like > > >>>>> you are connected to him via A->B->C. > > >>>>> Tell efficient way to solve this problem( apart from Brute Force). > > > >>>>> -- > > >>>>> *Regards > > >>>>> Jitesh Kumar* > > > >>>>> -- > > >>>>> You received this message because you are subscribed to the Google > > >>>>> Groups "Algorithm Geeks" group. > > >>>>> To post to this group, send email to [email protected]. > > >>>>> To unsubscribe from this group, send email to > > >>>>> [email protected]. > > >>>>> For more options, visit this group at > > >>>>>http://groups.google.com/group/algogeeks?hl=en. > > > >>>> -- > > >>>> Regards , > > >>>> P Veera Reddy Devagiri > > >>>> Senior Under Graduate > > >>>> Computer Science and Engineering > > >>>> IIIT Hyderabad > > >>>> Mobile no-+91-9492024783 > > > >>>> -- > > >>>> You received this message because you are subscribed to the Google > > >>>> Groups "Algorithm Geeks" group. > > >>>> To post to this group, send email to [email protected]. > > >>>> To unsubscribe from this group, send email to > > >>>> [email protected]. > > >>>> For more options, visit this group at > > >>>>http://groups.google.com/group/algogeeks?hl=en. > > > >>> -- > > >>> *Regards > > >>> Jitesh Kumar > > > >>> "There is only one 'YOU' in this world. You are Unique and Special.* > > >>> *Don't Ever Forget it."* > > > >>> -- > > >>> You received this message because you are subscribed to the Google > > >>> Groups > > >>> "Algorithm Geeks" group. > > >>> To post to this group, send email to [email protected]. > > >>> To unsubscribe from this group, send email to > > >>> [email protected]. > > >>> For more options, visit this group at > > >>>http://groups.google.com/group/algogeeks?hl=en. > > > >> -- > > >> You received this message because you are subscribed to the Google Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]. > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > > "Stay Hungry Stay Foolish" > > > MeHdi KaZemI > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > *Regards > > Jitesh Kumar > > > "There is only one 'YOU' in this world. You are Unique and Special.* > > *Don't Ever Forget it."* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
