make the full circular path, shortest path exercis

Question

I got this question in an interview and I was not able to solve it.

You have a circular road, with N number of gas stations. You know the ammount of gas that each station has. You know the ammount of gas you need to GO from one station to the next one. Your car starts with 0 gas. The question is: Create an algorithm, to know from which gas station you must start driving to COMPLETE the circular PATH. It does not specify that you must visit all stations. You can only drive clockwise.

I had to do it in c#

The only code I started is with a GasStation entity

class GasStation
  int gasAtStation;
  int gasToMoveToNextStationNeeded;
  string nameOfGasStation;


GasTation wheretoStart(List<GasStation> list)
{

}

I did it this way:

static void Main(string[] args)
        {
            int[] gasOnStation = {1, 2, 0, 4};
            int[] gasDrivingCostTonNextStation = {1, 1,2, 1};

            FindStartingPoint(gasOnStation, gasDrivingCostTonNextStation);

        }

        static void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts)
        {
            // Assume gasOnStation.length == gasDrivingCosts.length
            int n = gasOnStation.Length;
            int[] gasEndValues = new int[n];
            int gasValue = 0;
            for (int i = 0; i < n; i++)
            {
                gasEndValues[i] = gasValue;
                gasValue += gasOnStation[i];
                gasValue -= gasDrivingCosts[i];
            }

            if (gasValue < 0)
            {
                Console.WriteLine("Instance does not have a solution");
                Console.ReadLine();
            }
            else
            {
                // Find the minimum in gasEndValues:
                int minI = 0;
                int minEndValue = gasEndValues[0];
                for (int i = 1; i < n; i++)
                {
                    if (gasEndValues[i] < minEndValue)
                    {
                        minI = i;
                        minEndValue = gasEndValues[i];
                    }
                }

                Console.WriteLine("Start at station: " + minI);
                Console.ReadLine();
            }
        }

Thanks

Answer 1

If we define that a trip from station A to B comprises of the GasAtStation A and TripCost. Then for each trip we have that TripBalance = GasAtStation-TripCost

The sum of all the trip balances must be greater or equal to zero, otherwise a solution does not exist. The solution consists of having a list with the trip balances for each gas station and iterate through the items keeping a variable for the tripBalance, if the tripBalance becomes negative, then the trip should start at the next gas station, if so, we reset the tripBalance and we keep processing until we check the last entry in the list:

public int FindFirstStation(List<int> tripBalances)
{
  if (tripBalances.Sum() < 0) return -1;
  var firstStation = 0;
  var tripBalance = 0;

  for (int i = 0; i < tripBalances.Count; i++)
  {
    tripBalance += tripBalances[i];
    if (tripBalance < 0)
    {
      tripBalance = 0;
      firstStation = i + 1; // next station
    }
  }
  return firstStation;
}

I tested it using the following code:

[TestMethod]
public void Example()
{
  var tripBalances = new List<int> { 0, 1, -2, 3 };
  var resolver = new GasStationResolver();
  var indexOfGasStation = resolver.FindFirstStation(tripBalances);
  Assert.AreEqual(3, indexOfGasStation);
}

See that the passed values are the ones worked out from the example given at the question header. In this case, the answer is that the last gas station in our list should be the first gas station. Finally, if there is not solution, the method returns -1.

Another example to cover where the stations with higher gas are not the solution:

/// <summary>
/// Station 1 - Gas: 3   Cost: 4
/// Station 2 - Gas: 10  Cost: 11
/// Station 3 - Gas: 8   Cost: 9
/// Station 4 - Gas: 6   Cost: 3
/// Station 5 - Gas: 4   Cost: 2
/// 
/// Then - Trip Balances are:
/// Station 1 - -1
/// Station 2 - -1
/// Station 3 - -1
/// Station 4 -  3
/// Station 5 -  2
/// </summary>
[TestMethod]    
public void SecondExample()
{
  var tripBalances = new List<int> { -1, -1, -1, 3, 2 };
  var resolver = new GasStationResolver();
  var indexOfGasStation = resolver.FindFirstStation(tripBalances);
  Assert.AreEqual(3, indexOfGasStation);
}

Answer 2

This is optimized case of @George Duckett's answer.

• Choose and remember your start station.
• Loop(1) through stations clockwise.
  • Get a fuel.
  • If you have enough fuel, go to next station, decrease remaining fuel amount, continue loop(1)

If you reached your start station - problem solved.

If on some station you do not have enough fuel to reach next one

• Remember your end station.
• Distance_to_start = 0, fuel_to_start = 0
• Loop(2) from your start station counterclockwise.
  • Add available fuel and distance to next station to your counters
  • If fuel_to_start > distance_to_start, you have some excess fuel. Mark this station as your new start and go to loop(1) again - may be you can go ahead now.
  • Otherwise, continue loop(2)

If you had gone counterclockwise to already visited station - bad luck, there is not enough fuel on stations to go full circle.