Amazon Software Engineer Interview Experience — Four Interviews with a Train Fare Calculator and Sliding Window Max

Interview #1 — LP + DSA/OOP

Leadership Principles behavioral interview, about 10–15 minutes.

Then the design question: a train fare calculation system. There is one train line, G → U → H → K → I, and the fare between every two adjacent stations is 1 (for example, G to I costs 4).

1. Implement calculateFare(start, stop) to compute the fare between two stations.
2. Think about OOP/LLD design: where does the route data come from? Design and implement a class that supports dynamically adding/pushing stations onto the route.
3. Follow-up: on weekends, the total fare needs to be capped at a certain maximum amount. Implement that business logic.

Interview #2 — DSA + GenAI

A string/substring-style coding problem.

1. Implement the core algorithm and dry run it by hand.
2. Write test cases for the algorithm, including the empty string and other edge cases.

There were also technical questions and discussion about GenAI.

Interview #3 — Leadership Principles / Behavioral

A fully behavioral interview.

1. They asked about dealing with a difficult teammate, or about making a difficult decision.

Interview #4 — LP + DSA

Behavioral question: share a time you had to overcome obstacles to reach an important goal.

Then design a sliding window data structure that supports getting the maximum value in the window. Implement this interface:

SlidingWindow(k)
put(number)
getMax()   // returns the max of the k most recently inserted elements

1. Implement a basic version and analyze its time and space complexity.
2. Follow-up: how do you optimize the space so you don't store all the history, bringing it down to O(k)?
3. Discussion: compare the time/space complexity and trade-offs of using an array, a hash map, a linked list / doubly linked list, and a heap for this.
4. Discussion: how to use a monotonic deque to get the optimal solution.