Sales Path
The car manufacturer Honda holds their distribution system in the form of a tree (not necessarily binary). The root is the company itself, and every node in the tree represents a car distributor that receives cars from the parent node and ships them to its children nodes. The leaf nodes are car dealerships that sell cars direct to consumers. In addition, every node holds an integer that is the cost of shipping a car to it.
Take for example the tree below:
A path from Honda’s factory to a car dealership, which is a path from the root to a leaf in the tree, is called a Sales Path. The cost of a Sales Path is the sum of the costs for every node in the path. For example, in the tree above one Sales Path is 0→3→0→10, and its cost is 13 (0+3+0+10).
Honda wishes to find the minimal Sales Path cost in its distribution tree. Given a node rootNode, write a function getCheapestCost that calculates the minimal Sales Path cost in the tree.
Implement your function in the most efficient manner and analyze its time and space complexities.
For example:
Given the rootNode of the tree in diagram above
Your function would return:
7 since it’s the minimal Sales Path cost (there are actually two Sales Paths in the tree whose cost is 7: 0→6→1 and 0→3→2→1→1)
Give it a try using the code editor!
Stuck? Make sure you fully understand what's being asked. Can you find the minimum sales path(s) in the above example?
Practice by diagramming an example tree and finding all the possible paths there. The tree in the question is abstract, but if it helps to concretize the problem, you can assume that the function initially gets a tree node, and that every node has a field holding the cost, and an array holding its children nodes.
Try dividing the paths per child of the root node.
What would happen if you input the function of the children of the root node? Given that, go back and look for the connection between the function's value on the root, and on every child node. What's the runtime and space requirements for your answer? If not O(N) for both, you can do better.
What's the runtime and space requirements for your answer? If not O(N) for both, you can do better!
Obviously iterating through all paths again and again is not a good solution, since its wasteful in terms of time and memory. But intuitively if we find a solution that uses previous calculations somehow. This hints that the solution should involve recursion in some manner.
First we notice that if the root is also a leaf, the best Sales Path, is simply the value in the node itself. This is the base case for the solution. If the root has children, then the minimal Sales Path is also a minimal path from the root’s child. Thus, if we already know the minimal cost for the root’s children, then the minimal cost for the root is simply the minimum of the values for its children plus the value stored in the root itself. A solution to this question, using these facts is given below:
Pseudocode:
function getCheapestCost(rootNode): n = rootNode.numberOfChildren() if (n == 0): return rootNode.cost else: # initialize minCost to the largest integer in the system minCost = MAX_INT for i from 0 to n-1: tempCost = getCheapestCost(rootNode.child[i]) if (tempCost < minCost): minCost = tempCost return minCost + rootNode.cost
Time Complexity: let N be the number of nodes in the tree. Notice that getCheapestCost is applied to every node exactly once. Therefore, there are overall O(N) calls to getCheapestCost.
Space Complexity: every time the function recurses,
it consumes only a constant amount of space. However, due to the nature
of the recursion we used, the stack call holds N instances of getCheapestCost which makes the total space complexity to be O(N).
MAX_INT = float('inf')
def get_cheapest_cost(rootNode):
if not rootNode.children:
return rootNode.cost
else:
minCost = MAX_INT
for child in rootNode.children:
tempCost = get_cheapest_cost(child)
if tempCost < minCost:
minCost = tempCost
return minCost + rootNode.cost
# A node
class Node:
# Constructor to create a new node
def __init__(self, cost):
self.cost = cost
self.children = []
self.parent = None
def get_cheapest_cost(rootNode): # need to do DFS for each branch # but this can be done recursively n = len(rootNode.children) if n == 0: return 0 else: min_cost = float('inf') for i in range(len(n)): temp_cost = get_cheapest_cost(rootNode.children[i]) if (temp_cost < min_cost): min_cost = temp_cost return min_cost + rootNode.cost # A node class Node: # Constructor to create a new node def __init__(self, cost): self.cost = cost self.children = [] self.parent = None