Decode the Coding Interview in Rust: Real-World Examples/

...

/

Gas Station

Gas Station

Understand and solve the interview question "Gas Station".

We'll cover the following...

Description

Suppose there are n gas stations identified by integers 0, 1, . . ., n-1, where the amount of gas at the ithi^{th} station is gas[i]. Imagine that these gas stations are arranged clockwise in a circle, as shown below.

You have a car with an unlimited gas tank. It costs cost[i] amount of gas to travel from the ithi^{th} station to the (i+1)th(i + 1)^{th} station. The trip will begin with an empty tank at one of the gas stations.

Given two integer arrays, gas and cost, you have to return the starting gas station’s index if you can travel around a circular route in the clockwise direction, otherwise, return -1.

If a solution exists, it is guaranteed to be unique.

Let’s review a few examples below:

Coding exercise

Press + to interact
fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>)-> i32 {
    // write your code here
    return 0;
}

Solution

Before getting to the solution, let’s discuss a couple of things:

  1. We cannot perform the road trip if sum(gas) < sum(cost). In this situation, the answer will be -1. We can compute the total amount of gas in the tank, total_tank = sum(gas) - sum(cost), during the round trip. The round trip is only possible if total_tank >= 0, otherwise we return -1.

  2. We cannot start the trip at a station i if gas[i] - cost[i] < 0, because then there is not enough gas in the tank to travel to the i + 1 station. Let’s say we have a curr_tank variable that keeps track of the current amount of gas in the tank. If at a station curr_tank is less than 0, this means that we cannot reach this station. Then, we need to mark this station as a new starting point and reset curr_tank to 0 since, at this station, we start with no gas in the tank.

The following illustration shows these steps in detail:

Algorithm

The algorithm to solve this problem is as follows:

  1. We initialize the total_tank and curr_tank variables as zero. We also choose station 0 as a starting station.
  2. Iterate over all the stations:
    • Update total_tank and curr_tank at each step, by adding gas[i] and subtracting cost[i].
    • If curr_tank is less than 0 at the i + 1 station, we will make i + 1 station a new starting point and reset curr_tank to 0 to start with an empty tank.
  3. Finally, we will return -1 if total_tank < 0 or the starting gas station’s index otherwise.

Solution intuition

Suppose we have a situation where total_tank >= 0 and the algorithm above returns NsN_{s} as the starting station. Our algorithm ensures that we can reach station 0 from NsN_{s}. But what about going from station 0 to NsN_{s}? We need to ensure that we can loop around to NsN_{s}.

Let’s use proof by contradiction and assume that there exists a station 0<k<Ns{0 < k < N_{s}} ...