## Ebay Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
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"
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

The problem asks for an Eulerian path, not a Hamiltonian path (each edge needs to be used once, not each vertex). The problem of finding an Eulerian path is in fact solvable in linear time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Triangle is a simple cycle. We can find all cycles in O(n) with DFS. All we need is to simply find cycles and print those lenght are 3.

Comment hidden because of low score. Click to expand.
0

You misunderstand the problem statement. It's not asking for triangle cycles, the reference to triangles was example. You are asked "compute paths in G that traverses each edge in E exactly once in each direction"

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.