Student Interview Question
Country: India
If I understand correct, assuming that the max. gas available at station located at distance
3 is 15
6 is 4
8 is 5
...
and we start with 17 units of gas to reach 20 units of distance.
let us consider the total gas required to reach the destination. At each stop let us determine if we need to refill with gas to get to the end or not.. if we see that the max. gas available at a station is less than required to reach the final destination, then we would have to stop at some other station to refill. If in some place before we reach destination we run out of gas, then the distance cannot be traversed.
A DP O(n) solution -
public static void main(String[] args){
int[] dist = {3, 6, 8, 15};
int[] gas = {15, 4, 5, 6};
int initialgas = 17;
int finaldistance = 20;
int n = minstops(dist, gas, initialgas, finaldistance);
System.out.println(n);
}
public static int minstops(int[] dist, int[] gas, int initialgas, int finaldistance){
int[] dp = new int[finaldistance+1];
int stationindex = 0;
int remaingas = initialgas;
int remaindistance = finaldistance;
for(int i = 0; i <= finaldistance; i++){
remaingas -=1;
remaindistance -= 1;
if(stationindex < dist.length && dist[stationindex] == i){
if(remaingas < remaindistance){
remaingas += gas[stationindex];
if(i > 0)
dp[i] = dp[i-1]+1;
}else{
if(i > 0)
dp[i] = dp[i-1];
}
stationindex +=1;
}else if(remaingas <= 0 && remaindistance > 0){
return -1;
}else{
if(i > 0)
dp[i] = dp[i-1];
}
}
return dp[finaldistance];
}
I assume there are no negative values for gas stations, so only direction you
can go, is right. It's not greedy, because in order to make the best decision you
need to look further then just the next gas station.
(Note:I assumed I can fill gas in, but after reviewing the given sample data I think the original question was, that you can take the gas, but you don't fill your tank up, you kind of replace the tank... if it's like this, there is a linear solution as well (I think)... anyway understanding this one will help creating the other one)
- Chris November 11, 2017