## Amazon Interview Question for Applications Developers

• 3

Country: United States

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

DP solution in C#

onestopinterviewprep.blogspot.com/2014/03/traverse-array-in-shortest-number-of.html

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

FUCK you codechamp and your sock puppets.

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

All above solution is non-linear complexity. if the question is only the number of steps then I have O(n) solution. Mine function return -1 if there is no feasible solution

``````#include <iostream>
#include <vector>

using namespace std;

int minJump(vector<int> jumps)
{
size_t n = jumps.size();

bool feasible = true;
size_t lend = 1;
int jump_cnt = 1;
int i = 0;

while (feasible)
{
size_t lr = 0;
for ( ; i < lend; ++i)
if (i + jumps[i] > lr)
lr = i + jumps[i] + 1;
if (lr >= n)
break;
feasible = (lend < lr);
lend = lr;
++jump_cnt;
}
return feasible ? jump_cnt : -1;
}

int main()
{
//int a[] = {1, 5, 4, 6, 9, 3, 0, 0, 1, 3};
int a[] = {2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
std::vector<int> va(a, a + sizeof(a) / sizeof(a));
std::cerr << minJump(va);

}``````

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

Ahh!! The greedy algorithm!!

``````The above algorithm works as follows:

1. Let initial position be '0'.

2. If current position is 'i' then the frog can jump by atmost Array[i] cells. The frog will jump on one of the cells from Array[i+1] to Array[i + Array[i]]. Now from these cells choose the one which can take the frog to the farthest.
e.g { 3, 2, 4, 4, _ , _ , _ , _ , _ }. In this case, the frog will jump from '3' to second '4' because this second '4' will take it to the farthest. This "greedy choice" is right because the positions to which the frog can jump from second '4' also include all of the positions to which the frog can jump from '2' and first '4'.

3. Continue Step-2 till the frog jumps on/skips the last cell.

This algorithm runs in O(n) time because the frog considers each cell only once!
Also extra space used is O(1).``````

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

@EOF: yes, this solution will also work.

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

I understood the approach, but i don't understand how the complexity will be O(n), because for every cell we need to consider all the positions it can go to and then choose the one which will take it farthest

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

Performance is linear as it is at least as good as 2n where n is the size of array.

This can be proven by contraction.

Suppose the performance is 3n or worse.
That implies that there is at least some index 'j' that you evaluate 3x or more. (some index you loop over three times)

In order to evaluate 'j' 3 or more times, there must be 3 indices that you jumped from when evaluating 'j'. Let those 3 indices be 'a', 'b' & 'c', encountered in that order.

``{ … a … b … c … j ... }``

'c' must allow you to jump farther in array than 'b' since you chose 'c' after 'b'.

But 'c' would have been evaluated on both the iteration from 'a' and the iteration from 'b'. This must be true because the index of 'j' is greater than 'a', 'b' and 'c'. Since you encountered 'j' on all 3 iterations, you certainly encountered 'c' from the first 2 (from a & b)

This is a contradiction because if c gets you farther than b, then you would have chosen c when iterating from a.

The contradiction proves that there is not a j that you evaluate 3 or more times. So the most you evaluate any array index is 2 or less; therefore, the performance is linear O(2n) = O(n)

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

@EOF : Your greedy approach is wrong.
Consider this case:
3,3',2,2',1,100,Destination (' is just to differentiate)
If you take greedy approach , you will take path :
3,3',2',100,Destination = 5 jumps (at 2nd jump : Max of 3',2,2' = 3')
While the answer would be 3,2',100,Destination = 4 jumps

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

``````// Returns minimum number of jumps to reach arr[n-1] from arr
int minJumps(int arr[], int n)
{
int *jumps = new int[n];  // jumps[n-1] will hold the result
int i, j;

if (n == 0 || arr == 0)
return INT_MAX;

jumps = 0;

// Find the minimum number of jumps to reach arr[i]
// from arr, and assign this value to jumps[i]
for (i = 1; i < n; i++)
{
jumps[i] = INT_MAX;
for (j = 0; j < i; j++)
{
if (i <= j + arr[j] && jumps[j] != INT_MAX)
{
jumps[i] = jumps[j] + 1;
break;
}
}
}
return jumps[n-1];
}``````

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

I believe we need to reach position "n", meaning jump through all the array.

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

Here is a DP solution in C#.
Time complexity is O(N). Each index is evaluated only once. You can see it by looking at the print traces.

``````private static Hashtable cachedResults = new Hashtable();

private static int CacheAndReturn(int index, int jump)
{
return jump;
}

private static int MinJump(int[] array, int index)
{
if(cachedResults.ContainsKey(index))
return (int)cachedResults[index];

Console.WriteLine("Evaluating index: " + index);

if (index >= array.Length - 1)
return CacheAndReturn(index, 0);

if (array[index] >= array.Length - index - 1)
return CacheAndReturn(index, 1);

int min = Int32.MaxValue;
for (int x = 1; x <= array[index]; x++)
{
int temp = MinJump(array, index + x);
if (temp < min)
{
min = temp;
}
}

if (min != Int32.MaxValue)
{
return CacheAndReturn(index, 1 + min);
}
else
{
return CacheAndReturn(index, Int32.MaxValue); // no jump
}
}``````

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

How is this O(N) ?
If each array value =N
for (int x = 1; x <= array[index]; x++) will run N time for each recursion and hence total run time = O(n*n)

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

Here is the code in O(n) and O(1) space

``````#include <stdio.h>
#include <conio.h>

void findJumps(int arr[],int n)
{
int i,len=0,prev;
if(arr>n)
{
printf(" No of jumps are 1 ");
}
else
{
for(i=0;i<n;)
{
if(i+arr[i]>=n-1)
{
len=len+1;
break;
}
i=arr[i+arr[i]];
if(i==0&&i<=n-1)
{
len=len+arr[i];
break;
}
len=len+1;
}
}
if(len==0)
{
printf(" No jumps are there ");
}
else
{
printf(" Number of jumps are %d ",len);
}
}
int main()
{
int arr[]={1,5,4,6,9,3,0,0,1,3};
int n=sizeof(arr)/sizeof(arr);
findJumps(arr,n);
}``````

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

A greedy like this does not work. Simple counter-example:
arr[] = {2,5,0,0,0};
Answer is 2, this code says "no jumps are there". You need to check all N positions to jump, not just the furthest away at each step.

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

Thanks for pointing this out. I have updated the code it will work now

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

Java Code :

int[] a = {2 ,5 ,9 ,6 ,9 ,3 ,0 ,0 ,1 ,3 ,13};

int min = (a.length - 1 - 0 - a);
int step = a;
int max_jump = 1;
int sum = 0;
int index = 0;
String strPosition=0+",";
for (int i = 1; i < a.length; i++) {

--step;
sum = (a.length - 1 - i - a[i]);
if (sum <= min) {
min = sum;
index = i;
}
if (step == 0) {
++max_jump;
step = a[index];
strPosition +=" "+index+",";
}
}

System.out.println(" position "+ strPosition+" number of jumps "+ max_jump);

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

My implementation of greedy solution suggested by @EOF. Runtime is O(N * L) where N is the size of array and L is the average length of jumps.

``````#import <stdio.h>

int leastJumps(int *array, int array_length);

int main(){
int jumps[] = {2,5,0,0,0};
int least_Jumps = leastJumps(jumps, 5);
printf("Max jumps: %d\n", least_Jumps);
return 0;
}

int leastJumps(int *array, int array_length){
int jumps = 0; // total of number of jumps to reach end

int curr_index = 0;

while(1){

int max_jump_length = array[curr_index]; //  maximum amount you can jump for array[curr_index]

if(curr_index + max_jump_length >= array_length-1){
// Can reach end of array with 1 more jump from this position
return jumps;
}

int best_index = array[curr_index]; // best index to jump to from array[curr_index]
for(int j = curr_index+1; (j <= curr_index+max_jump_length && j < array_length); j++){
if(array[j] > array[best_index]) best_index = j;
}
if(array[curr_index] == 0){
}else{
jumps++;
}
}

}``````

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

Greedy approach will not work.
Run your code on {3,3',2,2',1,100,1}; (' for discrimination)
It prints 4 (3->3'->2'->100->1)
while the answer should be 3 (3->2'->100->1)
you can cross verify that this should indeed have been the answer if you replace 3' with something < 2' : (3,1,2,2',1,100,1) : prints 3

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

The ranges of jumps are more or less mutually inclusive , the only necessary info to maintain is the furthest jump
then you search the furthest jump you can make the next step with in the range you can reach from the last jumps

``````#include<stdio.h>
#include<stdlib.h>

void f(int *ary, int size){
int bgn, end=-1;// inclusive end, exclusive bgn
int stp_cnt=0;
int leap_dst=0;  //the furthest frog can jump next stp
int ary_end=size-1;
do{
bgn=end;
end=leap_dst;

int i;
stp_cnt+=1;
for(i=end;i>bgn;i--)
if(leap_dst<i+ary[i])
leap_dst=i+ary[i];
if(leap_dst==end){
printf("unreachable\n");
return;
}
}while(leap_dst<ary_end);
printf("%d\n",stp_cnt);
}
main(){
int ary1[]={1, 5, 4, 6, 9, 3, 0, 0, 1, 3};
int ary2[]={2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
f(ary1,10);
f(ary2,10);
}``````

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

Simple python approach using memoization.
Thanks to memoization the inner recursive function is called only once for each array element.

Each call at position i will examine at most n-i elements, so the total number of array accesses is O(n^2), and extra space required is O(n)

``````def min_steps(a):
n = len(a)
if n == 1:
return 0  #edge case!

steps = [None] * n  #Memoization will help us avoiding redundant recomputation

def rec_min_step(a, i):
#Invariant: i < n - 1 [edge cases are handled separately, and this function will never recurse on i >= n - 1
n_steps = float('inf')
m = a[i]

if i + m >= n - 1:
#can reach the last element with one jump
steps[i] = 1
return 1
else:
#test every possible jump, from 1 to the max possible value
for j in xrange(i + 1, i + m + 1):  #xrange right guard is exclusive
if steps[j] is None:
rec_min_step(a, j)  #will assign a value to steps[j]
if steps[j] < n_steps:
n_steps = steps[j]

#add to the recursive value 1 for this jump
steps[i] = n_steps + 1
return n_steps + 1

return rec_min_step(a, 0)``````

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

Python implementation of the greedy algorithm, which requires O(n) time and O(1) space

``````def greedy_min_steps(a, i=0, steps=0):
best_jump = i
best_jump_pos = i
n = len(a)
if i == n - 1:
return 0

m = a[i]
if m + i >= n - 1:
return steps + 1

for j in xrange(i + 1, min(n - 1, i + m + 1)):
s =  a[j] + j
if s > best_jump_pos:
best_jump_pos = s
best_jump = j

if best_jump == i:
return float('inf')
else:
return greedy_min_steps(a, best_jump, steps + 1)``````

You can test that this and the memoization versione always return the same value

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

``````void Main()
{
int[] input = new []{2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
Console.WriteLine(FindMinimumJumps(input,0,0));
}

int FindMinimumJumps(int[] input, int currentPosition, int numberOfJumps)
{
int lastPosition = input.Length - 1;
if(currentPosition > lastPosition)
return int.MaxValue;
else if(currentPosition == lastPosition)
return numberOfJumps;

int maxJump = input[currentPosition];
if(maxJump == 0)
return int.MaxValue;

int minHops = int.MaxValue;
for(int i = 1;i<=maxJump;i++)
{
minHops = Math.Min(minHops, FindMinimumJumps(input, currentPosition + i,numberOfJumps+1));
}

return minHops;
}``````

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

This can be solved by converting it to graph.
1. Consider each array element A[i] as vertex Vi.
2. Value "val" at A[i] will tell you the connectivity of Vi other vertex Vj.
Vi ----->V(i+1)
|
+-----------------V(i+2)
|
.
+----------------------------------V(i+val)
3. Create adjacency matrix and apply shortest path algo.

In fact given array is the compact form of adjacency list.

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

Using DP to solve this problem. maybe o(n^2)

``````public static int getMinJumpCount(int[] data){
int[] count = new int[data.length];

for(int i = data.length - 2; i >= 0; i--){
if(data[i] == 0)
count[i] = 0;
else if(i + data[i] >= data.length - 1)
count[i] = 1;
else{
count[i] = data.length;
for(int j = i + 1; j <= i + data[i] && j < data.length; j++){
if(count[j] != 0 && count[i] >= count[j] + 1)
count[i] = count[j] + 1;
}
}
}
return count;
}``````

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

None of this makes any sense at all. That question makes absolutely no sense... are you all speaking Klingon?

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

The simplest code would be:

``````def jump(a):
#a = [2, 0, 2, 1, 2];
steps = 0

if len(a) == 0 or len(a) == 1:
return 0

for i in range(1, len(a)):
a[i] = max(a[i], a[i-1]-1)

i=0;

print a;
while i<len(a)-1:
steps+=1
i+=a[i]

return steps;``````

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

We can use BFS to get the solution as below:
[1 5 4 6 9 3 0 0 1 3]
We need to make a Directed acyclic graph for this array and then all we need to do is to find out the minimum number of hops till we reach the destination which is 3 in this case.

Anyway if someone can post a DP solution with clear explanation that would be great.

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

dp solution:

``````int jumps[] = {2, 7, 5, 4, 3, 2, 2, 0, 3};
#define N sizeof(jumps)/sizeof(jumps)
int main()
{

int i, j;
int *min_jump;

min_jump = malloc(sizeof(int)*N);
memset(min_jump, 0, sizeof(int)*N);

min_jump = 0;
for(i=1;i<N;i++)
min_jump[i] = i;

for(i=0;i<N;i++)
for(j=1;j<=jumps[i];j++)
if(min_jump[i]+1 < min_jump[i+j])
min_jump[i+j] = min_jump[i]+1;

printf("%d\n", min_jump[N-1]);
return 0;
}``````

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

I prefer to approach this kind of problems backwards - from the end to the beginning.
We can use DP with N states. dp[i] means the minimum amount jumps to go from position i to the end of the array (position N).
A BFS is also perfectly fine here. The time complexity of both algorithms will be the same - O(N * Max_Jump).

``````// I will assume there is always a valid solution
int minJumps(int jumps[], int n) {
vector<int> dp(n+1, n*2);// n*2=infinity: n*2 is more than any valid solution
dp[n] = 0;
for (int i = n-1; i >= 0; i--)
for (int j = 1; j <= jumps[i] && i+j <= n; j++)
dp[i] = min(dp[i] , 1 + dp[i+j]);
return dp;
}``````

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

I have the O(N) solution that you mind want to check out

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

Here, dp[i] stores minimum steps to reach end from ith position.
Initially, dp[n-1]=0 because frog is at end. Start from right end and go towards left to calculate steps.

``````#include<stdio.h>
#include<limits.h>
#include<iostream>
#include<stdlib.h>
using namespace std;

int *dp;
void calc(int *a,int index,int n,int steps)
{

if(index<0)
return;

int myMin=INT_MAX;
for(int i=1;i<=a[index] && index+i<n;i++)
{
int x = dp[index+i];
if(x<myMin)
myMin = x;
}
if(myMin<dp[index]-1)
dp[index]=myMin+1;
calc(a,index-1,n,steps+1);
}

int main()
{
int n;
cin>>n;
int *a = (int*)calloc(n,sizeof(int));
dp = (int*)calloc(n,sizeof(int));
for(int i=0;i<n;i++)
{
cin>>a[i];
dp[i]=INT_MAX;
}
dp[n-1]=0;
//cout<<calc(a,0,n,0)<<endl;
calc(a,n-1,n,0);
cout<<dp<<endl;

return 0;
}``````

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

A Dynamic Programming solution you asked is here>>>

``````WORST CASE TIME: O(n^2)
EXTRA SPACE: O(n)

1. Create a Jumps[] array.
Jumps[i] = minimum number of jumps required from index i to reach end.
Assuming 0-based indexing, Jumps[n-1] = 0 (because "n-1" is the last
index of the array).
2. Now,
if (Array[i] == 0)
Jumps[i] = INFINITE; //once reached here, cannot jump further...
else if (Array[i] >= Array.length - i - 1)
jumps[i] = 1; //can reach the end in a single jump from here...
else let Array[i] = k (suppose) then
Jumps[i] = 1 + min(Jumps[i+1], Jumps[i+2], ... , Jumps[i+k])
3. Proceed from right to left and return Jumps as the answer.

NOTE: MAY BE I'VE NOT CONSIDERED SOME BOUNDARY CASES!``````

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

You are missing many cases

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

I dont know why u asked for DP solution when it can be done by applying simple greedy solution..

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

``````public static int findMinumumJump(int array[]){
if(array == null){
return -1;
}

if(array.length == 1){
return 0;
}

int jumps[] = new int[array.length];

for(int i = array.length - 2; i >= 0 ; i--){
if(array[i] == 0){
jumps[i] = Integer.MAX_VALUE;
continue;
}

if((array[i] + i) >= array.length - 1){
jumps[i] = 1;
}
else{
int minumnNumber = Integer.MAX_VALUE;
for(int j = i + 1; (j < array.length - 1) && (j <= array[i] + i); j++){
if(jumps[j] < minumnNumber){
minumnNumber = jumps[j];
}
}
jumps[i] = minumnNumber + 1;
}
}
return jumps;
}``````

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

Simple

``O(n)``

solution: the frog looks into the array, and then jumps to the end based on whichever tile he lands on.

``````def jump(list,qty):
if len(list) <= qty:
return 0
qty += 1
return 1+jump(list[qty:], list[qty-1])

def main(script,*args):
list = [1, 5, 4, 6, 9, 0, 0, 1, 3]
print "arr = ", list, "; frog jumps = ", jump(list, 0)

list = [2, 8, 3, 6, 9, 3, 0, 0, 1, 3]
print "arr = ", list, "; frog jumps = ", jump(list, 0)

if __name__ == '__main__':
import sys
main(*sys.argv)``````

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

Gives incorrect solution for input e.g. [1, 5, 4, 6, 9, 3, 0, 0, 5, 3, 0, 0, 7, 0, 0, 2, 4, 1].

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

Based on WHAT??? This doesn't make any sense!!!

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

I'm not sure I am understanding the question properly but here is an overview of my solution.
Greedy algorithm
Example:[1 5 4 6 9 3 0 0 1 3 13]
i 0 1 2 3 4 5 6 7 8 9 10
start at i = 0;
We first look at i = 0 which would give back the set of indecies i = {1}
we look at i = 1 which would give us back the set of indecies i = {2,3,4,5,6}
i = 2 -> {3,4,5,6}, i = 3 -> {4,5,6,7,8,9}, i = 4 -> {5,6,7,8,9,10,11,12,13}, i = 5 -, i > {6,7,8}= 6 -> {}
we choose the index that will give the set with the highest possible index (i = 4)
we look at i = 4 which would produce the set {5,6,7,8,9,10,11,12,13}
we are done since this set contains the last index.

O(n) time

Producing the sets is an easy way of talking about it. For coding purposes, just choosing the (next highest number + the distance) from your current index will get you to your next index.

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

I still don't understand the question and the example given as how we got the answer as 3 and 2 respectively.

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

We start at position 0.
[1 5 4 6 9 3 0 0 1 3]

[2 8 3 6 9 3 0 0 1 3]

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.