## Microsoft Interview Question

**Country:**United States

**Interview Type:**Written Test

gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

-Sort gasStation on the basis of remaining distance.

-Now start traversing from biggest remaining distance gas station to lower

-Keep track of upto what max distance we can ride in case opt for current gas station

-In case max distance capability is higher than previous max distance, override it else ignore

-Keep traversing upto distance current fuel capacity allows and we have our first stop to help us on longest ride in one gas filling stay. Save it in a list.

-Repeat all above step and keep adding optimal gas filling station in list.

-At the end we have all the required stops in list.

Time complexity:

=> Sorting: n log(n) + Traversing: n

=> n log (n)

Similar to leetcode 45 Jump Game II.

Generally it would be a dynamic programming solution. We either include the station or exclude it. 1) if we include the station, we add 1 stop to the result and add all gas; 2) if we exclude it, we add 0 stops and 0 gas. Something like this:

```
var incl = 1 + minStops(startIndex + 1, remainingGas + stations[startIndex].gas);
var excl = minStops(startIndex + 1, remainingGas);
return Math.min(incl, excl);
```

This would be O(N^2) with memoization because each function has 2 parameters.

But for some reason a greedy algorithm works here. Greedy algorithms almost never work, in 99% of cases dynamic programming is better, but this question for some reason is different. There should be a formal proof why a greedy algorithm works here, but I can't find it and can't prove it myself. But in the result it will be O(n):

```
var stations = [
{pos: 16, gas: 3},
{pos: 10, gas: 7},
{pos: 14, gas: 11},
{pos: 11, gas: 5},
{pos: 7, gas: 6}
];
stations.push({pos: 20, gas: 10}); // add initial stop
stations.push({pos: 0, gas: 0}); // add final stop
console.log('min stops to take: ' + minStopsGreedy(stations));
function minStopsGreedy(stations) {
// Sort by position descending
stations.sort((a, b) => b.pos - a.pos);
var lastStepReach = 0;
var currentStepReach = 0;
var step = 0;
for (var i = 0; i < stations.length; i++) {
var distFromStart = stations[0].pos - stations[i].pos;
if (distFromStart > lastStepReach) {
step++;
lastStepReach = currentStepReach;
}
currentStepReach =
Math.max(currentStepReach, lastStepReach + stations[i].gas);
}
if (currentStepReach < stations[0].pos) {
return Infinity;
}
return step;
}
```

The brute force is exponential; however, the solution below has TC = O(n^2) and SC = O(n).

- George Curious March 19, 2018