Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Will you plz explain a little more ? Suppose I have found the max sum, but what will be the approach after that ? Thanks in advance.
Kadane's algorithm
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
Approach:
Let D be the distance array.
Let P be the petrol array.
int [] D = {4, 7, 4, 8, 4, 1};
int [] P = {3, 5, 3, 8, 3, 6};
Now start with i=0;
D[0] = 4 > P[0] = 3; i=0 can not be starting point so we move to i=1;
D[1] = 7 > P[1] = 5; i=1 can not be starting point So we move to i=2;
D[2] = 4 > P[2] = 3; i=2 can not be starting pointso we move to i=3;
D[3] = 8 <= P[3] = 8; i=3 can be starting point, now keep on summing the D[i] and P[i] and P[i] >= D[i]
D[4] = 4 > P[4] = 3; here the P[i] is not greater or equal to D[i] so we break; and start from next i=5;
D[5]=1 < P[5] = 6; and carry over petrol is 5
now,
D[0] = 4 < P[0] + carry = 3 + 5;
D[1] = 7 < P[1] + carry = 5 + 4;
D[2] = 4 < P[2] + carry = 3 + 2;
D[3] = 8 < P[3] + carry = 8 + 1;
D[4] = 4 <= P[4] + carry = 3 + 1; // now next i = 5 is the same as the starting point ie index 5.
So the starting point is index=5;
Total time complexity: O(n)
using this sort of circular queue will make the worst case comparisons as 2*n, ie. when the last value is the only solution, this is still in the order of O(n)
Hi
I have the same solution as people are suggesting above. But as I had maximum sum sub sequence problem in my homework I would like to write down the logic. So the first point to note is that you can go only from P(i) to P(i+1). So i think taking a circular queue or a list would be wrong. Now you have two arrays, create a third array say arr
where arr[i]=P[i]-D[i];
And now follow this
For every element, find the OPT(i)=max{arr(i),arr(i)+OPT(i-1)}
And base case is OPT(i<0)=0 .
We fill the array from left to right, and the max value in the array would mark the beginning of the journey and where the OPT goes 0, that would mark the end. So the run time is 2n.
What does it mean? We are supposed to sort the stations list or we have to keep the original sorting and only find a starting point?
In the latter case we'd assume that this list is a cirtular one (a ring), that is the last element's X is the distance from the first station.
Can we know that how much distance will the vehicle cover in for a given amount of gas? If this becomes known, maybe we can think of trying something like a knapsack kind of optimization strategy here.
But again as you said that sorting is not required, a knapsack problem's solution doesn't stand a chance here.
There are few other unknowns that can be discussed.
1) Does the vehicle's fuel tank has enough capacity that if it is full, then it can run between any two stations?
2) If after filling the fuel in the tank, can the excess fuel be carried along? Or the vehicle's fuel tank capacity becomes an upper limit of fuel?
My solution (1 unit petrol = 1 unit distance). O(n)
public int find(int[] petrols,int[] distances) {
int[] diff = new int[2*petrols.length];
for(int i=0;i<petrols.length;i++) {
diff[petrols.length+i] = diff[i] = petrols[i] - distances[i];
}
boolean[] notOrigin = new boolean[diff.length];
for(int i=0;i<petrols.length;i++) {
if(notOrigin[i]) continue;
int sum = 0;
for(int j=i;j<i+petrols.length;j++){
sum+=diff[j];
if(sum<0) {
for(int k=i;k<=j;k++) notOrigin[k] = true;
break;
}
}
}
for(int i=0;i<petrols.length;i++)
if(!notOrigin[i]) return i;
return -1;
}
i think instead of using continue, we can to do following way for better performance
static int find(int []p,int []d)
{ int diff[]=new int[2*p.length];
for(int i=0;i<p.length;i++ )
{ diff[i]=diff[p.length+i]=p[i]-d[i];
}
for (int j = 0; j < p.length; j++)
{
int sum= 0;
int k ;
for ( k = j; k < j+p.length; k++)
{
sum =sum+diff[k];
if(sum<0){
j=k;
break;
}
}
if(k==j+p.length){return j;}
}
return -1;
}
tell me if it is wrong
Enhanced version.
public int find(int[] petrols,int[] distances) {
int[] diff = new int[2*petrols.length];
for(int i=0;i<petrols.length;i++) {
diff[petrols.length+i] = diff[i] = petrols[i] - distances[i];
}
for(int i=0;i<petrols.length;i++) {
boolean notOrigin = false;
int sum = 0;
for(int j=i;j<i+petrols.length;j++){
sum+=diff[j];
if(sum<0) {
notOrigin = true;
i=j;
break;
}
}
if(!notOrigin) return i;
}
return -1;
}
O(n) solution:
// first - distance, second - petrol
typedef std::pair<int, int> Station;
typedef vector<Station> PetrolStations;
int GetStartStationIdx(PetrolStations stations)
{
int result = stations.size() - 1;
int petrol = 0;
for(int idx = stations.size() - 2;idx>=0;--idx)
{
if ( petrol>0 )
petrol = 0;
const Station& station = stations[idx];
petrol += (station.second - station.first);
if ( petrol>=0 )
result = idx;
}
petrol = 0;
for(int i = 0;i<stations.size();++i)
{
PetrolStations::size_type idx = (result + i)%stations.size();
const Station& station = stations[idx];
petrol += (station.second - station.first);
if ( petrol<0 )
{
result = -1;
break;
}
}
return result;
}
Not working for
stations.push_back(Station(20, 2));
stations.push_back(Station(3, 2));
stations.push_back(Station(3, 6));
stations.push_back(Station(3, 2));
stations.push_back(Station(3, 1));
stations.push_back(Station(4, 4));
and for
stations.push_back(Station(1,0));
stations.push_back(Station(1,1));
stations.push_back(Station(1,0));
stations.push_back(Station(9,13));
I assume you have to touch every station, so starting from P(N-1) requires to move circurarly to P(0) where N is the number of stations. In that case first case is -1 and second is 3.
My O(n) solution. I think this works, though the proof is a little tricky.
Instead of worrying about distance and petrol, let's combine them into a single value "surplus", where surplus[i]=petrol[i]-distance[i]. This tells us how much extra (or less) petrol we have left over after moving to the next station.
Say we start from Station [headpt]. If sum(surplus[headpt]...surplus[tailpt])<0 for some Station [tailpt], then Station [headpt] cannot be the first station in the path (since we ran out of petrol before we got to the end). In which case, we take Station[headpt+1] to be our new starting point.
But here's the sneaky part: we don't actually need to sum all the way from the start of the path again! We can remove the surplus of Station[headpt] and continue from where [tailpt] left off. If the sum is still<0, we continue to discard the first station in the path until our sum is >=0.
Why does this work?
If we were to graph the cumulative surplus after each station we visited, the final station (where the total becomes negative) is the lowest point. Removing stations from the front of the path has the effect of shifting the remainder of the graph up or down. No matter what, the last point is always the lowest. Therefore if we delete stations from the front until the cumulative sum is >=0, we can guarantee that all subpaths starting from that station up to [tailpt] have positive sums.
If [tailpt] manages to reach [headpt-1], then we have found a positive path.
Since [headpt] circles through the list of stations at most once, and [tailpt] at most twice, this is O(n).
The code...
//return index of starting station.
public static int findPath(int[] petrol, int[]distance){
//assume petrol[i]=petrol @ Station [i]
//assume distance=distance from Station [i] to [i+1]%N
int N=petrol.length;
int[] surplus=new int[N];//how much surplus petrol we obtain traveling [i]->[i+1].
for (int i=0;i<N;i++){
surplus[i]=petrol[i]-distance[i];
}
int cumsum=0;//sum of surpluses
int headpt=0;
int tailpt=0;
while(headpt!=N){
cumsum+=surplus[tailpt];
while(cumsum<0){
//delete petrol station at headpt from path. Must stop when headpt==tailpt.
cumsum-=surplus[headpt];
headpt++;
}
tailpt++;
tailpt%=N;
if(tailpt==(headpt-1+N)%N)//have reached last station.
return headpt;
}
return -1; //couldn't find anything
}
For each station consider the difference between petrol and distance. Let's assign to each station the letter P if this difference is positive or N otherwise. Starting from station i-nt find the cumulative sum cs for each station to the j-th untill cs<0. At this point you can say that i-th is not the start. But (trick) you can exclude all stations in range [i,j]. In fact, if you have (for instance) the sequence P,N,P,P,N,P,N and only after last N you have cs<0, you can conclude it will be negative also if you start from every P in the sequence (because sum is still positive after every N but the last). Now you can scan just once the sequence and find (if any) the starting point. Check my algo above.
It might be solved using the maxsum subarray algorithm, the element of the values are (petrol amount - distance). So, the start station must be the start element of the max sum subarray.
boolean checkedOnce=false;
int coveredPlaces=0;
int pos=0;
int carry=0;
int n=5;
int[] D={6,6,4,2,6};
int[] P={7,5,3,1,8}
while(covered!=(n-1))
{
if(pos==0 && covered==0 && checkedOnce)
{ break;}
else
{checkedOnce=true;)
if(D[pos]<=(P[pos]+carry))
{
covererd++;
if(pos==(n-1))
{
pos=0;
}
carry=(P[pos]+carry-D[pos]);
}
else
{
covered=0;
carry=0;
}
}
if(covered==(n-1)){
if(pos==(n-1)){
out(0);
}
else
{
out(pos+1);
}
}
#include <vector>
#include <iostream>
/*
Given a list of n gas station of form P(D,X) where D is the distance from this station to next station and X
is the amount of petrol available at this station, identify the starting station from where you can complete
journey to each station in order from 1.....N. You can only go in one direction i.e from P(i) to P(i+1)
*/
int main(int argc, char **argv)
{
/*
std::vector<std::pair<int, int>> P = {
{ 4, 3 },
{ 7, 5 },
{ 1, 6 },
{ 4, 3 },
{ 8, 8 },
{ 4, 3 },
};
*/
/*
std::vector<std::pair<int, int>> P = {
{ 20, 2 },
{ 3, 2 },
{ 3, 6 },
{ 3, 2 },
{ 3, 1 },
{ 4, 4 },
};
*/
std::vector<std::pair<int, int>> P = {
{ 1, 0 },
{ 1, 1 },
{ 1, 0 },
{ 9, 13 },
};
size_t count = P.size();
std::pair<int, int> candidate(-1, -1);
for (auto i = 0; i < (P.size() * 2) - 1; ++i) {
if (i < P.size()) {
if (P[i].first <= P[i].second && candidate.second < 0) {
candidate = std::pair<int, int>(i, 0);
count = P.size();
}
}
if (candidate.second >= 0) {
candidate.second += (P[i % P.size()].second - P[i % P.size()].first);
--count;
}
if (!count) {
std::cout << candidate.first <<std::endl;
break;
}
}
return 0;
}
A valid starting point would satisfy the following 2 properties:
Assuming P(D,X) = {(d1, x1), (d2, x2),...(dr, xr),...(dn, xn)};
Let valid starting station is, P(dr, xr), then:
1. dr < xr
2. for all i, r < i < n:
Σdi < Σxi
Solution would be O(n).
I think simple kadane's algorithm is enough to solve this pbm :)
- NoMind January 27, 2013Find the distance between petrol and distance (p-d) and create one array. After that apply kadane's algorithm for maximum sum :)