## Student Interview Question

Country: India

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

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)

``````/*

0-----3-----6---8----------15-----20
(17)  15    4   5          6      (0)

the problem is more convenient to talk about if we include start gas and end position
int the arrays and subtract at the end one from the solution (one stop less).

pos = [0, 3 , 6, 8, 15, 20]
gas = [17, 15, 4, 5,  6, 0]

at a certain point you have two options, take the gas or leave it there.

rec(i, g) = min{
infinity, if g < 0 // can't reach
0, if i == n-1 and g >= 0 // no more stop needed
rec(g - (pos[i+1] - pos[i]))
rec(g - (pos[i+1] - pos[i]) + gas[i]) + 1
}

rec(0, 0) would then be the solution of the recursion

note that this has time complexity of 2^n and will most likely exceed the time given
to find a solution.

next question is how to improve it.

look for a common subproblem... i think about it like this, I can make it to each gas
station with index i doing at most i-1 stops. But I eventually can get there with i-2
stops in multiple ways, i-2 to be exact. How ever, I only am intersted in the max gas
of all i-2 stops. etc.

so I keep an array gas_stops[n][n] which holds the max amount of gas for a certain amount
of stops per iteration (later we can optimize this to two arrays of size n)
it starts with gas_stops[0][0] = start_gas, all other elements must be -1

for(int i = 1; i < n; ++i) {
int dist = pos[i] - pos[i-1]; // how far to travel
for(int stops = 0; stops < n; ++stops) {
if(gas_stops[i-1][stops] >= dist) { // can I make it to this stop
gas_stops[i][stops] = max(gas_stops[i][stops], gas_stops[i-1][stops]-dist); // don't pick up gas at i
gas_stops[i][stops+1] = max(as_stops[i][stops + 1], gas_stops[i-1][stops]-dist+gas[i]); // pick up gas at i
}
}
}

// get the least stops for the last station
for(int stops = 0; stops < n; ++stops) {
if(gas_stops[n-1][i] >= 0) return stops;
}

since we only access gast_stops[i-1] and [i] we only need two arrays at a certain time

so we end up with an O(n^2) time and O(n) space complexity solution for this common problem
*/
#include <vector>
#include <iostream>
#include <limits>
#include <algorithm>

using namespace std;

// -- recursive brute force version --
int min_stops_rec(const vector<int>& pos, const vector<int>& gas, int g, int i)
{
if (g < 0) return numeric_limits<int>::max(); // ran out of gas
if (i + 1 == pos.size()) return 0; // reached last station
int dist = pos[i + 1] - pos[i]; // distance
return min(min_stops_rec(pos, gas, g - dist, i + 1), // don't pick up gas
1 + min_stops_rec(pos, gas, g - dist + gas[i], i + 1)); // pick up gas
}

int min_stops_rec(const vector<int>& pos, const vector<int>& gas)
{
return min_stops_rec(pos, gas, 0, 0) - 1;
}

// -- optimized version (space optimization not done for better readability) --
int min_stops_opt(const vector<int>& pos, const vector<int>& gas)
{
int n = pos.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
dp[0][0] = gas[0];
for (int i = 1; i < n; ++i) {
int dist = pos[i] - pos[i - 1];
for (int stops = 0; stops < n; ++stops) {
if (dp[i - 1][stops] >= dist) {
dp[i][stops] = max(dp[i][stops], dp[i - 1][stops] - dist);
dp[i][stops + 1] = max(dp[i][stops + 1], dp[i - 1][stops] - dist + gas[i]);
}
}
}
for (int i = 1; i < n; ++i) {
if (dp[n - 1][i] >= 0)
return i;
}
return numeric_limits<int>::max(); // can't make it
}

int main()
{
cout << min_stops_rec({ 0, 3, 6, 8, 15, 20 }, { 17, 15, 4, 5, 6, 0 }) << endl; // 1 stop at 15 or 1 stop at 3
cout << min_stops_opt({ 0, 3, 6, 8, 15, 20 }, { 17, 15, 4, 5, 6, 0 }) << endl; // 1 stop at 15 or 1 stop at 3

// other example
cout << min_stops_rec({ 0, 2, 4, 5, 10, 15 }, { 5, 10, 20, 10, 5, 0 }) << endl; // 1 stop at 5
cout << min_stops_opt({ 0, 2, 4, 5, 10, 15 }, { 5, 10, 20, 10, 5, 0 }) << endl; // 1 stop at 5

}``````

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

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];
}``````

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.