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.
