## Amazon Interview Question for Software Engineer / Developers

• 0

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

DP problem. Assume F(N,X) is number of ways to pick X from array[N] without two consecutive number.
1.We pick last one in N, F(N-2,X-1)
2.We don't pick last one in N, F(N-1,X)
add these two case we get
F(N,X)=F(N-2,X-1)+F(N-1,X)

initial condition: F(N,1)=N if N>0, F(0,X)=0, F(N,X)=0 if N<=X

Test: N=6, X=2
(1,3) (1,4) (1,5) (1,6) (2,4) (2,5) (2,6) (3,5) (3,6) (4,6) 10 combinations
F(N,X)=F(N-2,X-1)+F(N-1,X)
F(6,2)=F(4,1)+F(5,2)=4+F(3,1)+F(4,2)=7+F(2,1)+F(3,2)=9+F(1,1)+F(2,2)=10

Test: N=6, X=3
(1,3,5) (1,3,6) (1,4,6) (2,4,6) 4 combinations
F(N,X)=F(N-2,X-1)+F(N-1,X)
F(6,3)=F(4,2)+F(5,3)=F(2,1)+F(3,2)+F(3,2)+F(4,3)=2+1+1+F(2,2)+F(3,3)=4

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

if N is odd the (N/2 +1) non consecutive numbers are there. Else If N is even then (N/2)
Non consecutive number are there...
run selection on these non consecutive numbers using combination i.e. (N/2) C (X)

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

This doesnt include all the combination. This solution only includes purely odd set or purely even number sets. For the sets of x elements it can include mixed of odd and even numbers.
Why can't this be C(N,X) minus the consecutive set?

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

C(N-(X-1), X)

Suppose a choice is a1, a2, ..., aX.
Let a1' = a1, a2' = a2 - 1, ..., aX' = aX - (X - 1), then, a1', a2', ..., aX' is the X combination out of N - (X - 1) numbers.
On the other hand, given any choice of a1' < a2' < ... < aX' in N - (X - 1) numbers, we can get the solution a1, a2, ..., aX.

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

This looks perfect!

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

0

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

0

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

0

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

use dynamic programming
assume c(n,x) is # of ways to select x elements from the first n elements with the last element selected, then c(n,x)=sum{i=1..n-2}c(i,x-1), initial conditions are c(n,1)=1 and c(i,x)=0 for any i<2x-1. At last the total number of ways is sum{i=1..n}c(i,x)

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

I mean sum{i=1..N}c(i,X) for the final result

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

0 if N < 2x-1
(x+1)^(N-2x+1) if N >= 2x-1

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

C(N,X) -N-1+X

is the number of ways one can do..

correct if i am wrong

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

Wrong.

For X = N/2 + 1 answer should be zero as there will always be two which are adjacent.

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

1,2,3,4,5,6....N
1. We can pick X elements at a space of 1 ( which are odd or even numbers )
space=1, N/x times
2. We can pick X elements each spaced at 2..
space =2 N/2X times
3. We can continue to pick x lements , each element spaced at X-1. ( as long as X(X-1)<N)
space = x-1, N/2(x-1) times

so this is a summations
sum(N/px) where p varies from 1 to X-1
provided other conditions are satisfied.
if we know the value of N and X, then the solution is a geometric series

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

For n = 6 and x = 2,
there are 4 combinations (1, 3) (2, 4) (3, 5) (4,6), however N/x gives me only 3 combinations.

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

... (1,4)(1,5)(1,6)(2,5)(2,6)(3,6)... and "loneranger" probably needs to look at combinations.

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

Combination minus consequtive combinations which to me sounds like (N /X) - (N-X+1)

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.