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
|