This is a solution to problem 28 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

Create a new array whose elements are the net gain or loss of gas after visiting each station. For example, if at station 2 there are 5 gallons of gas, and the distance to station 3 is 9 miles, then you would set a(2) to -4.

Now, starting at the beginning of this array, keep a running sum of the total amount of gas in your tank as you visit each station, allowing the value to go negative, and imagine a graph of this running sum. Note that if you had started at a different point in the array, the graph would look the same, just translated up or down so that the value at that point is 0. So all you have to do is remember the minimum value of this running sum, and the station at which you attained it. If you start at that station, the running sum will never go below 0, and you will never run out of gas.

-- Or --

Consider again the array of net gain or loss of gas at each station. You know that the sum of the array is 0. Starting at the beginning of the array, keep a running sum of the elements. As soon as this sum becomes negative, reset the sum and continue. So what you are doing is marking off segments of the array, each with a negative sum. Thus, you know that the last segment must have a positive sum, since the sum of all the segment sums must be 0. Start your car at the beginning of this last segment.

Note: I was given this question in an actual interview. I gave the first solution, and the interviewer said he hadn't heard that solution, and he gave me the second solution above. We wrote up the code for both solutions on the whiteboard:


// My solution
int racetrack(int stations, int* net_gas)
{
    int min = MAX_INT;
    int last = -1;

    for (int i = 0; i < stations; i++)
    {
        if (net_gas[i] < min)
        {
            min = net_gas[i];
            last = i;
        }
    }

    return last;
}

// His solution
int racetrack(int stations, int* net_gas)
{
    int sum = 0;
    int last = -1;

    for (int i = 0; i < stations; i++)
    {
        sum += net_gas[i];
        if (sum < 0)
        {
            sum = 0;
            last = i;
        }
    }

    return last;
}

It was a little creepy how similar the code looked structurally, but I guess that makes sense.

Log in or register to write something here or to contact authors.