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

Feature #3: Plot and Select Path

Explore how to select the optimal path from Uber drivers to a user by building a graph of city checkpoints and using depth-first search to calculate travel costs. Understand how to handle driver availability and find the minimum accumulated cost path for efficient route planning.

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,

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

  • path_costs 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 g_map.

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

Ruby
require 'set'
def get_total_cost(g_map, path_costs, drivers, user)
    city ={}
    # Step 1). build the city from the G_map
    g_map.zip(path_costs).each do |(source_node, dest_node), path_cost|
        
      if (!city.has_key? (source_node))
          city[source_node] = {}
      end
      if (!city.has_key? (dest_node))
          city[dest_node] = {}
      end
      
      # add nodes and two edges into the city
      city[source_node][dest_node] = path_cost
      city[dest_node][source_node] = path_cost
    end
    
    # Step 2). Evaluate each driver via backtracking (DFS)
    #  by verifying if there exists a path from driver to user
    results = []
    drivers.each do |driver|
        if (!city.include?(driver)) or (!city.include?(user))
            # Either node does not exist
            ret = -1.0
        else
            visited = Set.new
            ret = backtrack_evaluate(city, driver, user, 0, visited)
        end
        results.push(ret)
    end
    return results
end
def backtrack_evaluate(city ,curr_node, target_node, acc_sum, visited)
    visited.add(curr_node)
    ret = -1.0
    neighbors = city[curr_node]
    if neighbors.include? target_node
      ret = acc_sum + neighbors[target_node]
    else
      neighbors.each do |neighbor, value|
          if visited.include? neighbor
              next
          end
          ret = backtrack_evaluate(city, neighbor, target_node, acc_sum + value, visited)
          if ret != -1.0
              break
          end
      end
    end
    visited.delete(curr_node)
    return ret
end
# Driver code
g_map = [["a","b"],["b","c"],["a","e"],["d","e"]]
path_costs = [12.0,23.0,26.0,18.0]
drivers = ["c", "d", "e", "f"]
user = "a"
all_path_costs = get_total_cost(g_map, path_costs, drivers, user)
puts("Total cost of all paths "+ all_path_costs.to_s)
Plot and Select Path

Complexity measures

Time
...