Ebay Interview Question Software Engineer / Developers
Country: United States
This problem is called a Hamiltonian Path. It is an NP-complete problem. That means there are no "Efficient" solutions.
check wiki :
en.wikipedia.org/wiki/Hamiltonian_path_problem
A path that visits every edge in a graph exactly once is called an Euler tour (see Wikipedia).
You might say your graph is undirected, but since you want each edge to be traversed once *in each direction*, direction becomes relevant and you can model the graph as a directed graph. Convert your undirected graph to a directed graph by replacing each undirected edge with two directed ones, one in each direction. We will now ask: can we produce a path that traverses each edge of this directed graph exactly once?
For there to exist a path that visits every edge, the original undirected graph must be a connected graph (it is clearly impossible to move between components that are not connected). In addition, the directed graph has an important property: every vertex in the directed graph has exactly as many inbound edges as outbound edges because the directed edges were placed in pairs (that is, A -> B always accompanied by B -> A).
Given these properties, here is how you can find a path. By this algorithm, you can also see that a path always exists:
1. Pick an arbitrary node in the graph.
2. From that node, take any previously untraveled outbound edge. You will now be at a new vertex.
3. Repeat step 2 until you return to the vertex you started with in step 1, and record the path you travel along the way. You are guaranteed to eventually reach the vertex you started with -- you will never run out of untraveled edges somewhere in the middle and get stuck -- because every intermediate vertex has an outbound edge for every inbound edge, so if you can get to that vertex, you can leave.
Now, consider the possibilities.
a. You've visited every vertex, and visited every edge. In that case, you're done.
b. You've visited every vertex, but not every edge. In that case, there are vertices in your path that have untraveled outbound edges.
c. You haven't visited every vertex. In that case, there are vertices in your path that have untraveled outbound edges. Otherwise, your graph wouldn't be connected.
So, either you're done, or there are vertices in your path that have untraveled outbound edges.
4. While there are untraveled outbound edges, pick an arbitrary vertex in your path that has such an edge. Call that vertex v0.
If v1 is your initial node picked in step 1, your current path looks like v1 -> ... -> v0 -> ... -> v1.
Repeat steps 2-3 starting from v0. The path generated by this operation will look like v0 -> ... -> v0. Insert this path into the previous path of v1 -> ... -> v0 -> ... -> v1, at the position of v0. Now your path looks like v1 -> ... -> v0 -> ... -> v0 ... -> v1.
Keep doing this and adding to the path until there are no untraveled outbound edges anywhere in your path.
The final resulting path visits every edge exactly once.
A fairly sloppy implementation of this algorithm might take O(n^2), but if implemented carefully, it is possible to achieve O(n).
Do this on a undirected graph and then whenever a Euleridean Path is found it means both directions of the path are feasible to be the answer. Then just do it in O(n).
You can't just run the algorithm on the undirected graph, at least not in the typical sense of finding an Euler path on an undirected graph (each edge must be traveled exactly once, regardless of direction). There is no constraint in this problem that the undirected graph must admit an Euler path.
However, since the question asks that we should travel each edge once *in each direction*, we know we can always make a tour because the in-degree equals the out-degree for every vertex in the equivalent directed graph.
It looks like I didn't see the requirement to find all paths when reading the problem, so I only found one.
Now that I think about it, there was no need to deal with Euler tours at all here. We could have simply maintained a linked list representing the path discovered so far, and for every edge (v1, v2) not yet included in the path such that v1 appears in the path already, make a new path v1 -> v2 -> v1 and merge it with the existing path at v1.
How about :
- Anonymous January 23, 2014{{
Use the BFS search:
From node u,
(1) for a new edge u->v, just print "visiting the edge from u to v";
(2) for a back edge u->v, just print "visiting the edge from u to v, and then v to u"
(3) when all the children are visited, back trace to u's parent v, just print "visiting the edge from u to v"
}}