6

I got this question in an interview and I was not able to solve it.

  • You have a circular road, with N number of gas stations.
  • You know the amount of gas that each station has.
  • You know the amount of gas you need to GO from one station to the next one.
  • Your car starts with 0.
  • You can only drive clockwise.

The question is: Create an algorithm, to know from which gas station you must start driving so that you complete a full circle.

As an exercise to me, I would translate the algorithm to C#.

  • Assuming that you start from one of the gas stations, do you have to get back to the same one or the one just before it? – NoChance Nov 15 '11 at 11:19
  • You have said that "You know the ammount of gas that each station has" - can each station have different amounts of gas? – user4234 Nov 15 '11 at 11:37
  • yes, each one can have a different ammount of gas. – Luis Valencia Nov 15 '11 at 11:38
  • 2
    First of all, this will not necessarily be possible. In fact, you may never make it to the next station no matter where you start. Secondly, is there a limit on how much gas the car can take in? – Job Nov 15 '11 at 16:30
  • Ok if assignment is like this (no limit to amount of fuel, no optimal solution), why just not try to start at every gas station and add maximum fuel it has and substract distance for next leg. If amount of fuel is negative continue with next start point, otherwise stop if you managed to reach your start point again.... Are you sure there's no limit? With limit it starts to be interesting problem. – MaR Nov 15 '11 at 17:36
23

(Update: now allows a gas tank size maximum)

You can solve this in linear time as follows:

void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts, int gasTankSize)
{
  // Assume gasOnStation.length == gasDrivingCosts.length
  int n = gasOnStation.length;

  // Make a round, without actually caring how much gas we have.
  int minI = 0;
  int minEndValue = 0;
  int gasValue = 0;
  for (int i = 0; i < n; i++)
  {
    if (gasValue < minEndValue)
    {
      minI = i;
      minEndValue = gasValue;
    }
    gasValue = gasValue + gasOnStation[i] - gasDrivingCosts[i];
  }

  if (gasValue < 0)
  {
    Console.WriteLine("Instance does not have a solution: not enough fuel to make a round.");
  }
  else
  {
    // Try a round.
    int gas = DoLeg(0, minI, gasTankSize);
    if (gas < 0)
    {
      Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
      return;
    }
    for (int i = (minI + 1) % n; i != minI; i = (i + 1) % n)
    {
      gas = DoLeg(gas, i, gasTankSize);

      if (gas < 0)
      {
        Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
        return;
      }
    }
    Console.WriteLine("Start at station: " + minI);
  }
}
int DoLeg(int gas, int i, int gasTankSize)
{
  gas += gasOnStation[i];
  if (gas > gasTankSize) gas = gasTankSize;
  gas -= gasDrivingCosts[i];
  return gas;
}

First, we look at the case where we don't have a gas tank with a maximum.

Essentially, in the first for-loop, we just drive the circle around, not caring if our fuel tank has negative fuel or not. The point of this is that no matter where you start, the difference between how much there is in your fuel tank at the start (0) and at the end is the same.

Therefore, if we end up with less fuel than we started (so less than 0), this will happen no matter where we start, and so we can't go a full circle.

