Amazon Interview Question
Software Engineer / DevelopersCountry: India
my algorithm is similar to most of the algorithms explained above but, it uses O(1) of extra space;
basic idea is that if we start at any point then in order to reach back at that point is possible
if and only if the minimum cumulative sum of the differences of dist[i]-petrol[i] from the starting point to the last point in the circle should be non-negative, and this can be managed in O(1) space very easily.....:)
@msramachandran
We can compute the sum of distance in linear time:
first we concatenate the distance vector with itself to get a int dist[2n]
to compute the sum of n consecutive numbers, do the following:
for the first n numbers, just add them one by one, then we get sum[n],
then for sum[n+i] compute it this way:
sum[n+i]=sum[n]-dist[i],
then we get all sums, just pick the first sum that is >0.
I think the O(n) space is not necessary, the following code should work:
public static void main(String[] args) {
int[] petrol = {3,5,6};
int[] dist= {2,7,3};
int sum = 0;
int startPoint = -1;
for (int i=0;i< petrol.length;i++){
sum +=(petrol[i]-dist[i]);
if (sum < 0){
startPoint = -1;
}else if (startPoint == -1){
startPoint = i;
}
}
if (startPoint == -1){
System.out.println("Can not find");
}else{
System.out.println("found start point:" + startPoint);
}
}
Suppose i have petrol array = 2 7 9 3 and dist array = 1 6 12 3
Then according to your code it should give ans as 3 but if we proceed from 3 it would be impossible to reach 3 back again as after travelling 3: sum=0; then it should move back to
petrol station 0 so sum=1 then sum=2 then sum=-1
let petrol[i] and dist[i] be the two respective arrays.
make a new array arr[i] = petrol[i] - dist[i];
find the maximal sub-sequence in this arr. the beginning of this maximal sub sequence would be the starting point of the travel.
You will have to complete the total circle. That means if you start from 2nd point you will have to reach 2nd point. Also one catch:
Suppose you are able to go from point 1 to point 3. That doesnt necessarily mean you will be able to go from 2 to 3.
So I don't think your algorithm will work. May be I didnt understand properly. Can you please explain your solution?
@erarpitagarwal: is correct answer.
@Annonymous: question says that it will stop at every point. You can't go from 1-3 directly. 1-2-3 is correct order.
No. the solution is incorrect. Take an example. If the difference array is this,
5 5 -6 -6 2
you would start from position 1, but u cannot travel. you have to start from 2. This happens because it is a circular array.
The answer is :
do sequential summation of elements in the difference array. find the point where the summation would be at lowest. Start from the next position to that.
@msramachandran
I thought of the same thing but here's a counter example.
-12 10 10
You'll need to start from the first 10 but the sequential sum of the difference array would be,
-12 -2 8 and it would suggest starting from the second 10.
Here the amount of petrol is enough to travel the distance ... litres of petrol = distance in kilometres ... so i don't think 5 5 -6 -62 is a possible scenario ... but I am still not sure if the start of the maximum subsequence will still give the answer ... Please le me know if I am missing something
How about this?
suppose i is the first point, and that the truck can travel to point j but can't travel to j+1. so the truck can not travel to j+1 if it starts any point between i and j.
sorry, i forgot the code. here it is.
int findfp(int petrol[], int dist[], int num) {
int beg, cur count;
beg = 0;
cur = 0;
count = 0;
int remaining = petrol[cur];
while (cur < 2 * num) {
if (remaining >= dist[cur % num]) {
remaining -= dist[cur%num];
count ++;
remaining +=petrol[cur % num];
cur ++;
} else {
if ( cur >= num)
return -1;
count = 0;
beg = cur;
remaining = petrol[cur];
}
if (count == num)
return beg;
}
return -1;
}
Assume diff[i] = petrol[i] - dist[i]
Concatenate diff array so that we have diff[i + N] = diff[i]
Then use the following modification max sum sub-sequence algorithm
int maxsofar = 0, count = 0;
for (i = 0 ; i < 2N ; i++) {
maxsofar += diff[i];
if (maxsofar < 0) {
/** petrol is less than the distance **/
maxsofar = 0;
count = 0;
} else {
/** petrol is more than distance - increment petrol pump **/
count++;
if (count == N) {
/** we have visited N pumps - success **/
printf("The first petrol pump to start is %d", i - N + 1);
break;
}
}
}
O(N) extra space for diff array and O(N) runtime.
how to approach such problem : ?
observations needed
a car can only start and reach at the same point back only and only if it has non negative petrol all the time.
it has infinite capacity so it will take all the petrol that is available to it .
mileage is 1km/ltr which just simplifies the calculation . the amount of petrol in car is equal to the distance it can travel.
line of thought : let car start from any petrol pump and reach the next petrol pump and fill its tank . at this point the car will contain residual petrol from the previous petrol pump and full petrol of current petrol pump. this will keep on happening till it reaches the same petrol pump again or petrol in tank becomes negative.
now let petrol pum capacity = [1, 1, 2, 3 , 1]
and distance between pumps =[2, 1, 1, 1, 3 ]
let there be another array diff=[-1, 0, 1, 2, -2] the difference between 1st and 2nd array { it was allowed to use O(n) space so it was hint that helper array can be used }
if car starts from i-th petrol pump and is currently at j-th petrol pump .. petrol in its tank will be the sum of elements of diff array from i to j . so car will be able to reach its origin point only when the sum of elements from its start point i and end point j ( the last petrol pump) is at least zero.
in this example truck can start from both B and C of petrol pump { A,B,C,D,E
python code based on above
fuel = map(lambda x:int(x), raw_input().split())
distance = map(lambda x:int(x), raw_input().split())
# takes the standard input as space separated integers in two lines.
diff = [b-a for b,a in zip(fuel, distance)] # creates the diff array
diff = diff + diff # to account for cyclic array
start = 0 # let say we start from 0 the position
end = 0
summation = 0
counter = 0 # keeps the count of petrol pumps accessed
for i in range(len(diff)):
if(end - start >= len(distance)):
break;
summation += diff[i]
end += 1
if(summation < 0):
summation = 0
start +=1
end = start
if(end - start == len(distance)): # we covered exactly 5 petrol pumps
print start
else:
print "solution doesn't exist"
Simple and elegant solution to this problem is:
///Stations are starting from index 0 to n-1.
#include<iostream>
using namespace std;
struct petrolPump
{
int petrol;
int nxtDistance;
};
int main()
{
int n;
cout<<"\n Enter the total number of pumps: ";
cin>>n;
struct petrolPump p[n];
for(int i=0;i<n;i++)
{
cout<<"\n Enter the petrol Capacity : ";
cin>>p[i].petrol;
cout<<"\n Enter the next distance :";
cin>>p[i].nxtDistance;
}
// Elimination of starting point
int start =0;
int i=0;
while(p[i].petrol<p[i].nxtDistance)
{
i++;
start++;
}
int loopIndicator = start;
int end= start;
int leftPetrol=0;
while(1)
{
leftPetrol = leftPetrol-p[start].nxtDistance+p[start].petrol;
if(leftPetrol<0)
{
loopIndicator++;
//cout<<loopIndicator<<" ";
start = loopIndicator;
cout<<"\n Not possible with this start station. So changing the start station to "<<start<<endl;
leftPetrol = 0;
continue;
}
start= (++start)%n;
cout<<"\n Vechile is now at station "<<start<<" with leftOver petrol : "<<leftPetrol<<endl;
if(start==loopIndicator)
break;
}
if(start==loopIndicator)
{
cout<<"\nStart Station is "<<start<<endl;
}
return 0;
}
I am pretty sure that following soln will work. The concept is simple, if at any point we find that the current petrol used is less than the distance traveled then just start again from the very next point considering it as the first point.
}
- ishantagarwal1986 October 30, 2011