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

}

- Chris November 11, 2017 | Flag Reply
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];
  }

- sudip.innovates November 13, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More