## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

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

1. sort the slabs on the basis of any one dimension.
2. find longest increasing subsequence with respect to other dimension.

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

Sort in both directions. First for length then width.
Then find the longest increasing subsequence with length[i] < length[j] and width[i] < width[j] where i < j
This could be done in O(nlogn) + O(n)

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

what Psycho said is correct. We should sort on one dimension and then sort on the other.

Eg: After sorting on length lets say this is what you get: 1,4 1,2 2,5 4,6
Now you might get wrong answer as 3 with what Anonymous said.

But sort the above array on width so to get this:
1,2 1,4 2,5 4,6

Now you'll get the correct ans as 4.

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

I think this problem will require DP

for input sorted on length assume we get 1,3 1,7 2,4 2,8 2,7 3,10 3,8
and on sorting the breadth we get 1,3 2,4 1,7 2,7 2,8 3,8 3,10

we will get two increasing series starting from 0th index to 6th excluding 3rd element and one from 3rd to 6th so we need to maintain them in an array using dp to get the longest increasing subsequence

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

This is a simplified form of box stacking problem. An optimized solution can be given using Dynamic Programming.
1) Sort boxes on basis of base area (higher to lower) .
Now we define h(j) = max height with which box j ends up on the top.

h(j) = max(h(i)) + height of jth tower, such that li > lj and wi > wj for all i <j.

By formulating this recursion we will get the answer.

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

Dynamic Programming because this problem is a recurrence relation:

Let m[h,w] represent the max slabs which you can stack, including the base slab:

m[0,0]=0
m[1,1]=1
m[1,2]=1
m[2,1]=1
m[2,2]= 1 + m[1,1] = 1+1=2
m[3,2] =1 + m[2,1] + m[1,1] = 1 + 1 + 1 = 3
m[2,3] = 1 + m[1,2] + m[1,1] = 1 + 1 + 1 = 3
m[3,3] = 1 + m[2,2] +m[2,1] + m[1,2] = 1 + 2 + 1 + 1 = 5
m[h,w] = 1 + Sum(m[h-k,w-n]) where 1<=k<=h-1, and 1<=n<=w-1

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

``````import java.util.Scanner;

class Slab implements Comparable<Slab>{
int len,wdt;
public Slab(int len,int wdt){
this.len = len;
this.wdt = wdt;
}
@Override
public int compareTo(Slab o) {
// TODO Auto-generated method stub
if(o.len*o.wdt == this.len*this.wdt)
return 0;
else if(o.len*o.wdt > this.len*this.wdt)
return 1;
else
return -1;
}

}
public class MaxSlabHeight {
static Slab ar[];
public static void quickSort(int lo,int hi){
if(lo<hi){
int mid=partion(lo,hi);
quickSort(lo, mid-1);
quickSort(mid+1, hi);
}
}
private static int partion(int lo, int hi) {
// TODO Auto-generated method stub
int pivot = lo;
int i = lo;
for( int j = lo+1;j<=hi;j++){
if(ar[j].compareTo(ar[pivot])==-1){
i++;
Slab temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
Slab temp = ar[i];
ar[i] = ar[pivot];
ar[pivot] = temp;
return i;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
ar = new Slab[N];
for(int i = 0;i<N;i++){
int len=sc.nextInt();
int wdt=sc.nextInt();
ar[i]=new Slab(len, wdt);
}
quickSort(0,ar.length-1);
int heap[] = new int[N];
for(int i = 0 ; i < N ; i ++){
int j = i;
while(j>=0){
j--;
if(j<0){
heap[i]=1;
}else{
if(ar[i].len<=ar[j].len && ar[i].wdt<=ar[j].wdt){
heap[i] = heap[j]+1;
break;
}
}
}
}
int max = -1;
for(int i = 0 ; i < N ; i ++)
if(max<heap[i])
max = heap[i];
System.out.println("max heap:"+max);
}
}``````

this is a java implementation of DP explained by akki and jack

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

first line of input is no of tiles

then next line takes len
and next line with
and so on

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

Hallo,

I learnt so much in such little time about
Amazon Interview Question for Software Engineer / Developers . Even a toddler could become smart reading of your amazing articles.

I am currently working on a project that does not include storyboards and I am trying to create a user authentication and sign-in method. I was initially going to use FireBase but they did not have Carthage support so I decided to try out AWS.
Amazon Interview Question for Software Engineer / Developers I initially tried using AWSCognitoIdentityProvider framework with my custom UI but the passwordauthentication method for signing in would not trigger a result. I moved onto the AWSAuthUI framework (plus AWSAuthCore, AWSFacebookSignIn, AWSGoogleSignIn, AWSUserPoolsSignIn) with the built in UI but I keep getting the error below before even getting to the login screen.

Anyways great write up, your efforts are much appreciated.

,Merci
Irene Hynes

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More