Interview Questions

You are given n petrol stations s(0), s(1), s(2).......

Microsoft Interview Questions and Answers


(Continued from previous question...)

131. You are given n petrol stations s(0), s(1), s(2).......

Question:
You are given n petrol stations s(0), s(1), s(2), ..., s(n-1) which have petrol available p(0), p(1), p(2), ..., p(n-1). Going in a circle, with distance to next station being d(0), d(1), d(2), ..., d(n-1), how will you find where to start, such that you can complete the loop. You can assume mileage to be 1.


maybe an answer:


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.

(Continued on next question...)

Other Interview Questions