Amazon Interview Question
SDE-2sTeam: Product Details Page
Country: India
Interview Type: In-Person
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);
}
}
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);
}
}
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));
}
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)));
}
}
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)));
}
}
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.
So I request you to please provide your detailed answer and give some explanations. Please provide some help here.
Can you give an example ???
- hnatsu March 04, 2016