If we end up with at least as much fuel as we started after going a full circle, then we search for the moment our fuel tank was at its lowest point (which is always just as we get to a gas station). If we start at this point, we will never end up with less fuel than at this point (because it is the lowest point and because we don't lose fuel if we drive a circle).

Therefore, this point is a valid solution, and in particular, there always is such a point.

Now we'll look at the version where our gas tank can hold only so much gas.

Suppose our initial test (described above) we found out it is not impossible to go the entire circle. Suppose that we start at gas station i, we tank at gas station j, but our gas tank ends up being full, so we miss out on some extra gas the station has available. Then, before we get to station k, we end up not having enough fuel, because of the gas we missed out on.

We claim that in this scenario, this will end up happening no matter where you start. Suppose we start at station l.

If l is between j and k, then we either stop (long) before we can get to station k because we started at a bad station, or we'll always have at most the amount of fuel that we had when we started at i when we try to get to k, because we passed through the same stations (and our tank was full when we passed j). Either case is bad.

If l is not between j and k, then we either stop (long) before we get to j, or we arrive at j with at most a full tank, which means that we won't make it to k either. Either case is bad.

This means that if we make a round starting at a lowest point just like in the case with the infinitely large gas tank, then we either succeed, or we fail because our gas tank was too small, but that means that we will fail no matter which station we pick first, which means that the instance has no solution.

  • 2
    Is it "Perfect"? In the real world, a car fuel tank cannot hold all the gas a station has. Although this answer solves the stated problem, it is unlikely to provide a useable real world solution. These interview questions are designed to test this kind of software developer skill. i.e. Do you blindly code to the requirements, or do you ask questions and clarify when the requirements appear incorrect or inconsistent with the real world. – mattnz Nov 16 '11 at 22:04
  • 4
    @mattnz: on one hand, you're right: as a software engineer, you should always make sure your requirements are clear and appropriate for the situation. However, this question is clearly not a real-life situation: why'd we want to drive in a circle on this road? Why can we start at any station we like? Does an airplane drop us off at a station? Either the question was purely to test algorithmic skills, or the question is a reformulation of an actual question, and in the actual question the equivalent of the gas tank has unlimited capacity. Or at least, that's how I look at it. – Alex ten Brink Nov 16 '11 at 23:16
  • Indeed, it's a correct answer to the question as asked, and presumably as intended. However, now I'm curious to know if the solution does work if the car can only hold a max, or if not, if there's an alternative that would. – Jack V. Nov 17 '11 at 16:46
  • @JackV.: see my update for a modified algorithm that also handles the case where the gas tank isn't infinitely large. – Alex ten Brink Nov 17 '11 at 19:10
  • I read that.... paying huge attention!!! to try follow the "solution".... to read the last line, which is what i kept thinking... the whole time and was waiting to be wow'ed. +1 dude – Seabizkit Dec 7 '16 at 10:04
9

It looks like a derivation of the shortest path algorithm, so you basically consider each station to be a vertex of a graph, and the edges are weighted to their distance (in terms of fuel).

Then you can use an adaptation of Dijkstra to solve it -> http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

  • I didn't mean Dijkstra algorithm, but an adaptation of it. – Daniel Scocco Nov 15 '11 at 11:56
5

My first response would be "The requirements appear to be incomplete, are you sure you want me to write the code based on these requirements alone, shall we make them up as we go, or would you like my help completing the requirements before we design the software?".

The incomplete requires are, as stated in other questions, Fuel capacity of the car. End point - is it the start point or the station before the start point. (I think you answer this in your comment "complete a full circle implies end = start, in that case. I would clarify this as it is not explicit) The question implies there is one, and only one solution, is this correct.

Other issues Is performance of the algorithm a concern, or put another way, what is the budget for this project.

It's a good question - you cannot answer it in it's current form and be certain you have provided the customer with the solution to the problem he is expecting.

  • 1
    +1, fair assumptions. Some requirements are not fully specified. – NoChance Nov 16 '11 at 0:20
5

I feel like given quiz is missing some vital parts. However, in my reasoning I would use following assumptions:

  • Car tank have unlimited fuel capacity
  • It's possible to travel clockwise only
  • Car starts with 0 gas
  • Car should finish in the same gas station

Given this assumptions, the task can be easily brute forced with O(n**2) complexity, by trying all gas stations.

If it's required more robust solution, it's possible to transform this quiz to maximum continuous sub-sequence problem with extra constrains, that it should't go below zero. The complexity of this algorithm is O(n) - linear.

For first step, lets transform our initial problem to problem that is solvable by maximum sub-sequence by summing amount of gas at gas station and cost of going to that station.

Second step is to apply maximum sub-sequence algorithm. The algorithm is based on 2 assumptions:

  • if gas counter went below 0, that is always better to restart from current gas station
  • otherwise it's better just to fill-in the tank, since it's more than 0 gas here

Applying this algorithm to the circled list of the stations 2 times (2 overlapping sequences), we will get the station that starts sequence which accumulates most of the fuel.

Third step is to verify that goal is reachable with given amount of fuel and given start station, complexity o(n)

  • given that it is an interview question not specifying all the requirements may have been by design i.e. it may test the candidates ability to clarify requirements by asking questions – jk. Mar 12 '12 at 10:46
4

Below is a description of how I think it could work. I can't claim that this is the only solution. I did not thoroughly test this so I leave this to you to verify.

In fact I think that it is too difficult to come up with during an interview.

The illustration attached shows the general idea. The variable x represents the current node being examined. enter image description here

Use this formula if you for the first node.

enter image description here

Use this formula for nodes x=2,...,N

enter image description here

each node has amount of gas g(x) and the distance from node x to next node is given by d(x,x+1)

The R.H.S of the above equation should be the distance between the last two nodes in a route.

You start by generating a permutation of valid routes - Example:

route 1: A, B, C, D, A

route 2: B, C, D, A, B

route 3: C, D, A, B, C

route 4: D, A, B, C, D

The idea is that for each route, at any node x of a given route, you need to calculate whether you can travel to the next node or not. This is determined as follows:

[Step 0] See how much gas you have so far + the max gas you can use from current station if the above amount allows you to travel to the next station, then add this node to your route.

[Step 1] if the above amount is not enough, then the current start point is bad, try another route.

Now, to calculate how much gas you have at a node x, assume that for each unit of gas you consume, you travel 1 unit of distance, do this:

Sum all the gas filled from each gas stop (g1+g2+...+g(x-1)) - Sum all the distances traveled (d1+d2+...+d(x-1)) + Add to the above two sums the gas at this station (g(x))

Example1 - Using the provided data:

route 1, A,B,C,D

Calculating B(1):

g(1)=4

d(1,2)=5

B(1) = false. This means choosing the route A,B,C,D is not good since if you start at A, you will not have enough gas to go to B.

Example 2:

route 2, B,C,D,A

Calculating B(1):

g(1)=48

d(1,2)=45

g(1) <= d(1,2) is false, so B(1)=false that means starting at B is working so far. Continue to examine the situation at the next node (C)

g(2)=50

d(2,3)=44

g(1)-d(1,2) = 48-45

now

50 + (48-45) <= (d(2,3)=44) is false, so B(2) is false, this means that starting at B and getting to C is working so far. Continue the tests to see the status at next node (D)

  • I am not a native English speaker but I feel it would be more clear if you rephrase how to calculate how much gas at a node x: sum(g[1..x])-sum(d[1..x-1]) – Codism Nov 15 '11 at 17:35
  • @Codism: Thank you for your comment, my wording was not clear but I tried to make it better by editing the sentence. – NoChance Nov 16 '11 at 0:08
  • If anyone is interested further in this, a mathematical question for proof by induction is found at: math.stackexchange.com/questions/119091/… – NoChance Mar 12 '12 at 8:45
1

It's a bit late, but I would propose a trial and error method. (I do not consider the interview context and the clarification of requirements question.)

Let's start from station k and drive to the farthest station we can. If we reach N+k = k again (we are in modular arithmetic modulo N, so 0 = N, 1 = N+1, etc.), then we have succeeded.

But assume we can't reach k again, but only l with k <= l < N+k. Bad. We should have started before k. Let's try from k-1. If we can't reach k, then try from k-2, k-3, ...

There are two possibilities :

(1) Unluckily, we fail to reach k from k-1, from k-2, ..., and finally from k-N = k. There is no way we could succeed, we have tried every possible start gas station of the road.

(2) Or we find a k' < k that gives us enough gas to reach k. From k, we reach l, and maybe even a l' > l (if we had enough gas at station k). Maybe we can even reach k' again: we have succeeded (a). If that is not the case, [k', l'] is nevertheless a properly superset of [k, l], because k' < k and l' >= l (b).

If we are not discouraged, then we can apply the same method again and again (keeping the N+k boundary), and we will find a sequence of routes, each of these routes being longer (has more gas stations) than the previous. Until we meet condition (1) (failure) or condition (2) (a) (success).

When we think of coding this simple algorithm, we see that the cost of route from k to l is computed only once. So we just have to compute the cost of the new part of the route (from k' to k and from l to l') at each step. I think this is reasonably fast.

Note : as stated in some other answers, this problem is a simple version of a more complex problem which involves graphs, see https://cs.stackexchange.com/questions/25906/understanding-an-algorithm-for-the-gas-station-problem.

Hope it helps.

EDIT : here's an implementation of the above solution with limited gas tank. It uses only one loop, thus it's just slightly slower when there is not enough gas in the stations, but faster in any other case. I'm sure it is more understandable than the literal explanation.

int FindStartingPointInOneLoop(int[] gasOnStation, int[] gasDrivingCosts, int gasTankSize)
{
  // Assume gasOnStation.length == gasDrivingCosts.length
  int n = gasOnStation.length;
  bool move_forward = true;
  int k = 0;
  int l = 0;
  int gas = 0;
  while (true) {
    if (move_forward) { // try to move forward
      gas = DoLeg(gas, l, gasTankSize);
      if (gas < 0) { // we're out of gas : let's try a new start
        move_forward = false;
      }
      l = (l+1) % n;
    } else { // try to start from a previous gas station
      k = (k-1) % n;
      if (k == 0) { // that was a complete round without any adequate start
        Console.WriteLine("Instance does not have a solution.");
        return -1;
      }
      gas = DoLeg(gas, k, gasTankSize);
        if (gas >= 0) { // we reached our start point, let's try to move forward with the optional extra gas
          move_forward = true;
      }
    }
    if (l == k && gas >= 0) { // we joined "head" and "tail"
      return k;
    }
  }  
}
int DoLeg(int gas, int i, int gasTankSize)
{
  gas += gasOnStation[i];
  if (gas > gasTankSize) gas = gasTankSize;
  gas -= gasDrivingCosts[i];
  return gas;
}

protected by gnat Dec 1 '16 at 21:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.