Facebook Interview Question SDE1s
Country: United States
As you can only go from one station to the next you can't perform any kind of searching. The algorithm just needs to check that starting from one station you can always reach the next one with the accumulated gas.
def compute_gas(gas, cost):
solutions = []
for x in xrange(len(gas)):
current_gas = gas[x]
y = (x + 1) % len(gas)
while x != y:
if current_gas < cost[y - 1]:
break
current_gas = current_gas - cost[y - 1] + gas[y]
y = (y+1) % len(gas)
if x == y and current_gas > cost[y - 1]:
solutions.append(x)
return solutions
@Yevgen I don't know why I can't reply below the source code.... Anyway the j index is not correctly updated. What happens when you are at N - 1?? j has to be 0 not N otherwise the code will rise an exception. I haven't checked the rest of code there might be more errors.
The following code is in O(n). The baseline in O(n^2) is straight forward!
#include <vector>
vector<int> canCompleteCircuit(int gas[], int cost[], int n) {
vector<int> ret;
// do the initial forward
int current = 0, budget = gas[0],i,flag=-1;
for (i = 0; i < n && budget - cost[i] >= 0; i++)
{
budget += (gas[i+1]-cost[i]);
}
if (i == n) // the first station is valid
{
ret.push_back(0);
budget = 0;
}
else
{
flag = i;
}
current = n - 1;
// find the first valid gas station
while (current != 0 && ret.size()==0)
{
budget += gas[current] - cost[current];
while (budget>=cost[flag] && flag!=current)
{
budget += gas[flag + 1] - cost[flag];
flag = (flag + 1) % n;
}
if (flag == current) ret.push_back(current);
current--;
}
budget = 0;
// find the rest valid gas stations
while (current > 0 && ret.size() > 0) // it has found a path
{
while (current > 0 && gas[current] - cost[current] + budget < 0) current--;
if (current > 0)
{
ret.push_back(current);
budget = 0;
}
current--;
}
return ret;
}
Another way to solve this in O(n) is to propagate all the deficits and eliminate non-viable stops in two linear passes.
def gas_run(gas, cost):
deficits = list(gas)
for idx, c in enumerate(cost):
deficits[idx] -= c
def eliminate(carry=0):
# carry is the carried deficit to start with
for i in reversed(xrange(len(deficits))):
s = deficits[i]
if s is None:
# this stop is already eliminated
continue
s += carry
if s >= 0:
# this stop is viable
deficits[i] = s
carry = 0
else:
# this stop is not viable
deficits[i] = None
carry = s
return carry
eliminate(eliminate())
return [idx for idx, s in enumerate(deficits) if s >= 0]
print gas_run(
[1, 1, 7, 1, 4, 1, 1],
[2, 2, 2, 2, 1, 0, 3]
)
my approach for a linear time (O(n)) solution
- Chris May 23, 2017/* 1. brute force would be O(N^2) time and O(1) space (space for the result not calculated) 2. there is a better approach in O(N) time and O(N) space, comes from the following observation: I start at an arbitrary point (e.g. index 0) with 0 gas: i=0, totGas[0] = 0 to reach i+1 I get gas at i and use gas to go to i+1: totGas[i+1] = totGas[i] + gas[i] - cost[i]: note: I started at i with totGas[i] initial fuel repeat this for i up to n-1, so, totGas is an array of n+1 length if starting at i=0, if there is any value below totGas[0] on the right side of the totGas-array, it means, at some point I will run out of gas. This is, I can find out if I can reach station n-1 by looking at the minimum value of totGas in [i+1..n]. But what happens with the stations [0..i] if i > 0? pretty much the same, but i need to remove the start fuel from totGas[i] and add totGas[n] to the min-Value in this range, since initial calculation was done starting from 0 and because we had potentially some fuel left when starting over at i=0... I can do this by finding the min-values from the left and right and pick the appropriate. If I do so, I need to offset the right-hand value by totGas[i] as well since they were calculated forward assuming it had totGas[i] gas in the tank initially. complete in Java8, cleanup the indexes a bit */ public class GasStations { static public List<Integer> canCompleteCircuit(int[] gas, int[] cost) { assert(gas != null && cost != null && gas.length == cost.length); int n = gas.length; List<Integer> result = new ArrayList<>(); // totGas[i] is the amount of gas in tank at i when started with 0 at 0 // at totGas[n] is to get back to 0 int[] totGas = new int[n+1]; // minGas[i] is the minimum gas in tank at range [0..i-1] [i+1..n-1] int[] minGas = new int[n+1]; for(int i = 0; i < n; i++) { totGas[i+1] = totGas[i] + gas[i] - cost[i]; } // get the minimum fuel found going towards the n-th station for(int i = n-1, minG = Integer.MAX_VALUE; i >= 0; i--) { minG = Math.min(minG, totGas[i+1]); minGas[i] = minG - totGas[i]; } // get the minimum fuel found coming from the 0-th station for(int i = 1, minG = totGas[0] + totGas[n]; i < n; i++) { minG = Math.min(minG, totGas[i] + totGas[n]); minGas[i] = Math.min(minG - totGas[i], minGas[i]); } // see from which index i can start without running out of gas for(int i = 0; i < n; i++) { if(minGas[i] >= 0) result.add(i); } return result; } public static void main(String[] args) { System.out.println(canCompleteCircuit(new int[]{10,2,3,5}, new int[]{5,6,2,6})); System.out.println(canCompleteCircuit(new int[]{4,2,7,5}, new int[]{5,2,8,3})); } }