You could do a depth-first search limited to depth 2. If that fails, do it to depth 3. Then 4, etc. It is very space efficient, and you will be spending 99% of your time at the deepest level, so the time penalty compared to breadth first is not all that bad.
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.
