[algogeeks] Re: Yahoo Interview Question for Software Engineer/Developer about Algorithms
Even if u are connected to that person via some another friend it'll show the shortest chain by which you are connected to that person..So DFS will be optimum i guessWhy do you think it wouldn't be optimum.? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Yahoo Interview Question for Software Engineer/Developer about Algorithms
i will choose BFS. As we just don't want to show a connection.. we want to show the shortest one. On Sat, Sep 18, 2010 at 4:12 PM, soundar soundha...@gmail.com wrote: Even if u are connected to that person via some another friend it'll show the shortest chain by which you are connected to that person..So DFS will be optimum i guessWhy do you think it wouldn't be optimum.? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.
[algogeeks] Re: Yahoo Interview Question for Software Engineer/Developer about Algorithms
You could construct two level graphs starting starting simultanously from your node and the other member's. Add layers one at a time to each. When, after adding a new level, you find one or more nodes in both level graphs, you can stop. Each shared node gives you a least-edge path between the two start nodes. By roughly halving the depth of a simple BFS, you avoid touching k^(D-1)nodes in a graph with degree k, which is a useful trick. Whether this is optimal can't be said because you haven't defined optimality. In case some haven't heard the term, a level graph is formed by breadth first search in stages. First you find all nodes reachable from the start node by 1 edge traversal. This is level 1. Then find all unfound nodes reachable by 1 edge from level 1 nodes. This is level 2, etc. On Sep 18, 4:04 am, bittu shashank7andr...@gmail.com wrote: if you click on any orkut member's name you will notice the relationship graph for both of you indicating through whom you are interconnected or in certain cases you won't get this path. if you have to propose algorithm what would be the one ...breadth first or depth first traversal with some modifications will help but wouldn't be most optimum way Regards Shashank Mani Computer Science Engineering Birla Institute of Technology,Mesra Cell No. +91-9166674831 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
