I think we could use Algorithm A* where in subgraph(G) maintains all the
paths to the required profile and subtree(Tr) gives us the optimal
path..
On Tue, Sep 13, 2011 at 5:43 PM, JITESH KUMAR wrote:
> Suppose you are visiting someone's profile in fb or linkedin, you get to
> know how you ar
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 wrote:
> I think applying BFS is good, what's the problem with space? Isn't the
> depth gon
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 th
bfs
On Tue, Sep 13, 2011 at 5:59 PM, JITESH KUMAR 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
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,
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 wrote:
> Suppose you are visiting someone's profile in fb or linkedin, you get to
> know how you are connected
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).
--
*Reg
