## Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

Represent the problem as a graph: train as edge (directed), station as vertex
Use dijkstra's shortest distance path to get shortest distance from any given start to all ends.

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

Create a Node<A,T> for each stop S at time T. There would be 24*4 nodes for each city for each day.

For each train with n stops, create n^2 edges between appropriate nodes. The cost of an edge would be the fare. The edge includes seat availability information.

For transfers, create a special zero cost "local edge" from Node<S,T1> to Node<S,T2> , for each S, if T1 earlier than T2 by fixed amount of layover time. These edges can be built into the shortest path algorithm and need not be represented using data.

For travel between stops S1 to S2, use shortest path algorithms like Dijkstra and A* to find shortest route from Node<A,T1> to Node<B, *>. Limit/Bound the shortest path to maximum of two trains and one "local edge".

Train data can be maintained in database as an adjacency matrix.

Update graph data structure regularly by
1. Removing Nodes and Edges from past times
2. Adding Nodes and Edges for new routes as they arrive (typically a few months ahead of time).
3. Updating data when train times are updated
4. Updating availability for edges as tickets are purchased

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

Corrections:
1. Maintain adjacency list, not database.
2. For travel between stops S1 to S2, use shortest path algorithms like Dijkstra and A* to find shortest route from Node<S1,T1> to Node<S2, *>

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

This can be done using another approach .i.e

For every pair of station , simply use brute force approach to calculate the path between the both .
This is a lot easy to implement .

Now the result can be stored in database easily and queried easily.

The scalability depends on number of queries the site is getting .

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Create a graph to represent the system
Use BFS to find shortest path.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Create a graph to represent the system.
Use BFS to find the shortest path

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.