CareerCup

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

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.

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

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

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