Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in C#: Real-World Examples

Feature #3: Plot and Select Path

Explore how to determine the optimal driver route to a user by calculating travel costs through checkpoints in a city map. Learn to build graphs representing roads, use depth-first search to find paths, and select the lowest-cost driver while handling possible unavailability scenarios.

We'll cover the following...

Description

After obtaining the closest drivers and calculating the cost of traveling on different roads, we need to build a functionality to select a path from the driver’s location to the user’s location. All the drivers have to pass through multiple checkpoints to reach the user’s location. Each road between checkpoints will have a cost, which we learned how to calculate in the previous lesson. It is possible that some of the k chosen drivers might not have a path to the user due to unavailability. Unavailability can occur due to a driver already ...

In the above example,

  • GMap has the values [["a","b"],["b","c"],["a","e"],["d","e"]].

  • pathCosts has the values [12,23,26,18].

  • drivers has the values ["c", "d", "e", "f"].

  • user has a value "a".

After calculating the total cost of each driver’s route to the user, we’ll select that driver that has a path to the user with the lowest cost. Here, the driver f has no path to the user due to unavailability.

Solution

The main problem comes down to finding a path between two nodes, if it exists. If the path exists, return the cumulative sums along the path as the result. Given the problem, it seems that we need to track the nodes where we come from. DFS (Depth-First Search), also known as the backtracking algorithm, will be applicable in this case.

Here is how the implementation will take place:

  1. Build the graph using the city map list GMap.

  2. Assign the cost to each edge while building the graph.

  3. Once the graph is built, evaluate each driver’s path in the drivers list by searching for a path between the driver node and the user node.

  4. Return ...

C#
using System;
using System.Collections.Generic;
class Solution {
  
  public static double[] getTotalCost(List<List<string>> GMap, double[] pathCosts, List<string> drivers, string user) {
		Dictionary<string, Dictionary<string, double>> city = new Dictionary<string, Dictionary<string, double>>();
		// Step 1). build the city from the GMap
		for (int i = 0; i < GMap.Count; i++) {
			List<string> checkPoints = GMap[i];
			string sourceNode = checkPoints[0], destNode = checkPoints[1];
			double pathCost = pathCosts[i];
			if (!city.ContainsKey(sourceNode))
				city[sourceNode] = new Dictionary<string, double>();
			if (!city.ContainsKey(destNode))
				city[destNode] = new Dictionary<string, double>();
			city[sourceNode][destNode] = pathCost;
			city[destNode][sourceNode] = pathCost;
		}
		// Step 2). Evaluate each driver via bactracking (DFS)
		// by verifying if there exists a path from driver to user
		double[] results = new double[drivers.Count];
		for (int i = 0; i < drivers.Count; i++) {
			string driver = drivers[i];
			if (!city.ContainsKey(driver) || !city.ContainsKey(user))
				results[i] = -1.0;
			else {
				HashSet<string> visited = new HashSet<string>();
				results[i] = backtrackEvaluate(city, driver, user, 0, visited);
			}
    	}
    	return results;
  }
  private static double backtrackEvaluate(Dictionary<string, Dictionary<string, double>> city, string currNode, string targetNode, double accSum, HashSet<string> visited) {
      // mark the visit
      visited.Add(currNode);
      double ret = -1.0;
      Dictionary<string, double> neighbors = city[currNode];
      if (neighbors.ContainsKey(targetNode))
          ret = accSum + neighbors[targetNode];
      else {
          foreach(var pair in neighbors) {
              string nextNode = pair.Key;
              if (visited.Contains(nextNode))
                  continue;
              ret = backtrackEvaluate(city, nextNode, targetNode,
                      accSum + pair.Value, visited);
              if (ret != -1.0)
                  break;
          }
      }
      // unmark the visit, for the next backtracking
      visited.Remove(currNode);
      return ret;
  }
  public static void Main() {
    // Driver code
    List<List<string>> GMap = new List<List<string>>();
	GMap.Add(new List<string>(new string[] {"a", "b"}));
	GMap.Add(new List<string>(new string[] {"b","c"}));
	GMap.Add(new List<string>(new string[] {"a","e"}));
	GMap.Add(new List<string>(new string[] {"d","e"}));
    double[] pathCosts = {12.0,23.0,26.0,18.0};
    List<string> drivers = new List<string>(){"c", "d", "e", "f"};
    string user = "a";
    double[] allPathCosts = getTotalCost(GMap, pathCosts, drivers, user);
    Console.WriteLine("Total cost of all paths [{0}]", string.Join(", ", allPathCosts));
  }
}
Plot and Select Path

Complexity measures

...