Learn and practice the Graphs, Tries, and Custom Data Structures patterns to solve coding interview problems.

Educative-99 in Python: Accelerate Your Coding Interview Prep

Proficiency in advanced data structures is a marker of a highly experienced engineer, and interviewers use such questions to finetune how they grade candidates. This module teaches you the use of two advanced data structures—graphs and tries—to solve relatively complex problems. To solve problems with very specific requirements that may not be handled by standard data structures, we gain experience in the advanced skill of the design, implementation, and efficient use of custom data structures.

Advanced Data Structures

# 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.

Graphs

Trie

Custom Data Structures

Conclusion

Solution: Bus Routes

Statement