Microsoft Interview Question
Software Engineer / DevelopersQuestion is unclear.
it says petrol stations going in a circle, and asks where to start to complete the loop.
Why not just start at any station, they are in a circle anyways. maybe some info is missing
Taking mileage as 1 KM/Liter, suppose p(0) is 2 Liters and d(0) is 3 KM, then we can't make it from s(0) to s(1).
An O(n) approach is to start from s(0), go on till available petrol Sum(p(i)-d(i)), becomes negative, then move backwards s(n-1), s(n-2), ... till it becomes +ve again, go on doing like this, till you arrive at same node from both sides... let me know if this is still not clear. Sorry, the question is easy to explain in picture - the way it was put in front of me, think of it in terms of circular list, will be easier to comprehend.
public class Test{
public static boolean isPossible(int[] pet,int[] dis,int start , int end, int excess){
int n = pet.length-1;
if(end<start)end=n+end;
for(int i=start;i<=end;i++){
if(pet[i%n]+excess<dis[i])return false;
excess+=pet[i%n]-dis[i];
}
return true;
}
public static int getStation(int[] pet, int[] dis){
for(int i=0;i<dis.length;i++){
int end=dis.length-1;
if(i!=0)end = i-1;
if(isPossible[pet,dis,i,end,0]){
return i;
}
}
return -1;
}
public static void main(String args[]){
int[] dis= new int[]{3,5,7,1,9,11,23,4};
int[] pet= new int[]{1,5,6,7,53,23,11,0};
System.out.println(getStation(pet,dis));
}
}
ignore the above code:
public class Test{
public static boolean isPossible(int[] pet,int[] dis,int start , int end, int excess){
int n = pet.length;
if(end<start)end=n+end;
for(int i=start;i<=end;i++){
if(pet[i%n]+excess<dis[i%n])return false;
excess+=pet[i%n]-dis[i%n];
}
return true;
}
public static int getStation(int[] pet, int[] dis){
for(int i=0;i<dis.length;i++){
int end=dis.length-1;
if(i!=0)end = i-1;
if(isPossible(pet,dis,i,end,0)){
return i;
}
}
return -1;
}
public static void main(String args[]){
int[] dis= new int[]{3,5,7,1,9,11,23,4};
int[] pet= new int[]{1,5,6,7,53,23,11,0};
System.out.println(getStation(pet,dis));
}
}
~
I believe your code will work in O(n squared) time. A more efficient version will try starting at one station, adding up the difference between the petrol and distance one by one, until either the running sum is negative or the starting node is reached. If the running sum is negative at some point, increment the starting point by 1, removing the difference for the removed node from the running some. Do this until the running sum is positive again, and restart adding nodes. If your beginning node becomes the first node without finding a viable path, return false.
This should work in O(n).
I think we can use greedy method here.
1) calculate p-d at each station.
2) pick the hightest p-d and travel clockwise/anti-clockwise.
3) one of them has to work.
any contradictory proofs for this approach?
hmm how about this example:
1--(1)--2--(1)--3--(1)--4--(2)--5--(2)--6--(2)--7--(2)--1
Number is bracket is the distance between nodes.
And you have P(4) = 7 and P(3)=3, others has 0 petro.
According to your greedy algorithm (correct me if I'm wront), you will choose to start at node 4 since 7/2 is bigger than 3/1?
Start at any petrol station and keep moving by using advancing Pi-Di petrol to next station. If you end up getting stuck in between stations k and k+1, start over from the k+1 station.
It works in O(n)..You think about it, why it works :)
in your example.. there is no solution because for a solution to exist, sigma pi > sigma di.
But, lets p3 =4. then sigma di = sigma pi =11.
travel anti-clockwise u have the solution. but i think i figured the contradictory proof.
pi = {5,5,5,0,10,0,5,5,5}
di = {1,1,1,9,1,9,1,1,1}
We can use backtracking to solve the problem, start at any position and incrementally keep going, if we get a negative value then come backward and choose the next station.
I believe this should be solved by dynamic programming. Let c[i,j] denote the excess fuel when going from i to j. Then the recursion should be c[i,j] = max((c[i,j-1] + p(j)-d(j)),(c[i-1,j] + p(i)-d(i))) for possible i,j
That would be O(N^2).
The O(N) algorithm is simply to keep track of the difference b/w two quantities (also keep the running sum )and as soon as you encounter that the above condition is violated i.e running sum becomes -ve , start over from the next node(i.e after the node at which sum becomes -ve).
Also the question asked prior to this one was:
Give a necessary condition for the trip to exist.
Thanks!!!
First of all, I don't think the s(i) is useful here. All we need is the capacity of each station, and the distance to the next one. Below is an O(n) solution. Start at station 0, with zero fuel. Add current station's capacity to the fuel, then subtract current station's distance from the fuel. If the fuel is negative, we need to keep advancing the starting station till we have non-negative fuel again. Otherwise we just move on to the next station and do the same capacity/distance accounting. We quit when we have either completed a loop or no valid starting station exists.
These accounting can be tricky. Since I haven't tested my code, it might not work but the general idea should work.
static int start(int[] cap, int[] dist) {
int N = cap.length;
int start=0;
int curr=0;
while(start>=N) {
int fuel=0;
while(true) {
fuel+=cap[curr];
fuel-=dist[curr];
if(fuel<0)
break;
curr = (curr+1) % N;
if(curr==start)
return start;
}
while(fuel<0) {
fuel-=cap[start];
fuel+=dist[start];
start++;
if(start>=N)
break;
}
}
return -1;
}
Explaining XYZ idea in more details.
- WellSaid July 02, 2011Known fact
If Summation(d(i) - p(i)) < 0 there is not solution.
Start at any node think of it as origin. Starting going forward and maintain E(d(i) - p(i)) if at any point this is negative. It means the rest of the circle must be positive.
Loop
So if at k we are negative start at k+1 and maintain E(d(i) - p(i)) starting from k+1 as 0.
Two possiblites we cross the origin and there is a negative sum. In this case no solution.
We complete a loop. That means a solution starting at that k+1.