Learn essential coding patterns to answer problems and prepare for tech companies' interviews.

Ace the C++ Coding Interview

This module teaches us the underlying patterns behind common coding interview questions. By learning these essential patterns, we'll be able to assess the problem statement and unpack and answer any problem the right way. This approach was created by FAANG’s hiring managers to help us prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon.

By the end of this module, we'll have the skills we need to unlock even the most challenging questions, grok the coding interview, and level up our career with confidence.

Coding Interview Patterns

# Statement
You are given an array, `routes`, representing bus routes where `routes[i]` is a bus route that the $i^{th}$ bus repeats forever. Every route contains one or more stations. You have also been given the source station, `src`, and a destination station, `des`. Return the minimum number of buses someone must take to travel from `src` to `dest`, or return `-1` if there is no route.

**Constraints:**

* $1 \le$ `routes.length` $\le 50$
* $1 \le$ `routes[i].length` $\le 100$
* $0 \le$ `routes[i][j]` $< 1000$
* $0 \le$ `src`, `dest` $< 1000$

# Solution

The solution starts by creating an adjacency list that maps each station to the buses that travel through that station. This is done by iterating through `routes` and, for each `route`, adding the `route`'s index to the adjacency list for each station in that route.

Next, we use the BFS algorithm to find a path from `src` to `dest` using the minimum number of buses since BFS always finds the shortest path in an unweighted graph.
 The BFS algorithm is implemented using a queue that stores the current station and the number of buses taken to reach that station. The queue is initialized with `src` and a bus count of `0`.

Then, we repeatedly dequeue the next station from the queue, and if it is equal to the `dest`, we return the number of buses. Otherwise, we iterate through the buses that travel through the current station and, for each unvisited bus, we enqueue all the stations in that bus route along with the bus count incremented by `1` and mark that bus as visited by adding it into the set of visited buses.
If the queue becomes empty and no station is equal to the `dest`, we return `-1` because there is no route available from `src` to `dest`.

Let’s solve the Bus Routes problem using the Graphs pattern.