Amazon Interview Question for Software Engineer in Tests


Country: India
Interview Type: Phone Interview




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

We need to find _all_ possible starting points, which makes this an interesting problem.

An O(n) time algorithm is possible.

Assume we are going clockwise starting with an empty tank, and the petrol stations are numbered 1 to n.

Let p_i be the amount that will be in the car when an (empty) car fills up at station i and goes to station i+1 (i.e. distance between i and i+1 - petrol available at station i). Note: We allow p_i to be negative.

Let S_i = p_1 + p_2 + ... + p_i

If S_n < 0, there are no starting points, as we don't have enough petrol to complete the circle. So, assume S_n >= 0.

Now station k+1 is a valid starting point if the following holds true:

1) For every n >= j >= k+1 we have that S_j - S_k >= 0

2) For every 1 <= j <= k, we have that S_j - (S_k - Sn) >= 0

In O(n) time, we can find all k with property 1, by traversing the S[1,..n] array right to left and keeping track of the minimum seen so far, and checking if the minimum seen so far is >= current element.

A similar algorithm will work for finding all k with property 2.

Take the intersection of the k we found for 1 and the k we found for 2.

This is some python to demonstrate

def starting_points (p, d):
	n = len(p)
	S, count = [0]*n, 0
	s = 0
	while count < n:
		s += p[count] - d[count]
		S[count] = s;
		count += 1	
    	
	# No possible starting points.
	if S[n-1] < 0:
		return
    
	# find k with property 1
	prop1 = [False] * n
	k, min_so_far = n-1, S[n-1]
	while k >= 0:
		if S[k] <= min_so_far:
			prop1[k] = True
		min_so_far = min(S[k], min_so_far)
		k = k-1
    
	# find k with property 2
	prop2 = [False] * n
	k, min_so_far = 0, S[0]
	while k < n:
		if (S[k]-S[n-1]) <= min_so_far:
			prop2[k] = True
		min_so_far = min(S[k], min_so_far)
		k = k+1
    	
	# starting points
	k = 0
	while k < n:
		if prop1[k] and prop2[k]:
			yield (k+1)% n
		k += 1
    
def main():
	prices = [3,4,5]
	distances = [7,1,1]	
	for start in starting_points(prices, distances):
		print start
  
if __name__ == "__main__":
	main()

- Loler March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler, interesting.

Here's my take on doing it in linear time. I have chasing pointers, the starting city and the ending city. Let's say I have ten cities, and I start at city 0 and get to city 4 with enough gas, but then going from 4 to 5 leaves me on the side of the road. At this point I know all of the following:

1) City 0 is no longer a candidate.
2) If the trip from city 0 to city 1 is gas-positive (including the fillup at city 0), then I immediately rule out city 1 as well.
3) If the trip from city 0 to city 1 is gas-negative, then I know that the trip from city 1 to city 4 is gas-positive, and it's a constant-time adjustment to figure out how much gas I would have after the 1->4 trip, since I can subtract the 0->1 amount from the 0->4 amount.

During each constant-time iteration, I basically do the following:

1) Extend my trip by advancing the ending city.
2) Declare victory (if I've gotten all the way back around) and then advance the starting city.
3) Advance the starting city and immediately rule it out.
4) Advance the starting city and immediately compute its gas surplus for the ending city.

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

@Anonymous: Isn't this still potentially Omega(n^2)?

- Loler March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler, I think it's linear, because each iteration is done in constant time and advances one of the pointers (either starting city or ending city). Do you have a worst case scenario in mind?

- showell30@yahoo.com March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@showell: Perhaps I am missing something.

I agree this seems to work for a single point, but how does this algorithm enumerate all the starting points?

Once you have gotten a possible starting point (declare victory) how will it find the next one? How do you eliminate the next starting point in O(1) time?

Seems like a positive surplus does not allow you to either eliminate or declare victory for the next starting city.

Say the differences were 100, 50, 100, -150,

From the first city, you do 100 + 50 + 100 - 150 and are back to starting point with 100 in the tank.

Note that you can start at the second station and finish the trip for this set of differences.

But if the differences were 100, 49, 100, -150,1

The trip for the starting point still finishes with 100 in the tank, but you cannot finish the trip starting at the second station (1 liter short).

I don't see the algorithm distinguishing between 49 and 50 case.

- Loler March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler, you are right. After digging deeper, I am now confident that I can get to the first solution in linear time (which is better than a naive approach), but like you say, if I'm "lucky" enough to get all the way around, then I'm pretty much back to where I started for finding the 2nd solution.

- showell30@yahoo.com March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just realized it is kind of like an adversary argument. Even though the first circle went through fine, since you don't look at the exact intermediate spots, someone can shuffle those stations around to mess with your algorithm.

