## Microsoft Interview Question

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

``````import java.util.Arrays;
import java.util.Collections;

class GasStation implements Comparable<GasStation> {
double distance;
double fuelGallons;

public GasStation(double distance, double fuelGallons) {
this.distance = distance;
this.fuelGallons = fuelGallons;
}

@Override
public int compareTo(GasStation o) {
return Double.compare(this.distance, o.distance);
}
}

public class GasStationStops {
public static final int INSUFFICIENT_CREDIT = -1;
public static final int NO_EXACT_MATCH = -2;

static int find(GasStation[] gasStations, double availableGallons, double maxDistance) {
if (gasStations == null || gasStations.length == 0) {
return INSUFFICIENT_CREDIT;
}
Arrays.sort(gasStations, Collections.reverseOrder());
if (maxDistance < gasStations.distance) {
return INSUFFICIENT_CREDIT;
}

double[] requiredGallons = new double[gasStations.length + 1];
double currentDistance = 0.0;
int reGlIndx = 1;
for (int gasStIndx = gasStations.length - 1; gasStIndx >= 0; gasStIndx--) {
GasStation gasStation = gasStations[gasStIndx];
updateRequiredGallons(requiredGallons, reGlIndx, gasStation.distance - currentDistance, gasStation.fuelGallons);
currentDistance = gasStation.distance;
reGlIndx++;
}
double distanceToFirstLocation = maxDistance - gasStations.distance;
System.out.print(Arrays.toString(requiredGallons));
return binarySearch(requiredGallons, availableGallons - distanceToFirstLocation, 0, requiredGallons.length - 1);
}

private static void updateRequiredGallons(double[] requiredGallons, int reGlIndx, double delta, double moreGallons) {
for (int i = 0; i < reGlIndx; i++) {
requiredGallons[i] += delta;
}
requiredGallons[reGlIndx] = requiredGallons[reGlIndx - 1] - moreGallons;
for (int j = reGlIndx - 1; j > 0; j--) {
requiredGallons[j] = Math.min(requiredGallons[j - 1] - moreGallons, requiredGallons[j]);
}
}

private static int binarySearch(double[] a, double target, int i, int j) {
if (i < 0 || i >= a.length || j < 0 || j >= a.length || i > j)
return NO_EXACT_MATCH;

int m = (i + j) / 2;
if (a[m] == target)
return m;

int p;
if (target < a[m]) {
p = binarySearch(a, target, m + 1, j);
if (p == NO_EXACT_MATCH) {
return m < a.length - 1 ? m + 1 : INSUFFICIENT_CREDIT;
}
} else {
p = binarySearch(a, target, i, m - 1);
if (p == NO_EXACT_MATCH) {
return m;
}
}
return p;
}

public static void main(String[] args) {
print(find(null, 10, 20));
print(find(new GasStation[]{}, 10, 20));
print(find(new GasStation[]{
new GasStation(16, 3),
new GasStation(10, 7),
new GasStation(14, 11),
new GasStation(11, 5),
new GasStation(7, 6)}, 10, 20));
print(find(new GasStation[]{
new GasStation(15, 4),
new GasStation(10, 7),
new GasStation(5, 3)}, 10, 20));
print(find(new GasStation[]{
new GasStation(10, 7),
new GasStation(15, 4),
new GasStation(5, 3)}, 10, 20));
print(find(new GasStation[]{
new GasStation(10, 7),
new GasStation(15, 4),
new GasStation(5, 3)}, 6, 20));
print(find(new GasStation[]{
new GasStation(10, 7),
new GasStation(15, 4),
new GasStation(5, 3)}, 9, 20));
print(find(new GasStation[]{
new GasStation(10, 7),
new GasStation(15, 4),
new GasStation(5, 3)}, 12, 20));
print(find(new GasStation[]{
new GasStation(10, 7),
new GasStation(15, 4),
new GasStation(5, 3)}, 13, 20));
print(find(new GasStation[]{
new GasStation(10, 6),
new GasStation(15, 3),
new GasStation(5, 1)}, 10, 20));
print(find(new GasStation[]{
new GasStation(10, 1),
new GasStation(15, 1),
new GasStation(5, 1)}, 10, 20));
}

static void print(int x) {
if (x == INSUFFICIENT_CREDIT) {
System.out.println("Min # Stops:INSUFFICIENT INITIAL GALLONS");
} else {
System.out.println(", Min # Stops:" + x);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If you have :
eg: gas = 10 , distance = 20
gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

Then how can you opt for 14,11? because the initial gas itself is 10, Hence the only option for you is either , 10,7 or 7,6

I can think of Backtrack as one of the way to solve this

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.pos - stations[i].pos;
if (distFromStart > lastStepReach) {
step++;
lastStepReach = currentStepReach;
}

currentStepReach =
Math.max(currentStepReach, lastStepReach + stations[i].gas);
}

if (currentStepReach < stations.pos) {
return Infinity;
}

return step;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

struct station
{
int dist;
inr gas;
};
int Find( station gasStation[], int dist, int gas, int n)
{
//sort gas station array w.r.t to its gas quantity.
//{(14,11) ,(10,7) ,(7,6),(11,5),(16,3)}
sort(gasStation , 0 , n);
int count = 0;
for(int i = 0; i < n; i++)
{
if(dist - gasStation[i].dist > gas)
continue;
gas = dist - gasStation[i].dist + gasStation[i].gas;
dist = gasStation[i].dist;
count++;
if(gas >= dist)
return count;
}
return -1;

Comment hidden because of low score. Click to expand.
0
of 0 vote

871. Minimum Number of Refueling Stops in leetcode
has both dp and greedy solution approaches

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.