Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

The number of ways to jump to n steps is the n-th Fibonacci number!

F[n] = F[n-1] + F[n-2];
F1 = 1; F2 = 2;

- ninhnnsoc February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it should be F[n] = F[n-1] + F[n-2] +2;

- chaos February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is F[n] = F[n-1] + F[n-2]

F[3] = F[2] + F[1]
1 1 1 part of F[2]
2 1 part of F[2]
1 2 part of F[1]

F[2]
1 1
2

F[1]
1

- qxixp February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

or the (n+1)th Fibonacci number, depending on what you consider the sequence to be.

Interesting side note. (n+1)th is the only "word" that rhymes with month.

- zack.kenyon March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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


public class RecursiveFrogJump {
    

    public static List <List<Integer>> results = new ArrayList<List<Integer>>();
    
    public static void main(String[] args){
        int sum = 5;    
        List <Integer> way = new ArrayList<Integer>();
        printJumpWays(way, 0, sum);
    }
    
    /**
     * @param way
     * @param currentValue
     * @param sum
     */
    public static void printJumpWays(List <Integer> way, int currentValue, int sum){
        List <Integer> currentWay = new ArrayList<Integer>();
        if(currentValue < sum){
            currentWay.addAll(way);
            currentWay.add(1);
            printJumpWays (currentWay, currentValue+1, sum);
            currentWay = new ArrayList<Integer>();

            currentWay.addAll(way);
            currentWay.add(2);
            printJumpWays (currentWay, currentValue+2, sum);
        }
        
        if (currentValue == sum){
            results.add(way);
            System.out.println(way);
            return;
        }
            
        if (currentValue > sum){
            return;
        } 
    }

}

- Anonymous April 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry to use a static variable, but could make the codes a little clear

#include <iostream>

using namespace std;

static int num = 0;

static void jump(int left) {
        if (left == 0) {
                ++num;
        }
        else if (left < 0) {
                return ;
        }
        jump(left - 1);
        jump(left - 2);
}

int main() {
        jump(4);
        cout << num << endl;                
        return 0;
}

- blackball February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

How long does your code take to run for, say, n = 50?

- ninhnnsoc February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is a modification:

#include <iostream>

using namespace std;

static long long num = 0;
long long memo[150];

static void jump(int left) {
        if (memo[left]!=0){
            num += memo[left];
            return ;
        }
        if (left == 0) {
                num +=1;
        }
        else if (left < 0) {
                return ;
        }
        jump(left - 1);
        jump(left - 2);
        memo[left] = num;
}

int main() {
        jump(122);
        cout << num << endl;
        return 0;
};

- ninhnnsoc February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static
{
storeSteps[1] = 1;
storeSteps[2] = 2;
}

public static int calculateSteps(int number)
{
if(storeSteps[number] != 0)
return storeSteps[number];

int steps = 0;
steps = calculateSteps(number-1)+calculateSteps(number-2);
storeSteps[number] = steps;

return steps;

}

- woo February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a typical recursion question. Simply speaking, it's a problem like: choosing from set{*,*,*....} to form a sum of N.

public static int getWays(int[] units, int step, int sum){
	if(sum == step){
		return 1;
	}else if(sum>step){
		return 0;
	}
	int way = 0;
	for(int i=0; i<units.length; i++){
		way += getWays(units, step, sum+units[i]);
	}
	return way;
}

- YIJIN February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int jumpSteps(int step)
{
if (step == 1)
return 1;
else if (step == 2)
return 2;

return jumpSteps(step - 1) + jumpSteps(step - 2);
}

int main()
{
cout<<jumpSteps(4); // Answer : 5
}


Explanation :
(1,1,1,1)
(1,1,2)
(1,2,1)
(2,1,1)
(2,2)

- Abhijeet Kandalkar February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int jump(int n){
int prev=0;
int cur=1;
for(int i=1;i<=n;i++){
int temp=cur;
cur+=prev;
prev=temp;
}
return cur;
}

- Mem February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is another DP problem, with two steps 1, 2. It is a Fibonacci sequence as mentioned above. But what if Frog can jump S1, S2 ... Sn steps?

The number of ways to n is equal to
N[n-S1] + N[n-S2] + .. N[n-Sn] if (n-Si) > 0,
N[0] + 1 if n = Si
N[0] equals 0

The time complexity is equal to n x S, n is the sum and S is number of jumps frog has
The space complexity is equal to n

- qxixp February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FrogJump {
/*
 * Frog can jump 1 or 2 steps.
 * Find ways to cover n steps.
 * Question asked at amazon.com
 */
	int max;
	int ways=0;
	public int jump(int current){
		//System.out.println(current);
		if(current<max){
			jump(current+1);
			jump(current+2);
		}
		if (current==max){
			ways=ways+1;
			return 0;
		}
		if(current>max){
			return 0;
		}
		return 0;
	}
	
	public static void main(String[] args){
		FrogJump fj=new FrogJump();
		fj.max=5;
		fj.jump(0);
		System.out.println(fj.ways);
		
	}
	
}

- abc February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the frog can jump only 1 or 2 steps, the number of combinations of 1's and 2's to reach to a given sum 'n' is given by (n+1)th term of the Fibonacci Series where

f[0] = 0;
f[1] = 1;
f[2] = 1;
f[3] = 2;
f[4] = 3
f[5] = 5;
f[6] = 8;
f[7] = 13 and so on.


So if n =5, then the number of possible steps will be (n+1)th term which is the 6th term in the fibonacci series whose value is 8.

Possible combinations :
1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 = 2+2+1 = 2+1+2 = 1+2+2

Similarly, n = 6, then the number of possible steps will be (n+1)th term which is the 7th term in the fibonacci series whose value is 13.

Possible Combinations:
1 1 1 1 1 1
1 1 1 1 2
1 1 1 2 1
1 1 2 1 1
1 2 1 1 1
2 1 1 1 1
1 1 2 2
1 2 1 2
2 1 1 2
2 1 2 1
2 2 1 1
1 2 2 1
2 2 2

Java Code :

public class Problem90 {
	public static void main(String[] args){
		int target = 6;
		System.out.println(findNumberOfSteps(target));
	}
	
	public static int findNumberOfSteps(int n){
		int prepre=0,pre=1,sum=0;
		for(int i=0;i<n;i++){
			sum = pre + prepre;
			prepre = pre;
			pre = sum;
		}
		return sum;
	}
}

- Coder March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int func(int n,int index,int* memo) {
    if(index<=n) {
        if(memo[index]!=-1)
            return memo[index];
        memo[index]=func(n,index+1,memo)+func(n,index+2,memo);
        return memo[index];
    }
    return 0;
}

- Anonymous March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int func(int n,int index,int* memo) {
    if(index<=n) {
        if(memo[index]!=-1)
            return memo[index];
        memo[index]=func(n,index+1,memo)+func(n,index+2,memo);
        return memo[index];
    }
    return 0;
}

- k2 March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ /* Frog can jump 1,2,3 ( n different) steps write the code to find out number of ways to go up to n steps */ int distance[n]; int jumps[] = { 1,2,3}; int no_of_ways = 3; distance[0] = 0; int jump(int n) { if(n==0) return 0; if(distance[n] != -1) return distance[n]; int ans = 0; for(int i=0; i<no_of_ways && n>=jump[i]; i++) { if (n==jump[i]) ans++; ans+ = jump(n-jump[i]); } return distance[n] = ans; } /* Example : distance[0] = 0; distance[1] = 1; distance[2] = 1+1 = 2 (1,1) (2) distance[3] = 1+2+1=4 (1,1,1) (2,1) (1,2) (3) distance[4] = 4+2+1=7 (1,1,1,1) (2,2) (2,1,1) (1,2,1) (1,1,2) (3,1) (1,3) distance[5] = 7+4+2=13 (1,1,1,1,1) (1,1,1,2)(1,1,2,1)(1,2,1,1)(2,1,1,1)(1,1,3)(1,3,1)(3,1,1)(2,3)(3,2)(2,2,1)(2,1,2)(1,2,2) */ - Sekhar Pedamallu March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findPath(int num, char[] path, int count) {
if(num < 0)
{
return;
}
if (num == 0) {
System.out.println("path :: " + (new String(path)));
return;
} else {

if ((num - 1) >= 0) {
path[count]='1';
path[count+1]='\0';
findPath(num-1, path, count+1);
}

if ((num - 2) >= 0) {
path[count]='2';
path[count+1]='\0';
findPath(num-2, path, count+1);
}
}

}