- Loler March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler, yep. I like your algorithm, by the way. I just wonder if there is another way to tackle this, like maybe something that starts with the most adverse leg of the trip and then somehow divides and conquers on either side of that station.

- showell30@yahoo.com March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Glad you liked it. It does seem a little complicated and perhaps you are right, there might be something simpler. One simplification we can do is to pick the locations of the minimums (in S_k). Those and (some of) the last segment (to the right of the last minimum) will contain the possible starting points.

- Loler March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can I make more money?

- Amit Gupta March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

At each node i store the difference between petrol at i-1 node and distance between i-1 and i.
This would give the excess/deficit petrol at node i for further journey.
Now in this circle start from any node and proceed in one direction. Add the nodes on the way till the sum is positive. If it becomes negative move the start node backwards updating the sum.
Proceed as such.
Break out the loop once the end node reaches start node. If the result is positive the start node and end node is solution. If the result is negative no solution is possible.

- Expressions March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Expressions, tell me if my logic is flawed here. Let's say that I start at city 0 and can get to city 8 without running out of gas, but then the trip from 8 to 9 puts me at a deficit. At this point I can rule out all the cities between 0 and 8 as starting points. Let's take city 4 as an example. We know that the trip from 0 to 4 is net positive, yet the trip from 0 to 9 is net negative, so the trip from 4 to 9 must also be net negative. Instead of moving the start node backward, does it make sense to move it one past the last ending city?

- showell30@yahoo.com March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Don't you have to enumerate all possible nodes?

How does this work?

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

Since this only gives one station, and does not look like a viable algorithm to enumerate all the possible starting points (see comments to my answer). I am going to downvote this. Sorry.

- Loler March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@loler: this may work with some modification

a b c d e ->stations
5 4 3 2 1 -> distance between stations
4 5 2 5 0 -> petrol at each station
-1 1 -1 3 -1 -> difference (petrol at each station - distance between stations)

start from positive nodes i.e from the above we can start from 'b' and 'd' station.
if we start from 'b' station -> 1 + (-1) + 3 + (-1) + (-1) = 1
if we start from 'a' station -> 3 + (-1) + (-1) + 1 + (-1) = 1
so 'a' and 'b' can be starting points.

- try March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@try, you mean 'd' instead of 'a'. I love your illustration.

- iloveseahawks March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@try: Not all positive nodes give a starting point. See the comments to my answer.

- Loler March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@loler: Yes it is 'd' as you mentioned.

Loler: Not all positive nodes give a starting point
try: but in the example mentioned above it is giving.However you are right that all positive differences will not give the starting point.
Let's modify the strategy as below(taking your example)
differences are: 100, 49, 100, -150, 1
start from positive difference which is 100, 49, 100 and 1.
100: 100+49=149; 149+100=249; 249-150= 199; 199+1=200(nowhere the sum is negative as you can see)
49: 49+100=149; 149-150=-1; break here as sum is negative so this can be the starting point.
Do this process for every positive number but here comes the catch: is this not brute force?I think it is but then I don't understand loler solution as well as his use of i, j, k is confuses me more.I wish he does this for real numbers and show how it works?

- try March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modification in wordings in above post.
49: 49+100=149; 149-150=-1; break here as sum is negative so this can't be the starting point.

- try March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@try: Here is an explanation using your sample. [-1 1 -1 3 -1]

We compute the S_i

[-1 0 -1 2 1]

The two properties which I mention in the answer are basically to say that k+1 is a starting point.

Property 1 says that we can get to any station after the starting station (but before the n^th station).

Property 1 is computed, starting from right

[1 2 -1 0 -1]

1 is min seen so far (in [])? True.
2 is min seen so far (in [1,2])? False.
-1 is min seen so far (in [1 2 -1])? True
0 ? False
-1 ? True.

So we get

[True, False, True, False, True] (note we need to reverse this)

Property 2 states that we can get to any station before the starting station.

[-1 0 -1 2 1], S_n = 1

For -1, is S_k - S_n = -1 - 1 <= -1? True
For 0, is S_k - S_n = 0 - 1 <= -1? True.
For -1, is S_k - S_n = -1 -1 <= -1? True.
For 2, 2 - 1 <= -1? False.
For 1 False.

So we get

[True, True, True, False, False]

Take the intersection, and we get the result.

