Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

It's a dynamic programming question. And the solution format is just like the fabocci sequence. For example, if w = 1, then the answer is 1, if w = 2, the answer is 2, if w = 3, the answer is 1 + 2 = 3, if w = 4, the answer is 2 + 3 = 5. And the dynamic equation is
dp[n] = dp[n - 1] + dp[n - 2]. Here is the code:

``````public class Solution{
public int dp(int w){
if(w == 1){
return 1;
}
if(w == 2){
return 2;
}
int prev1 = 1;
int prev2 = 2;
int current = 0;
for(int i = 3; i <= w; ++i){
current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
return current;
}

public static void main(String[] args){
int w = 4;
Solution solution = new Solution();
System.out.println(solution.dp(w));
}
}``````

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

Above problem is nothing but a fibbonacci series .
f(n) = f(n-1) + f(n-2)

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

@striker, the question isn't how many tiles, the question is how many ways.

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

no, it seems to me that it is not fibonacci problem, it is a simple probability problem

for eg, for 3 = 3, using ur fiboinacci formula, it is giving answer as 3, but there are only 2 ways we can put tiles on a 2 * 3 floor.

the answer is (W/2) * 2 ways in total.

Please correct if my understanding of the question is wrong.

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

With width = 3, there are 3 ways we can arrange, not 2.

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

Isn't the answer to this N!
when w=1 there is 1 way
when w=2 there is 2 way
when w =3 there is 6 ways
just think of the tiles as a,b,c in the 3 slots it can be arranged in 6 different ways

Comment hidden because of low score. Click to expand.

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.