@DON: DFS should not be applied because, there can exist multiple paths from A to C, but the question is to find the shortest path. So, u might end up getting longer path. Otherwise you have to search for all possible paths which will be very inefficient.
---- Saurabh Agrawal On Tue, Sep 13, 2011 at 10:01 PM, Navneet <navneetn...@gmail.com> wrote: > 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 <dondod...@gmail.com> 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 <jkhas...@gmail.com> 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 <mehdi.kaze...@gmail.com > >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 < > karanthak...@gmail.com>wrote: > > > > > >> bfs > > > > > >> On Tue, Sep 13, 2011 at 5:59 PM, JITESH KUMAR <jkhas...@gmail.com> > 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 < > veeracool...@gmail.com>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 <jkhas...@gmail.com > >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 algogeeks@googlegroups.com. > > > >>>>> To unsubscribe from this group, send email to > > > >>>>> algogeeks+unsubscr...@googlegroups.com. > > > >>>>> 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 algogeeks@googlegroups.com. > > > >>>> To unsubscribe from this group, send email to > > > >>>> algogeeks+unsubscr...@googlegroups.com. > > > >>>> 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 algogeeks@googlegroups.com. > > > >>> To unsubscribe from this group, send email to > > > >>> algogeeks+unsubscr...@googlegroups.com. > > > >>> 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 algogeeks@googlegroups.com. > > > >> To unsubscribe from this group, send email to > > > >> algogeeks+unsubscr...@googlegroups.com. > > > >> 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 algogeeks@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com. > > > > 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
