CareerCup

public int[] solution(int [] input){
		
		int maxTillNow = Integer.MIN_VALUE;
		int minAfterNow = Integer.MAX_VALUE;
		int index = 0;
		
		List<Integer> result = new ArrayList<Integer>();
		for(int i = 0;i<input.length;i++){
			
			if(i>=index){
				minAfterNow = Integer.MAX_VALUE;
				for(int j=i+1;j<input.length;j++){
					if(input[j]<minAfterNow){
						minAfterNow=input[j];
						index=j;
					}
					
				}
			}
			
			if(input[i]>maxTillNow && input[i]<minAfterNow){
				
				result.add(input[i]);
			}
			
			maxTillNow = Math.max(maxTillNow, input[i]);
			
		}
		
		int[] returnVal = new int[result.size()];
		int idx = 0;
		for(int r : result){
			returnVal[idx]=r;
			idx++;
		}
		
		return returnVal;
		
	}

public int getSecondMin(Node root){
		
		if(root != null && root.left !=null){
			if(root.left.val == root.val){
				return Math.min(root.right.val, getSecondMin(root.left));
			}else{
				return Math.min(root.left.val, getSecondMin(root.right));
			}
		}else{
			return Integer.MAX_VALUE;
		}
		 
		
	}

public int rearrangeArray(int [] array){
		
		int tempZeroIdx = array.length-1;
		int count = 0;
		for(int i=array.length-1;i>=0;i-- ){
			if(array[i] == 0){
				if(tempZeroIdx != i){
					swap(array,i,tempZeroIdx);					
				}
				tempZeroIdx--;
				count++;
			}
		}
		
		return count;
	}
	
	private void swap(int[] array, int a,int b){
		int temp = array[a];
		array[a]=array[b];
		array[b]=temp;
	}

public int getMaxVolume(int[] heights){
		
		int max = 0;
		for(int i=0;i<heights.length-1;i++){
			for(int j=i+2;j<heights.length;j++){
				int w = j-i-1; 
				int l = Math.min(heights[i], heights[j]);
				max= Math.max(max, w*l);
				
			}
		}
		
		return max;
	}

Solution using java built in Stack class

import java.util.Stack;

public class MinStack {
	
	private Stack<Integer> stack;
	private Stack<Integer> minStack;
	
	
	public MinStack(){
		stack = new Stack<Integer>();
		minStack = new Stack<Integer>();
	}
	
	
	public void push(int value){
		if(stack.isEmpty()){
			stack.push(value);
			minStack.push(value);
		}else{
			stack.push(value);
			minStack.push(Math.min(value, minStack.peek()));
		}
		
	}
	
	public Integer pop(){
		minStack.pop();
		return stack.pop();
	}
	
	public Integer getMinValue(){
		return minStack.peek();
	}

}

Iterate through the array and check keep calculating the running sum by adding the current value.
If the running sum is greater than the maxSum then update the maxSum and after that if the current value is greater than maxSum then update maxSum and running sum as current value.
Special handling of all negative values. If all negative check if maxSum is < currentvalue and update the maxSum and running sum.

int getMaxSum(int [] array){
		
		int maxSum=array[0];
		int startIdx =0;
		int endIdx = 0;
		int runningSum = maxSum;
		boolean allNegative = false;
		if(maxSum<0){
			allNegative = true;
		}
		for(int i=1;i<array.length;i++){
			allNegative = allNegative && (array[i]<0);
			if(!allNegative){
				runningSum+=array[i];
				if(runningSum > maxSum){
					maxSum = runningSum;
					endIdx = i;
					if(array[i]>maxSum){
						startIdx=i;
						endIdx=i;
						maxSum=array[i];
						runningSum=array[i];
					}
				}
			}else{
				if(maxSum < array[i]){
					maxSum = array[i];
					runningSum = array[i];
					startIdx=i;
					endIdx=i;
				}
			}
			
		}
		
		System.out.println("Max Sum::" + maxSum);
		System.out.println("Start Idx ::" + startIdx + "  End Inx :: " + endIdx);
		return maxSum;
	}

void sortAlternate(int [] ip){
		
		int index=0;
		boolean max=true;
		int tempIndex =0;
		while(index<ip.length-1){
			for(int i=index;i<ip.length;i++){
				if(max){
					if(ip[i]>ip[tempIndex]){
						tempIndex=i;
					}
				}else{
					if(ip[i]<ip[tempIndex]){
						tempIndex=i;
					}
				}
				
			}
			swap(ip,tempIndex,index);
			index++;
			max=!max;
		}
		
		
	}
	
	void swap(int[] ip, int a,int b){
		int temp = ip[a];
		ip[a]=ip[b];
		ip[b]=temp;
	}

Iterate through all the tasks and for each task:
1) If the no of units > the total no of servers return false;
2) Else try and allocate the units to servers 1 at a time and while doing so if we run out of servers then return false.

public class ServerTask {
	
