We’re excited to include guest posts on our blog from interesting people and companies in the industry. This post was written by Chaitanya Mattey, a current Pathrise fellow who is working towards his dream job as a software engineer, with help from his advisor, Derrick Mar, a former software engineer at Facebook.
The moment has come and you are finally getting traction on your applications for software engineering positions. In order to make sure that you do well on the interviews, you need to prepare… a lot. We can’t stress this enough – it is better to be over prepared than underprepared for the technical interviews.
There are a lot of online platforms that you can use to practice for your software engineering technical interviews and sometimes the sheer number of options can be overwhelming. So, we wanted to make it a little easier for you. We wanted to provide a step-by-step solution to a common interview question from our 93 software engineering technical interview questions so that you can practice and check yourself.
Tackling a hard interview question can definitely look like a daunting task. As important as preparation is in the technical interview process, understanding the thought process that leads up to a working solution can be equally as important, and give us insights into approaching and solving similar problems in the future.
Cheapest Flights Within K Stops, is a popular algorithm question asked in software engineering interviews at Amazon, Airbnb, and, of course, Google. The problem is often a hurdle for even competent candidates, likely because it involves applying a number of varied concepts to come up with an efficient solution. In this guide, we’ll take a critical look at this problem, and come up with a logical progression of steps you can take to solve it. Every step is accompanied by illustrations for all of you visual learners out there.
“Let’s jump right into it” — Every YouTube reviewer ever
Cheapest Ticket Prices
In the Cheapest Ticket Prices problem we are asked to find the cheapest flight path from a “source” city to a “destination” city, with the constraint that the path can contain at-most K stops. The information that we are given is as follows:
When we first see this problem, it can look like an insurmountable task. There is a high chance of getting overwhelmed by considering all the requirements: we not only need to find a path from the source to the destination, but this path should be the cheapest path, and on top of that the path can only contain at-most K stops! Phew, that’s a lot. One of the key things to remember when tackling problems that seem to have varied conditions is to break the problem into manageable chunks.
Categorize the problem
First, let’s try to categorize the problem. This is an extremely strong practice, one that can make the strangest of questions easily tamable. As we will see, this allows us to use approaches that are usually associated with a particular type of problem.
Let’s take another look at our problem. We need to calculate a path from a source to a destination. Let’s try to represent this information visually.
Looking at the image/graph, we can safely say that we have a traversal problem on our hands. We have nodes which represent our cities, directed edges which represents a flight from a source to a destination, and the weight of each edge is the price for that particular flight.
Possible approaches
Great! Now the question doesn’t seem all that scary. Since we have a traversal problem the next natural step would be to think of ways we can traverse our graph. The two most common graph traversal techniques at our disposal are breadth first, and depth first traversal. Let’s see how they might apply to our problem.
Depth first traversal
Now we have a choice between these two traversal approaches. Which one do we choose? Let’s let the question guide us. The problem is asking us to find the cheapest flight path possible. Remember that if we traverse a graph using depth first traversal, we move from a start node, and don’t stop until we’ve exhausted all paths, or found our destination node. For our graph that would look something like this.
That looks pretty straight-forward. But there’s a catch. You can imagine as the size of the graph grows this approach keeps getting less efficient as we have more and more paths from the source to the destination.
The image above drives the point home. If we encounter a huge graph with many cities, and many connecting flights, the DFS approach to solve the problem would require us to compare every possible path from the source to the destination.
Breadth first traversal
Let’s look at our second option which was a breadth first traversal. While traversing a graph in this way, we visit all of the neighbors for a node first, and store them in some sort of a data structure (usually a queue) and then proceed to visit every neighbor for every subsequent node in our queue (making sure to put it’s neighbor into the queue as well). And unlike the depth first approach, while traversing using a breadth first approach, we have access to all of the neighboring nodes to a particular city, and can therefore choose which one to travel through next. Since we have to find the cheapest path, it would make sense to traverse through the edge (path) that has the cheapest overall cost at that particular point. Let’s try to visualize what the breadth first traversal would look like:
Using this approach, as you might have deduced already, we are guaranteed that once we reach the destination node, we will have found the cheapest path possible!
Here’s what the queue would look like while traversing the graph using BFS as above:
Current algorithm
Here’s the algorithm we’ve devised so far:
Improvements
In order to accomplish this in code we need to store the relevant state information in our queue as well. State information here refers to the total flight cost incurred so far, and the total number of stops we’ve made in traveling to our current city.
Here’s what the updated queue state would look like for our example:
At this point you might ask yourself, why are the “stops” variable initialized to -1? Why not to 0, which seems like the more obvious option? This is because the number of stops it takes to go from the source city directly to another neighboring city is 0 and therefore, we can say that the number of stops it takes to go to the source city should be one less than the number of stops it takes to go to a neighboring city (viz. 0), and that’s where the -1 comes from. Let’s understand this more clearly:
In addition to getting the cheapest flight in our queue, we are now also capable of extracting the number of stops we have taken corresponding to our current flight path. Having access to the number of stops ensures that we can find a path that has at most K stops, which is great because that is exactly what the question asks.
Let’s recap what we’ve done so far:
- We started by visualizing what the problem was asking, using a concrete example. Then we figured out what kind of problem we were facing, in this case the problem was a graph traversal problem.
- Then, we looked at a couple of popular techniques at our disposal to solve graph traversal problems like breadth-first traversal (BFS) and depth-first traversal (DFS).
- Next, we applied each of these techniques to our problem, and saw that the breadth first approach worked better.
- Finally, we updated the data in our queue to store more information so we could access the number of stops as well as the total cost.
Before we begin coding out our solution, let’s take another look at our algorithm:
On step #3, we are popping/removing the path with the minimum cost so far. There are multiple ways to accomplish this in code. Let’s look at some of the options.
- We can sort the queue every time before we remove an element from it. This would add O(nlogn) complexity each time the loop is run.
- We can look for the largest element using the QuickSelect algorithm. This algorithm has a O(n) average case time-complexity, but a O(n^2) worst case complexity.
- We can use a Min-Heap data-structure instead of a queue, so we can pop the min element(cheapest-flight path) in constant time, and maintain the heap property in O(log(n)) complexity at each loop iteration.
Looking at the options, and our problem again, we can observe that we don’t actually need to maintain a completely sorted list of all our flight paths. We only want the cheapest flight at any given point and a Heap is the perfect data structure to accomplish that. So, now instead of pushing and popping to/from our queue we can use a Heap to accomplish the same functionality with better performance compared to the other options.
Coding
Now keeping this approach in mind, let’s code up our algorithm step-by-step.
Storing flight information for easier retrieval using the start flight:
Initializing our heap:
Implementing our BFS:
Getting our exit conditions right, and checking for valid number of stops
Final algorithm:
Key insights
Here are some key insights that helped us solve this problem:
Future learning
Congrats on making it to the end! We hope you found the approach and insights useful. If you are looking to learn more about the software engineering hiring processes and interview questions at Google and other top tech companies, check out our Interviewing Insider Company Guides.
Pathrise is a career accelerator that works with students and young professionals 1-on-1 so they can land their dream job in tech. With these tips and guidance, software engineering fellows in our program have seen their interview performance scores double.
If you want to work with any of our advisors 1-on-1 on your software engineer technical interviews or with any other aspect of the job search, become a Pathrise fellow.