- Loler March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. First question that come to my mind is, are we supposed to move clockwise or anti clockwise as answer may vary.
2. Assuming clockwise
a. Station "i", definitely cannot be a starting point, if d [ i => i+1] > fuel[i]. i.e if even after filling the maximum allowed capacity at station "i", we cannot reach the next station, then station "i" cannot be a starting point.
b. For each of the stations found in 2.a, check if i-1, i-2, ... can be a starting point. We can say station "i-x" cannot be a starting point if ( fuel[i-x] + fuel[i-(x+1)] + .. + fuel[i] ) < (d [ (i-x) => (i-x+1)] + d [ (i-x+1) => (i-x+2) ] + ... + d[(i-1) => (i) ] + d [ (i) => (i+1) ]. i.e even after filling maximum allowed capacity at all the previous "x" stations, we are not able to get over the deficit distance needed to go the next city, then none of the previous "x" stations can be a starting point
c. After 2.a, final answer will be total stations - number of stations excluded in previous steps.

- prakash1529 March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int c=0;
while(c<n){
	petr=a[c];
	ptr = c+1;
	int countstations = 0;
	while(countstations<n)
	{
		petr -= a[ptr];
		if(petr<0){
			c++;
			break;
		}
		ptr++;
		countstations++;
		if(ptr==n)ptr=0;
	}
	if(countstations==n){
		ret.add(c);c++;
	}
}

- Ram March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:
petr -= dist[ptr];
if(petr <0){
c++;break;
}
petr += a[ptr]

- Anonymous March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

its codechef question ....

- goelrinku90 March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you have a link you can provide?

- Loler March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package amazon.interview;

import java.util.ArrayList;
import java.util.List;

import utils.ArrayUtil;

public class PetrolStationCity {

	public static void main(String[] args) {
		//data is in 2d array. 
		//The first int represents amount of petrol
		//The second int represents distance
		//so {1,2} means have 1 petrol and distance to next station is 2
		int[][] data = new int[][]{{1,2},{2,1},{7,5},{2,4},{5,6},{7,4},{2,5},{6,3},{4,3},{2,2},{4,2},{1,4}};
		int[] diff = getDifferences(data);
		ArrayUtil.printArray(diff);
		//result is [1, 5, 7]
		//means station 1, 5 and 7
		System.out.println(getStartStations(diff));
	}
	
	/* Differences are distance - petrol. 
	 * If result is positive, it means surplus, 
	 * otherwise it need petrol before car can arrive there
	 * Then add another list to double it so
	 * the result is
	 * station1, station2, station3, station4, station1, station2, station3, station4,
	 */
	public static int[] getDifferences(int[][] data){
		int[] result = new int[data.length*2];
		for (int i = 0; i<data.length; i++){
			result[i] = data[i][0]-data[i][1];
			result[i+data.length] = result[i];
		}
		
		return result;
	}
	
	public static List<Integer> getStartStations(int[] differences){
		List<Integer> result = new ArrayList<Integer>();
		for (int i = 0; i<differences.length/2; i++){
			if (differences[i]>=0){
				//When <0, then it can not start here. 
				//It will not arrive to the next station
				
				//Start from station[i]
				boolean isCompleted = true;
				int sum = 0 ;
				for (int j=i;j<differences.length/2+i;j++){
					sum = sum + differences[j];
					if (sum<0){
						//
						isCompleted = false;
						break;
					} 
				}
				if (isCompleted){
					result.add(i);
				}
			}
		}		
		return result;
	}
}

- skywalker42345678 April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi D, have you got any face2face interview call??

- Abhijit April 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Guys,

Here is the clean code!!

#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <vector>

using namespace std;

int main(){

	ifstream input("temp.txt");
	string line;
	string word;
	string src, dest;
	int limit;
	int dist;
	vector<int> factor;
	vector<string> petrol_pump;
	while(getline(input, line)){
		istringstream iss(line);
		iss >> src >> dest >> limit >> dist;
		petrol_pump.push_back(src);
		factor.push_back(limit - dist);
	}

	//int petrol_remain = new int[totalNumOfPetroPump];
	for(int start = 0; start < factor.size(); ++start){
		int result = 0;
		bool flag = true;
		int y = start;
		do{
			result += factor[y];
			if(result < 0){
				flag = false;
				break;
			}
			y = (++y)%factor.size();
		}while(y != start);

		if(flag)
			std::cout << "starting point: " << petrol_pump[start] << std::endl;
	}

	input.close();
}

- Punit Patel April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can use travelling salesman problem to solve this question where a salesman is required to travel different points and finally come back to the point of origin optimally.

- Bakhtiar March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why? There is a trivial quadratic algorithm (brute force).

- Loler March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

If the value of n is large, brute force method will be computationally expensive. To solve this problem you need to have at least one hamiltonian path existing in the graph of gas stations connected to each other. If there are more than one paths then you need to find out the optimal path. Kindly wiki for hamitonian path

- Bakhtiar March 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You say brute force is computationally expensive, fine. But, then want to run a hamiltonian path algorithm!?

- Loler March 28, 2013 | Flag


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