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.
