Routing for Minimum Travel Time | Dataford Interview Questions

Backend practical: use the Google Places API to convert resort names and a home address into place IDs, use the Routes API to get driving time between each pair of locations, then find the route that minimizes total travel time (travelling salesman).

Asked in the backend practical stage, pretty much as described in the prep materials. The task has 3 steps.

For grading, API calls are represented by a square travel_times matrix. Index 0 is home, and indices 1..n are resorts. Return the minimum total driving time and a route that starts and ends at home.

Output

Return {"route": [...], "total_time": number}.

Constraints

travel_times is a square matrix with size n + 1
Index 0 represents home and indices 1 through n represent resorts
0 <= n <= 15
0 <= travel_times[i][j] <= 10^6
travel_times[i][i] = 0
A route must start and end at home

Function Signature

def minimum_resort_route(travel_times):

Your question is Routing for Minimum Travel Time. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem