Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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
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;
}
}
}
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;
}
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;
};
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;
}
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
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);
}
}
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;
}
}
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);
}
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);
}
}
}
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
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
/* 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)
*/
The number of ways to jump to n steps is the n-th Fibonacci number!
- ninhnnsoc February 27, 2014F[n] = F[n-1] + F[n-2];
F1 = 1; F2 = 2;