Amazon Interview Question for SDE1s


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.

- dadakhalandhar May 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

what is the truck's fuel tank capacity?

- Anonymous May 06, 2013 | Flag
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.

- fmm May 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Have this for the for loop to fix that:

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

- bunnybare May 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous May 09, 2013 | Flag
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

- Kirankumar D G May 05, 2013 | Flag Reply
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.

- DashDash May 05, 2013 | Flag Reply
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";
}

- krec.kiran May 05, 2013 | Flag Reply
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.

- azhar.rao May 06, 2013 | Flag Reply
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.

- sk May 11, 2013 | Flag Reply
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.

- Ravi May 16, 2013 | Flag Reply
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.

- Anarkey June 07, 2013 | Flag Reply
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;
}

- Sibendu Dey July 02, 2013 | Flag Reply
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

- Gautam K March 30, 2017 | Flag Reply
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;
}

- puneet3821 September 28, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More