Facebook Interview Question
SDE1sCountry: 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