void frogPath() {
int num = 10;
char[] path = new char[num+1];
findPath(num, path, 0);
}

- naps March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Of Course We Can Calculate The No Of Steps By Using combinations.But It Takes Long Time.But It Follows Fibonacci Pattern

- Uda Anil Kumar March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ForgJump {
// * * * * * * * * * * /

static int count = 0;

public static void main(final String[] args) {

final int steps = 5;
jumpUtil(steps);
System.out.println(count);
}

private static void jumpUtil(final int steps) {
if (steps == 0) {
count++;
return;
}
if (steps >= 0) {
jumpUtil(steps - 1);
jumpUtil(steps - 2);

}
}
}

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

Matha matric qustion 5frog jump

- ARJUN PRATAP March 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]) {
        int finishSpot = 4;
        int t1 = countOptions(1, finishSpot);
        int t2 = countOptions(2, finishSpot);
        int result = t1 + t2;
    }

    public static int countOptions(int nextSpot, int finishSpot) {
        if (nextSpot > finishSpot) {
            return 0;
        } else if (nextSpot ==  finishSpot) {
            return 1;
        }

        return  countOptions(nextSpot + 1, finishSpot) + countOptions(nextSpot + 2, finishSpot);
    }


//n=2 => 2
//n=3 => 3
//n=4 => 5

- kkonashenkov April 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A frog can jump 1, 2, or 3 rocks at a time. In how many different ways can it reach the nth rock? Two ways are considered different if the frog does a different number of jumps or if the length of the ith jump is different. In other words, jumping two rocks then jumping one rock is different from jumping one rock then jumping two rocks. Input 1-616455 The input contains an integer n, the number of the rock the frog wants to reach. Output Print the number of different ways the frog can jump to the nth rock modulo 10° +7. Constraints 1 <= n <= 106 Example #1

- Anonymous January 25, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/* Frog can jump 1,2,3 ( n different) steps write the code to find out number of ways to go up to n steps */

int distance[n];
int jumps[] = {1,2,3};
distance[0] = 0;
int jump(int n)
{
	if(n==0)
		return 0;
	if(distance[n] != -1)
		return distance[n];
	int ans = 0;
	for(int i=0; i<no_of_ways && n>=jump[i]; i++)
	{
		if (n==jump[i])
			ans++;
		ans+ = jump(n-jump[i]);
	}	
	return distance[n] = ans;
}

/* Example
distance[0] = 0;
distance[1] = 1;
distance[2] = 1+1 = 2 (1,1) (2)
distance[3] = 1+2+1=4 (1,1,1) (2,1) (1,2) (3)
distance[4] = 4+2+1=7 (1,1,1,1) (2,2) (2,1,1) (1,2,1) (1,1,2) (3,1) (1,3)
distance[5] = 7+4+2=13 (1,1,1,1,1) (1,1,1,2)(1,1,2,1)(1,2,1,1)(2,1,1,1)(1,1,3)(1,3,1)(3,1,1)(2,3)(3,2)(2,2,1)(2,1,2)(1,2,2)
*/

- Sekhar Pedamallu March 05, 2014 | 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