	public static void main(String [] args){
		
		Server s1 = new Server(4);
		Server s2 = new Server(3);
		Server s3 = new Server(2);
		Server s4 = new Server(1);
		
		Server [] servers = {s1,s2,s3,s4};
		
		Task t1 = new Task(4);
		Task t2 = new Task(2);
		Task t3 = new Task(3);
		
		Task[] tasks = {t1,t2,t3};
		
		System.out.println(new ServerTask().canRunTasks(servers, tasks));
		
		
	}
	
	boolean canRunTasks(Server[] servers, Task[] tasks){
		boolean canRun = true;
		
		for(Task task : tasks){
			int noOfUnits = task.totalUnits;
			if(canRun){
				//If the total no of units in a particular task is more than the total no of servers 
				//then the condition of 2 units of the same task cannot run on same server cannot be met.
				if(noOfUnits>servers.length){
					canRun=false;
					break;
				}else{
					int idx =0;
					//Try and allocate the units in the task in 1 server at a time till all the units in the task are allocated.
					while(noOfUnits>0){			
						
						if(servers[idx].allocateSlot()){
							idx++;
							noOfUnits--;
						}else if(idx<servers.length-1){
							idx++;
						}
						else{//If we cannot find a server to allocate then break
							canRun=false;
							break;
						}
					}
						
					
				}
			}else{
				break;
			}
		}
		
		return canRun;
	}

}

class Server{
	int totalSlots;
	int openSlots;
	
	Server(int totalSlots){
		this.totalSlots=totalSlots;
		this.openSlots=totalSlots;
	}
	
	public boolean allocateSlot(){
		if(openSlots>0){
			openSlots--;
			return true;
		}else{
			return false;
		}
		
	}
}

class Task{
	int totalUnits;
	
	Task(int totalUnits){
		this.totalUnits=totalUnits;
	}
}

Visit each node and replace its value with the sum of node values to the right of it.

public class Solution {
	
	
	public void replaceInPlaceWithValuesGreaterThanSelf(TreeNode root){
		if(root == null)
			return;
		replaceWithSumOfNodesGreaterThanitself(root.left);
		replaceWithSumOfNodesGreaterThanitself(root);
		replaceWithSumOfNodesGreaterThanitself(root.right);
		
	}
	
	
	private TreeNode replaceWithSumOfNodesGreaterThanitself(TreeNode root){
		
		
		if(root.right==null)
			return root;
		
		root.data=sumOfChilds(root.right);
		
		return root;
	}
	
	
	
	private int sumOfChilds(TreeNode root){
		
		if(root == null)
			return 0;			
		return root.data+sumOfChilds(root.left)+sumOfChilds(root.right);
	
	}
	
	

}

class TreeNode{
	int data;
	TreeNode left;
	TreeNode right;
	public TreeNode(int data){
		this.data = data;
		this.left = null;
		this.right =null;
	}
}

Iterate through the list and find the max profit with one transaction.
Remember the index of buy and sell index for the max profit and then recursively calculate the profit with the sub array for values before the sell index and after the sell index.

private int getMaxProfit(int[] prices, int fee){
			
			int maxProfit = 0;
			int minPrice = prices[0];
			int minIndex = 0;
			int sellIndex = 0;
			int buyIndex = 0;
			for(int i=1;i<prices.length;i++){
				
				if(prices[i]<minPrice){
					minPrice = prices[i];
					minIndex =i;
				}else{
					if(prices[i]-minPrice-fee > maxProfit){
						maxProfit = prices[i]-minPrice - fee;
						buyIndex = minIndex;
						sellIndex=i;
					}
				}
			}
			
			if(buyIndex<prices.length-1){
				int[] newArray = Arrays.copyOfRange(prices, 0, buyIndex);
				if(newArray.length>1)
					maxProfit+=getMaxProfit(newArray, fee);
			}
			if(sellIndex!=prices.length-1){
				int[] newArray1 = Arrays.copyOfRange(prices, sellIndex+1, prices.length);
				if(newArray1.length>1)
					maxProfit+=getMaxProfit(newArray1, fee);
			}
			return maxProfit;
		}

class NtheLargest{
	
	int findNthLargest(int [] input, int n){
		int [] nLargestNumbers = new int[n];
		//Assume that the first n elements are the largest n numbers
		for(int i=0;i<n;i++){
			nLargestNumbers[i] = input[i];
		}
		//Starting from the n+1 elements update the nLargestNumbers if we find any value greater		
		for(int j=n-1;j<input.lenght;j++){
			for(k=0;k<nLargestNumbers.length;k++){
				if(input[j] > nLargestNumbers[k]){
					updateNLargest(nLargestNumbers,input[j]);
				}
			}
		}
		
		//Find the min in the nLargest numbers which will the nth Largest number in the array.
		intNthLargestvalue = 0;
		for(int v : nLargestNumbers){
			if(v < intNthLargestvalue)
				intNthLargestvalue = v;
		}
		
		return intNthLargestvalue;
	}
	
	updateNLargest(int [] array, int val){
		for(int a:array){
			if(val > a) {
				tmp = array[i];
				array[i] = val;
				updateNLargest(array,tmp);
			}
		}
	}
}