Bloomberg LP Interview Question
Software Engineer / DevelopersHere is what Cormen has to say about the above problem but i quite well did not understand the solution..
The optimal strategy is the obvious greedy one. Starting will a full tank of gas,
Professor Midas should go to the farthest gas station he can get to within n miles
of Newark. Fill up there. Then go to the farthest gas station he can get to within n
miles of where he Þlled up, and Þll up there, and so on.
Looked at another way, at each gas station, Professor Midas should check whether
he can make it to the next gas station without stopping at this one. If he can, skip
this one. If he cannot, then Þll up. Professor Midas doesnt need to know how
much gas he has or how far the next station is to implement this approach, since at
each Þllup, he can determine which is the next station at which hell need to stop.
This problem has optimal substructure. Suppose there are m possible gas stations.
Consider an optimal solution with s stations and whose Þrst stop is at the kth gas
station. Then the rest of the optimal solution must be an optimal solution to the
subproblem of the remaining m − k stations. Otherwise, if there were a better
solution to the subproblem, i.e., one with fewer than s −1 stops, we could use it to
come up with a solution with fewer than s stops for the full problem, contradicting
our supposition of optimality.
This problem also has the greedy-choice property. Suppose there are k gas stations
beyond the start that are within n miles of the start. The greedy solution chooses
the kth station as its Þrst stop. No station beyond the kth works as a Þrst stop,
since Professor Midas runs out of gas Þrst. If a solution chooses a station j < k as
its Þrst stop, then Professor Midas could choose the kth station instead, having at
least as much gas when he leaves the kth station as if hed chosen the j th station.
Therefore, he would get at least as far without Þlling up again if he had chosen the
kth station.
If there are m gas stations on the map, Midas needs to inspect each one just once.
The running time is O(m).
For each station, find (distance that can be traveled with gas available in that station - distance to next station). Create an array of these values and find the maximum positive consecutive substring. You have to start driving at the beginning of this substring.
PS: Remember that the stations are circularly arranged, so should the array. So it is possible for you to start on the "last" station and still go around to all of them.
PPS: Another thing that can be done is to ensure that sum of all distances to be traveled is less than distance that can be traveled with available gas. Otherwise, it makes not difference where you start, you will get stranded.
Basically you have two arrays, gas_needed[n] and gas_at_station[n]. However, I would work with a third array which is the difference gas_needed - gas_at_station. Let's call this array gas_remaining[n](R[n])
Sum(Ri) where m is the nth consecutive station after i. i is the starting station if
i->m
the sum never goes negative.
O(m)
class GasStation {
public static int canCompleteCircuit(int[] gas, int[] cost) {
if(gas == null || cost == null) return -1;
int total = 0;
int upToNow = 0;
int startPos = 0;
for(int i=0; i<gas.length; i++) {
int delta = gas[i] - cost[i];
if(upToNow >= 0) upToNow += delta;
else {
upToNow = delta;
startPos = i;
}
total += delta;
}
return total >= 0 ? startPos : -1;
}
public static void main(String[] args) {
int[] gas = {3,5,7};
int[] cost = {8,4,3};
System.out.println(canCompleteCircuit(gas, cost));
}
}
O(n^2) time is easy. Start at each and just simulate it out.
O(n) time is possible, but I won''t spoil it for you.
Cookie, no, that's not the problem. Therefore that's not the solution :))
I won't give the full solution how to do it in O(n), but I will provide all the hints.
The problem can be cast into a modified version of the very know problem: Maximum Consecutive Subsequence (of length 2*n-1). If during the search (in linear time for Maximum Consecutive Subsequence) you find a positive sum of length n, you found the solution to this problem.
Bajanfella, Your algorithm is O(m^2) instead of O(m). Basically, you are just simulating with different starting points.
A linear solution for this problem,
For every station a ( starting point of the trip)
calculate the carry over gas from station a to other stations in the trip , if there is a negative carry over mark this station unsuitable for starting the trip. ( this can be done O(n) for all stations).
let's say gasMinusDist represents value of gas at a station minus the distance from this station to next station.
- nutcracker February 15, 2011take example: 5,-10,4,6,-10,5,5 as 7 values. Since this is circular , so we can write this array as 5,-10, 4,6,-10,5,5,5,-10,4,6,-10,5 so that if we start from last gas station, we can still go through the round
code will look like
int delta=0; int count=0;
for int(i=0;i<2*n-1;i++)
{
delta+=gasMinusDist[i];
if (delta<0)/*not fit to start with this iteration
{delta=0;count=0;continue;}
count++; if (count==n) break;
}
if (count ==n)printf("start round from gas station number %d,i-count+1);
else printf("not possible...");