Amazon Interview Question for Software Engineer / Developers






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

This can be done greedily.
Your greedy selection will be based on max(i+a[i ]).
So at any index j,you can take a jump of size a[j], so consider an index 'k' in the interval
j to j+a[j] such that k+a[k] is maximum and jump to that.
Time : O(n)
Space : O(1)

- nitin November 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The code I posted before is greedy approach.

- Rayden November 23, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

R u sure this will work for every cases possible ?

- Decoder March 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

<pre lang="" line="1" title="CodeMonkey52805" class="run-this">#include <iostream>
#include <vector>

using namespace std;

int find_min_steps(vector<int>& input) {

int start, end, next_start;
vector<int> result;

start = end = 0;
int n = input.size();

while (end < n-1){
int max = -1;
for(int w = 0; start<= end ; w++, start++){
if(input[start] + w > max) {
max = input[start] + w ;
next_start = start;
}
}
if(input[next_start] == 0) {
cout << endl << "not possible to traverse the array ..stuck at input index : " << next_start << endl;
return -1;
}
start = end + 1;
end = next_start + input[next_start];
result.push_back(input[next_start]);
}

cout << endl << "steps are : ";
for(int i =0; i< result.size(); ++i)
cout << endl << result[i];

cout << endl;

return result.size();
}

int main() {
vector<int> input;
int t = -1;
cout << endl << "enter input values.. (-1) to end" << endl;
do {
cin >> t;
input.push_back(t);
}while(t != -1);

input.resize(input.size() -1); //remove last pushed -1.

cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
return 0;
}
</pre><pre title="CodeMonkey52805" input="yes">
</pre>

- Anonymous November 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijkstra's algorithm or BFS
-> consider each element is a node.
-> each node value represents connections to the next k nodes. so connect edges to next k nodes.
-> edge weights are '1'.
-> find the shortest path after constructing the graph

(or maybe mapreduce can be used?)

- blueskin.neo November 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually A* would be a lot better

- blueskin.neo November 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

blueskin_neo : good thinking :)

- ding_dong November 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

could dynamic programming be applied over here...is so how/>??


i guess the recursion would look something like this

opt(i,n) = min(1+opt(k,n),..k=i+1,i+2..., |k|=arr[i])

and with bottom up i think(?) we can get a O(n) solution.

- Amm December 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about making an auxiliary array B where B[i] = the index of the first element in A[] (the original array) that can reach the element at index i. Then follow the 'pointers' backwards from B[len - 1].

- Anonymous November 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Greedy will not work !!!
5 1 3 1 2 0 6
you jump at 0 (as you can jump 5 steps ahead from the first,and according to your greedy you will) and you are dead !.

- Anonymous November 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Greedy will not work !!!
5 1 3 1 2 0 6
you jump at 0 (as you can jump 5 steps ahead from the first,and according to your greedy you will) and you are dead !.

- Anonymous November 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@above
Read the soln properly

Here decison is based on the max value of i+a[i] not on max value of a[i]

According to greedy
while(i!=n){
maxindex=i;
for(int j=i;j<i+a[i];j++)
if(j+a[j]>maxindex+a[maxindex])
maxindex=j;
}
i=j;
minjmp++;
}

- nitin November 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Greedy will fail in case the array is a = [9,8,7,6,5,4,3,2,1,2,1]. Isn't it?

- careercup22 November 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this case answer is 9 and 2.
Only two jumps.
Isn't it.

- nitin November 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey nitin, nice solution btw. I am just curious as to what is the worst case time complexity of your solution. Could you please help with that.

- Fanatic May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep an array B[] in which B[i] represents the number of jumps required to reach from i to last position. initialize B[i] = infinity for all except last. start computing from i= last-1 to i, where B[i] = 1+min(B[j] for j from i+1 to i+A[i])

- A November 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep an array B[] in which B[i] represents the number of jumps required to reach from i to last position. initialize B[i] = infinity for all except last. start computing from i= last-1 to i, where B[i] = 1+min(B[j] for j from i+1 to i+A[i])

- Annonymous November 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the array is given, and we have to start from the first one, then why we can choose the elements? Everything is determined when the array is generated.

like 1,2,3,4,5,6,7, we can only start from 1, and 1 lead us to 2, 2 lead use to 4, et.

what on earth is the question asking?

- Anonymous December 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

read the question Carefully.. you don't have to jump to the precise element. You have a range to select the elements. This question is not about how much jumps are required. It is about minimum number of jumps.

- Ashish December 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> FindMinimumJumpsInArray(vector<int> a)
{
	vector<int> jumpArray;
	int maxIndex = 0;
	
	bool bDestReached = false;
	
	while(true)
	{
		jumpArray.push(maxIndex);
		
		nextLevel = a[maxIndex];
	
		int maxValue = 0;
		
		for(int i=maxIndex+1; i<=nextLevel; ++i)
		{
			if(i == a.size())
			{
				bDestReached = true;
				break;
			}
			
			if(maxValue <= i + a[i])
			{
				maxValue = i + a[i];
				maxIndex = i;
			}
		}
		
		if(bDestReached)
		{
			break;
		}
	}
	if(bDestReached)
		return jumpArray;
	else
		return vector<int>();
	
	
}

- MP007 December 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

could you explain ur approach?

- wtf May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey tell me 1 thing, is such kind of question expected in 1st / 2nd round of amazon's telephonic interview ? or r these 4 onsite ?

