Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

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

- Hong Duan January 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Hong duan January 14, 2016 | Flag Reply
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

- Vyasa January 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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, *>

- vyasa January 19, 2016 | Flag
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 .

- dhsharma27 May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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.

- tusharora19 July 23, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More