## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

Subtract the the distance from the petrol to the next one form the bunk capacity
we get a new array. If the sum of the new array is >=0, then only the tour is possible.
If the condition is satisfied, then apply the 'Maximum sub-array problem'. Starting position of the sub-array is a starting position of the tour.

Comment hidden because of low score. Click to expand.
0

That's correct.
Code in wikipedia is very clearly explained.

Comment hidden because of low score. Click to expand.
0

why wouldn't starting at the station with the max petrol capacity work?

what is the truck's fuel tank capacity?

Comment hidden because of low score. Click to expand.
1
of 1 vote

The maximum sub-array problem code is not sufficient. It needs adaptation. You have to threat the array as a circle.
Example:

3 , 4... some negative values ....4 5 ... some negative values 1, 2

The maximum subarray problem would find 4,5 as the maximum continuous subarray, but if you consider that the array is circular, the correct answer is 1, 2, 3, 4.

Comment hidden because of low score. Click to expand.
0

Have this for the for loop to fix that:

``for(i=1;i!= start;i=(i+1)%n)``

Comment hidden because of low score. Click to expand.
0

Visiting entire circle means we return to the original position? or we just have to visit each node once? If we just have to visit each node once, then there is a road we need not to travel.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````Ex: Nodes A,B,C,D
petrol at each station A:3 B:5 C:1 D:10
Distances A-B-> 5,B-C->6,C-D->2,D-A->6

Assume Start ->A and End->B
availabe fuel->3 Distance ->5 cannot reach
Move start to D fuel -> 3+10 distance>5+6 can reach
Move End to C fuel->3+10+5 distance -> 5+6+6 can reach
Move end to D fuel -> 3+10+5+1 distance -> 5+6+6+2
start and end are met``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Starting from any node we can calculate the diff between distance and petrol at each node.
(assuming we can only travel in one direction).
now I will start from a node which will have max positive diff and then work out going through every node. I cannot take nodes as start nodes which have negative diff.

Comment hidden because of low score. Click to expand.
0
of 0 vote

- Find the minimum of gas reserves graph. That is the index, where travel needs to be initiated, and we would never run out of petrol, as we start at the minimum.

#include <iostream>

int dist[] = { 2, 14, 6, 9 };
int refill[] = { 6, 3, 7, 11 };

static const int n = sizeof dist / sizeof *dist;

int main()
{
int cum = 0, min = 0, min_index = 0;
for (int i = 0; i < n; ++i)
{
cum += refill[i] - dist[i];
std::cout << cum << ' ';
if (cum < min)
{
min = cum;
min_index = i;
}
}
std::cout << "\nstart from index " << min_index << " (0-based)\n";
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Initially start with the node which has more fuel than its distance to it adjacent nodes and than apply Minimum Spanning Tree (MST) algorithm to Traverse through all the nodes. The MST will give us the optimal path from one node to it adjacent nodes, and this will apply for all the nodes. As we walk through the Nodes we will keep track of how much fuel we have and what distance have we covered or have to cover. At any point if the distance we have to cover is greater than the fuel we have, we will have to exit and start from the beginning.

The second time we will choose the Node who has the second most fuel but still the fuel should be greater than its distance to the adjacent nodes. And than again apply Minimum Spanning Tree.

In this problem we cannot choose the initial node unless we have Traversed through the complete tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

No need to check for circle after getting maximum sub array sum(when arraysum >0). Since each result has been computed based on prior inforamtion with arraySum >0. So in any case, it will get the starting point index, whose value is maximum in the max sub array.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Start with a node keep on going to next node,store start node in int start.
2.If not able to reach next node, then do step1 with that unreachable node.
repeat step1,2 till you complete a cycle i.e current = start
If there is no answer stop cyclying after first two cycles.(2*n turns)
else if you find current = start then answer is start.

Comment hidden because of low score. Click to expand.
0
of 0 vote

First, let us define the data structure for each node.

class Node{
int capacity;
int rightDistance;
int leftDistance;
Node right;
Node left;
int weightRight;
int weightLeft;
}

Now, weightRight = capacity-distanceRight;
weightLeft=capacity-distanceLeft;

meaning, if I were to start at that point and move right or left how much fuel i would have left when i reached the left node or the right node. This can be done at initialization.

Now, to lets begin for clockwise, wherever we have weightRight as -ve, those node will be discarded for moving right because we do not have enough fuel to move eight for them. Also, we are keeping track of the minimum of weightRight.

Now, whichever node has weightRight as minimum begin from there. and move anti clockwise and keep on adding weightRIght. whereever this sum is 0 or >0 stop there. Lets call this node1 and sum1

Now, go to the original minimum weightRight -ve node. Now, keep on moving forward adding weightRight of each subsequent node, if the sum is <0 at any point before reaching node1 discard node1 and move to left of node1 and add to sum1 till you find another node with sum>0.

Not sure what the complexity is but I think this considerable reduces it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
using namespace std;

int findStartingPoint(int *arrCapacity,int *arrDistance,const int size)  {
int arrSubDistance[size];
for (int index=0;index<size;index++)    {
arrSubDistance[index]=arrCapacity[index]-arrDistance[index];
}
int start=0;
int sum=arrSubDistance[start];
int currPetrolPump=start+1;
int count=1;
while(true) {
if(count==size) {
return start;
}
else if(sum<0)   {
sum-=arrSubDistance[start];
start=(start+1)%size;
if(start==0)
return -1;
count--;
if(currPetrolPump<start)   {
currPetrolPump=start;
}
}
else    {
sum+=arrSubDistance[currPetrolPump];
count++;
}
}
}

int main()  {
int arrCapacity[]={2,2,2};
int arrDistance[]={4,6,3};
int startPos=findStartingPoint(arrCapacity,arrDistance,3);
cout<<startPos;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

# Python program to find circular tour for a track
# A petrol pump has petrol and distance to next petrol pump

class PetrolPump:
def _init_(self, petrol, distance):
self.petrol = petrol
self.distance = distance

# The funtion return starting point if there is a possible
# solution otherwise returns -1

def printTour(arr):
n = len(arr)

# Consider first petrol pump as starting point

start = 0
end = 1
curr_petrol = arr[start].petrol - arr[start].distance

# Run a loop whie all petrol pumps are not visited
# And we have reached first petrol pump again with 0

while(end != start or curr_petrol < 0 ):

# If current amount of petrol pumps are not visited
# And we have reached first petrol pump again with

while(curr_petrol < 0 and start != end):

# Remove starting petrol pump. Change start

curr_petrol -= arr[start].petrol - arr[start].distance
start = (start +1)%n

# If 0 is being considered as start again, then
# there is no possible solution

if start == 0:
return -1

# Add a petrol pump to current tour

curr_petrol += arr[end].petrol - arr[end].distance
end = (end +1) % n
return start

# Driver program to test above function

arr = [PetrolPump(6,4), PetrolPump(3,6), PetrolPump(7,3)]
start = printTour(arr)
print "No solution" if start == -1 else "start =", start

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int Solution::canCompleteCircuit(const vector<int> &gas, const vector<int> &cost) {
int s = gas.size();
int need = 0, index = -1, minima = 0;
for(int i = 0; i < s; i++){
need = need + (gas[i] - cost[i]);
if(minima > need){
minima = need;
index = i;
}
}
if(need < 0)
return -1;
return
(index+1)%s;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.