Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

Just No more free questions left!

Upgrade Now

You wrote a trendy new messaging app, MeshMessage, to get around flaky cell phone coverage.

Instead of routing texts through cell towers, your app sends messages via the phones of nearby users, passing each message along from one phone to the next until it reaches the intended recipient. (Don't worry—the messages are encrypted while they're in transit.)

Some friends have been using your service, and they're complaining that it takes a long time for messages to get delivered. After some preliminary debugging, you suspect messages might not be taking the most direct route from the sender to the recipient.

Given information about active users on the network, find the shortest route for a message from one user (the sender) to another (the recipient). Return a list of users that make up this route.

There might be a few shortest delivery routes, all with the same length. For now, let's just return any shortest route.

Your network information takes the form of a dictionary mapping username strings to a list of other users nearby:

network = { 'Min' : ['William', 'Jayden', 'Omar'], 'William' : ['Min', 'Noam'], 'Jayden' : ['Min', 'Amelia', 'Ren', 'Noam'], 'Ren' : ['Jayden', 'Omar'], 'Amelia' : ['Jayden', 'Adam', 'Miguel'], 'Adam' : ['Amelia', 'Miguel', 'Sofia', 'Lucas'], 'Miguel' : ['Amelia', 'Adam', 'Liam', 'Nathan'], 'Noam' : ['Nathan', 'Jayden', 'William'], 'Omar' : ['Ren', 'Min', 'Scott'], ... }

For the network above, a message from Jayden to Adam should have this route:

['Jayden', 'Amelia', 'Adam']

We can find the shortest route in time, where N is the number of users and M is the number of connections between them.

It's easy to write code that can get caught in an infinite loop for some inputs! Does your code always finish running?

What happens if there's no way for messages to get to the recipient?

What happens if the sender tries to send a message to themselves?

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

Our solution has two main steps. First, we do a breadth-first search of the user network starting from the sender. Then, we use the results of our search to backtrack and find the shortest path.

How much work is a breadth-first search?

In the worst case, we'll go through the BFS loop once for every node in the graph, since we only ever add each node to nodes_to_visit once (we check how_we_reached_nodes to see if we've already added a node before). Each loop iteration involves a constant amount of work to dequeue the node and check if it's our end node. If we have n nodes, then this portion of the loop is .

But there's more to each loop iteration: we also look at the current node's neighbors. Over all of the nodes in the graph, checking the neighbors is , since it involves crossing each edge twice: once for each node at either end.

Putting this together, the complexity of the breadth-first search is .

BFS and DFS are common enough that it's often acceptable to just state their complexity as . Some interviewers might want you to derive it though, so definitely be ready in case they ask.

What about backtracking to determine the shortest path? Handling each node in the path is , and we could have at most N nodes in our shortest path. So, that's for building up the path. Then, it's another to reverse it. So, the total time complexity of our backtracking step is .

Putting these together, the time complexity of our entire algorithm is .

What about space complexity? The queue of nodes to visit, the mapping of nodes to previous nodes, and the final path ... they all store a constant amount of information per node. So, each data structure could take up to space if it stored information about all of our nodes. That means our overall space complexity is .

  1. In our solution, we assumed that if one user (Min) could transmit a message to another (Jayden), then Jayden would also be able to transmit a message to Min. Suppose this wasn't guaranteed—maybe Min's cell phone transmits over shorter distances than Jayden's. How would our graph change to represent this? Could we still use BFS?
  2. What if we wanted to find the shortest path? Assume we're given a GPS location for each user. How could we incorporate the distance between users into our graph? How would our algorithm change?
  3. In our solution, we assumed that users never moved around. How could we extend our algorithm to handle the graph changing over time?

Our app's design has a formal name: a mesh network. In a mesh network, data is sent from one node (here, a phone) to another directly, rather than through intermediate devices (here, cell towers). Assuming enough devices are in range, mesh networks provide multiple possible transmission paths, making them reliable even if some devices have failed.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

What's next?

Powered by qualified.io

. . .