## Amazon Interview Question for SDE-2s

Team: Product Details Page
Country: India
Interview Type: In-Person

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

Can you give an example ???

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

What is meaning of non-increasing and non-decreasing sub-sequence?

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

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

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

If you had already done this, then now do you u want some other solution ?

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

A dynamic solution plus caching technique is implemented. In the best case it has O((n-m)^2) computation complexity. And it has O(n*m) space complexity. Details: cpluspluslearning-petert.blogspot.co.uk/2016/03/dynamic-programming-find-difference-of.html

Test

``````void TestFindDiffOfAscAndDescSeq()
{
{
bool exceptionCaught = false;
try {
const std::vector<int> input;
GetDiffOfAscendingAndDescedningSequence(input, 2);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);

exceptionCaught = false;
try {
const std::vector<int> input = { 1, 2, 3 };
GetDiffOfAscendingAndDescedningSequence(input, 1);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);

exceptionCaught = false;
try {
const std::vector<int> input = { 1, 2, 3 };
GetDiffOfAscendingAndDescedningSequence(input, 4);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);

exceptionCaught = false;
try {
const std::vector<int> input = { 1, 2, 3 };
GetDiffOfAscendingAndDescedningSequence(input, 1);
}
catch (const InvalidParamException &e) {
exceptionCaught = true;
}
catch (...)
{
}
assert(exceptionCaught == true);
}
{
const std::vector<int> input = { 1, 2, 3, 4, 5, 6, 7, 8 };
assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 70);
assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 1);
}
{
const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1 };
assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == -28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == -56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == -70);
assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == -56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == -28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == -8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == -1);
}
{
const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 13, 14, 15, 16, 17, 18 };
assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 8*8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 8*28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 8*56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 8*70);
assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 8*56);
assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8*28);
assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 8*8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 9) == 8);
assert(GetDiffOfAscendingAndDescedningSequence(input, 10) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 11) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 12) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 13) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 14) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 15) == 0);
assert(GetDiffOfAscendingAndDescedningSequence(input, 16) == 0);
}

}``````

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

i implemented with a bit of dp complexity would be n^2*m

``````class Q1 {

/**
* @param args
*/
public static void main(String[] args) {

int[] arr = {1,2,3,-1,9,8};
int n =6;
int m=3;
if(m==1){
System.out.println(0);
return;
}

int[] decP  = new int[n];
int[] incP = new int[n];
int[] dec = new int[n];
int[] inc = new int[n];
for(int i=0;i<n;i++){
decP[i]= 1;
incP[i]=1;
}
for(int l=2;l<=m;l++){
for(int i=l-1;i<n;i++){
dec[i] = 0;
inc[i] = 0;
for(int j=l-2;j<i;j++){
if((arr[i]<=arr[j]))
dec[i] = decP[j]+dec[i];

if(arr[i]>=arr[j]){
inc[i]  = incP[j]+inc[i];

}
}
}
decP = dec.clone();
incP = inc.clone();
}
int diff=0;

for(int i =(m-1);i<n;i++)
diff =diff+inc[i]-dec[i];

System.out.println(diff);

}

}``````

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

``````public static void main(String[] args) {
/**
* n = 11
* arr = {1, 2, 3, 4, 1, 8, 9, 11, 2, 1, 0}
* m = 3
* increasing sequences of size 3 = [(1,2,3),(2,3,4),(1,8,9),(8,9,11)]
* decreasing sequences of size 3 = [(11,2,1),(2,1,0)]
* diff =
*/

int sequence[] = {1, 2, 3, 4, 1, 8, 9, 11, 2, 1, 0};
int incCount[] = new int[11];
int decCount[] = new int[11];
int diff = 0;

incCount[0] = 1;
decCount[0] = 1;
for( int i = 1; i <= sequence.length - 1; i++ ){
if( sequence[i] >= sequence[i-1] ) {
incCount[i] = incCount[i-1] + 1;
decCount[i] = 1;
}else{
incCount[i] = 1;
decCount[i] = decCount[i-1] + 1;
}
}

for( int i = 1; i <= sequence.length - 1; i++ ){
if( incCount[i] >= 3) diff += 1;
if( decCount[i] >= 3) diff -= 1;
}

System.out.println(Math.abs(diff));

}``````

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

clean code.

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

package com.mayank.Amazon;

import com.sun.org.apache.xalan.internal.xsltc.compiler.sym;

public class SequenceTest {

public static void main(String[] args) {
/**
* n = 11
* arr = {1, 2, 3, 4, 1, 8, 9, 11, 2, 1, 0}
* m = 3
* increasing sequences of size 3 = [(1,2,3),(2,3,4),(1,8,9),(8,9,11)]
* decreasing sequences of size 3 = [(11,2,1),(2,1,0)]
* diff =
*/

int arr[]={1, 2, 3, 4, 1, 8, 9, 11, 2, 1, 0};
int n =11;
int m =3;
int incCount=0;
int decCount=0;
int i=0;

for(i=0; i<=n-m ;i++)
{

if(arr[i]<arr[i+1])
{
if(arr[i+1]<arr[i+2])
{
incCount=incCount+1;

}
}
else if(arr[i]>arr[i+1]){
if(arr[i+1]>arr[i+2])
{
decCount=decCount+1;
}
}
}
System.out.println(incCount);
System.out.println(decCount);
System.out.println("difference is -----"+(Math.abs(incCount)-Math.abs(decCount)));
}

}

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

``````package com.mayank.Amazon;

import com.sun.org.apache.xalan.internal.xsltc.compiler.sym;

public class SequenceTest {

public static void main(String[] args) {
/**
* n = 11
* arr = {1, 2, 3, 4, 1, 8, 9, 11, 2, 1, 0}
* m = 3
* increasing sequences of size 3 = [(1,2,3),(2,3,4),(1,8,9),(8,9,11)]
* decreasing sequences of size 3 = [(11,2,1),(2,1,0)]
* diff =
*/

int arr[]={1, 2, 3, 4, 1, 8, 9, 11, 2, 1, 0};
int n =11;
int m =3;
int incCount=0;
int decCount=0;
int i=0;

for(i=0; i<=n-m ;i++)
{

if(arr[i]<arr[i+1])
{
if(arr[i+1]<arr[i+2])
{
incCount=incCount+1;

}
}
else if(arr[i]>arr[i+1]){
if(arr[i+1]>arr[i+2])
{
decCount=decCount+1;
}
}
}
System.out.println(incCount);
System.out.println(decCount);
System.out.println("difference is -----"+(Math.abs(incCount)-Math.abs(decCount)));
}``````

}

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

Hey @mruday4friendz can you please be little bit helpful? What is xyz? What was your bug and Brute force method? Why u did not explained your approach clearly? Why this suspense? I guess you want people to solve it by themselves which is nice but as you can see we r stuck here as clearly answer is not known.

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.