Recibí esta pregunta en una entrevista y no pude resolverla.

Tiene una carretera circular, con N número de estaciones de servicio. Conoces la cantidad de gas que tiene cada estación. Usted sabe la cantidad de gas que necesita para IR de una estación a la siguiente. Su automóvil comienza con 0 gasolina. La pregunta es: cree un algoritmo para saber desde qué estación de servicio debe comenzar a conducir para COMPLETAR la RUTA circular. No especifica que debe visitar todas las estaciones. Solo puede conducir en sentido horario.

Tuve que hacerlo en c #

El único código que comencé es con una entidad de GasStation

class GasStation
  int gasAtStation;
  int gasToMoveToNextStationNeeded;
  string nameOfGasStation;


GasTation wheretoStart(List<GasStation> list)
{

}

Lo hice de esta manera:

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();
            }
        }

Gracia