← All questions
Coding

Minimum Travel Cost

Asked atGoogle
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

Mocha and his friend wants to go on a vacation trip but they live in different cities. There are total of n cities given in form a binary tree rooted at vertex 1. To meet each other Mocha and his friend always stat travelling from their city towards the root.

For travelling each city they need to fill their fuel tank and you are given the cost required to fill the tank at each vertex. You need to fill the tank each city you visit. Mocha and his friend travel until they meet for the first time at same vertex/city.

You will be given binary tree **rooted **at vertex 1 and an array 'cost' (1-based indexing) which contains the cost of fuel required to fill at each vertex i.e. cost to refill the fuel at ith vertex is cost[i] (1 <= i <=n). All cities have a unique rule that once they sell their fuel then next time they need to reduce the cost to half of current cost (floor value should be considered).

You will be asked q queries which contains the start cities of Mocha(x) and his friend(y). You need to find the total cost spent by Mocha and his friend together on all of their trips in each city i.e. Cost spent for fuel on each vertex after all the queries.

Input : cost = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], root = 1 2 3 4 5 6 7 8 null null null null null 9 10 , queries = [ [4, 7], [8, 10], [4, 5], [6, 7], [2, 3] ] Output : [1, 3, 4, 7, 5, 6, 11, 8, 0, 10] **Explanation : ** 1st query -> traverse from vertex 4 to 7 and they meet at common vertex 1 for first time. The path is 4 -> 2-> 1 <- 3 <- 7. 2nd query -> traverse from vertex 8 to 10 and they meet at common vertex 1 for first time. The path is 8 -> 4 -> 2 -> 1 <- 3 <- 7 <- 10. 3rd query -> traverse from vertex 4 to 5 and they meet at common vertex 2 for first time. The path is 4 -> 2 <-5. 4th query -> traverse from vertex 6 to 7 and they meet at common vertex 3 for first time. The path is 7 -> 3 <- 6. 5th query -> traverse from vertex 2 to 3 and they meet at common vertex 1 for first time. The path is 2 -> 1 <- 3.

Cost spent on vertex 7 is calculated as below :

  • So vertex 7 is traversed in query 1, 2, 4.
  • So initial cost is 7 for tank refill. So after traversal in 1st query the cost is halved i.e. becomes 7/2 -> 3.5 -> 3.
  • After traversal in 2nd query cost is halved again 3/2 -> 1.5 -> 1.
  • After traversal in 4th query cost is halved again 1/2 -> 0.5 -> 0. So total money spent by Mocha and his friend on 7th vertex/city after all the queries is 7 + 3 + 1 => 11. Similarly we calculate the total cost spent for each vertex.

Input : cost = [3, 5, 4, 6], root = 1 3 2 4 , queries = [ [2, 3] ] Output : [3, 5, 4, 0] **Explanation : ** 1st query traversal path => 2 -> 1 <- 3. Cost at vertex1 -> 3. Cost at vertex 2 -> 5. Cost at vertex 3 -> 4. Cost at vertex 4 -> 0.

Input : cost = [10, 6, 6, 6, 10, 10], root = [1, 2, 4, 3, 5, null, null, 6], queries = [ [3, 5], [2, 6] ]

  • 1 <= n, q <= 1000
  • 1 <= cost[i] <= 104
  • 1 <= queries[i][0], queries[i][1] <= n

cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int data;
 *     TreeNode *left;
 *     TreeNode *right;
 *      TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
 * };
 **/

class Solution{

    public:
        vector<int> travel_cost(vector<int>& cost,vector<vector<int>>& queries, TreeNode* root){
            //your code goes here
        }
};

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int data;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { data = val; left = null, right = null }
 * }
 **/

class Solution {
    public int[] travelCost(int[] cost, int[][] queries, TreeNode root) {
        //your code goes here
    }
}

python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.data = val
#         self.left = left
#         self.right = right

class Solution:
    def travel_cost(self, cost, queries, root):
        #your code goes here

javascript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *      constructor(val = 0, left = null, right = null){
 *          this.data = val;
 *          this.left = null;
 *          this.right = null;
 *      }
 * }
 **/

class Solution {
    travel_cost(cost, queries, root) {
        //your code goes here
    }
}

csharp

/*
public class TreeNode {
    public int Val;
    public TreeNode Left;
    public TreeNode Right;
    public TreeNode Parent;

    // public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
    //     Val = val;
    //     Left = left;
    //     Right = right;
    // }
}
*/

public class Solution {
    public List<long> TravelCost(List<int> initialCosts, List<int[]> queries, TreeNode root) {
        // Your code goes here
    }
}

go

func travel_cost(cost []int, queries [][]int, root *TreeNode) []int {

}
Stuck? Show a way to structure it+
  1. 01Identify the meeting city as the LCA of the two starts.
  2. 02Apply each traveler's path contribution up to that LCA.
  3. 03Update each visited city's current fuel price after a purchase.
  4. 04Use preprocessing or path techniques according to query constraints.

Reference answer

Then expect these follow-ups

  • How would binary lifting accelerate LCA queries?

    Tests: tree preprocessing

  • What data structure supports many path updates and queries?

    Tests: heavy-light decomposition

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with EnzoSign up free

Next question