- rj January 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@MP007..ur solution is wrong.

- Newbie January 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int min_selections(int arr[],int n)
{
    int i,j;
    int dp[n],min;
    dp[n-1]=1;
    for(int i=n-2;i>=0;i--)
    {
        dp[i]=1;
        min=10000;
        for(j=1;j<=arr[i]&&(i+j)<n;j++)
            if(dp[i+j]<min)
                min=dp[i+j];
        dp[i]+=min;
    }
    return dp[0];
}
int main(void)
{
	int n,arr[20];
	cout<<"Size: ";
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	cout<<min_selections(arr,n);
}

- chiragjain1989 January 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@chiragjain1989 - Awesome solution man !!!

- Manish Agarwal January 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is more like dynamic programming
we know that we have to reach the last element
Now take another array of the same size and set the last element value to 0
This is because the last element can reach to itself in ZERO steps

we use memorization in dynamic programming

1. Let jump[n] be the resultant array 
//is the array specifying number of jumps required by each element to reach the last element

2. Set jump[n-1] = 0. //if we have to reach the last element

3. for each element in the jump array starting fromt the last but one element to the first element

jump[n-i] = min(1+min( jump[n-i+1] to jum[input[n-i]])//where input is the i/p array with the possible jumps

Special case 1:
if the element can reach the last element from imput[n-i] i.e
if the element is 7th element in the 10 element array with input[7]=5 then it can directly reach last element
Therefore jump[7] = 1

Special case 2:
if the input[i]=0 for an element then jump[i] = INTEGER.MAX//so that we don't use this element to jump

4. At the end jump[0] would give us the minimum number of jumps required to reach last element from the first

example:

index: 0  1  2  3  4  5  6  7  8  9  10
input: 1  3  5  8  9  2  0  7  6  8  9

step 1: set jump[n-1]=0

index: 0  1  2  3  4  5  6  7  8  9  10
jump :                               0

step2: now 9 can directly reach 10 as it can have 8 jumps from 9. 
So is index 8, it has 6 jumps from 8 and it requires only 2 to reach 10
for 6 it would be a different story as it cannot go ahead

index: 0  1  2  3  4  5  6    7  8  9  10
jump :                   INF  1  1  1  0

5 can reach only 6 and 7 so it has to choose minimum between 1+INF and 1+1, adn so it selects 1+1=2
3 and 4 can reach directly to 10 with 8 and 9 jumps respectively so their values are 1 and 1 
index 2 can go from index 3 to 7 and selects minimum from it and adds 1 to it and so has a value of 2

index 1 can select either 2 or 3 or 4 whose values are 2, 1 and 1 resp. so it selects either 1 in it and adds its own 1
therefore jump[1]=2

index 0 can only go to 1 and so has jump[1]=3

which is the minimum number of jumps

index: 0  1  2  3  4  5  6    7  8  9  10
jump : 3  2  2  1  1  2  INF  1  1  1  0

- ketz January 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

awesome sol ketz

- Kashyap June 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey12499" class="run-this">#include <iostream>
#include <vector>

using namespace std;

int find_min_steps(vector<int>& input) {

int start, end, next_start;
vector<int> result;

start = end = 0;
int n = input.size();

while (end < n-1){
int max = -1;
for(int w = 0; start<= end ; w++, start++){
if(input[start] + w > max) {
max = input[start] + w ;
next_start = start;
}
}
if(input[next_start] == 0) {
cout << endl << "not possible to traverse the array ..stuck at input index : " << next_start << endl;
return -1;
}
start = end + 1;
end = next_start + input[next_start];
result.push_back(input[next_start]);
}

cout << endl << "steps are : ";
for(int i =0; i< result.size(); ++i)
cout << endl << result[i];

cout << endl;

return result.size();
}

int main() {
vector<int> input;
int t = -1;
cout << endl << "enter input values.. (-1) to end" << endl;
do {
cin >> t;
input.push_back(t);
}while(t != -1);

input.resize(input.size() -1); //remove last pushed -1.

cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
return 0;
}
</pre><pre title="CodeMonkey12499" input="yes">
</pre>

- Anonymous November 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int FindMax(int range, int current, int *source)
{
    int tmp;
    int currentMax = source[current+1] - (range + 1);
    int maxPosition = current+1;
    for (int i=2; i<range; i++)
    {
        tmp = source[current+i] - (range + i);
        if ( tmp > currentMax ) 
        {
            currentMax = tmp;
            maxPosition = current + i;
        }
    }
    return maxPosition;
}

int FindJumpCount()
{
    int source[11] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    int arrayEnd = 11;
    int jumpCount = 0;
    int currentPosition = 0;
    while ( (source[currentPosition] + currentPosition) < arrayEnd )
    {
        currentPosition = FindMax(source[currentPosition], currentPosition, source);
        jumpCount++;
    }
    jumpCount++;
    printf("Jump Count is %d ", jumpCount);
    return jumpCount;
}

- Rayden November 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code will not work.
e.g.
source[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};
output is JumpCount = 6 and the jumps are
[1]->[3]->[8]->[9]->[6]->[7]->[1]
But the actual jumps should be
[1]->[3]->[5]->[7]->[1]

- Tulley November 29, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For source[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};
the jumps should be
[1]->[3]->[9]->[1] which has 4 elements in the sequence, not 5

- Anonymous November 29, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rayden:
Could you please explain your logic.
why subtracting (range+i)?

- career.baghel January 12, 2011 | 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