This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.
--
I found this one interesting...
Problem:
Given information about active users on a network, find the shortest route for a message from one user (the sender) to another (the recipient). Return an array 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 hash mapping username strings to an array 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']
-
If you want to follow along, feel free to post your answers in the comment.
My answers are in the comments. This problem is from InterviewCake.
Discussion (3)
Isn't this just a simple BFS?
play.rust-lang.org/?version=stable...
The function(+data type used for search) is:
Nice. Yes it is.
Logic:
-If there is a match, also store the path - who is directly connected to whom?
-That way in the end, you just have to go back the path from receiver to sender.
The code below could be cleaned up more.. But here it is.