CareerCup

O(n) solution

public int[] sortArrays(int[]A, int[]B){
		Hashtable<Integer,Integer>map=new Hashtable<Integer,Integer>();
		for(int i=0;i<A.length;i++){
			map.put(new Integer(A[i]), new Integer(i));
		}
		for(int i=0;i<B.length;i++){
			if(A[i]==B[i]){
				continue;
			}else{
				swap(A,A[i],0,map);
				swap(A,A[i],B[i],map);				
			}
		}
		return A;
		
	}
	private void swap(int[]A, int i, int j, Hashtable<Integer,Integer> map){
		int iIdx=map.get(new Integer(i)).intValue();
		int jIdx=map.get(new Integer(j)).intValue();
		A[iIdx]=j;
		A[jIdx]=i;
		map.put(new Integer(i), new Integer(jIdx));
		map.put(new Integer(j), new Integer(iIdx));
		
		
	}

This is O(n) solution:

public void maxPrefix(int[]a){
	int minSoFar=a[0];
	int currentMin=a[0];
	int maxPrefixSoFar=0;
	int currentMaxPrefix=0;
	for(int i=1; i<a.length; i++){
		if(a[i]>currentMin){
			currentMaxPrefix++;
		}else{
			if(currentMaxPrefix>maxPrefixSoFar){
				maxPrefixSoFar=currentMaxPrefix;
				minSoFar=currentMin;
			}
			if((a.length-i-1)<maxPrefixSoFar){
				break;
			}
			currentMin=a[i];
			currentMaxPrefix=0;
		}		
	}
	if(currentMaxPrefix>maxPrefixSoFar){
		maxPrefixSoFar=currentMaxPrefix;
		minSoFar=currentMin;
	}	
	System.out.println("Element:\t"+minSoFar);
	System.out.println("MaxPrefix:\t"+maxPrefixSoFar);
}

public int balance(int[] a){
	int leftW=a[0];
	int rightW=a[a.length-1];
	int left=0;
	int right=a.length-1;
	while(left<right-1){		
		if(rightW>=leftW){
			left++;
			leftW+=a[left];			
		}else if(rightW<leftW){
			right--;
			rightW+=a[right];
		}	
	}
	return left;
}

public void printMap(HashMap<String,List<String>> manEmp){
	Set<String> keys = manEmp.keySet();
	Set<String>printedKes=new HashSet<String>();
	for(String key: keys){
		if(!printedKes.contains(key)){
			String level ="";
			printedKes.addAll(printNestMap(manEmp,key,level));
		}	
	}			
}

private Set<String> printNestMap(HashMap<String,List<String>>manEmp, String man, String level){
	Set<String>printedKes=new HashSet<String>();
	System.out.println(level+"-"+man);
	if(manEmp.containsKey(man)){
		List<String> nestEmp= manEmp.get(man);
		printedKes.add(man);
		level+=" ";
		for(int i=0;i<nestEmp.size();i++){
			printedKes.addAll(printNestMap(manEmp,nestEmp.get(i),level));
		}			
	}
	return printedKes;

}

public int[][] randMat(int size, int min, int max){
		int[][] retMat=new int[size][size];
		for(int i=0;i<size;i++){
			for(int j=i;j<size;j++){
				int exclude=min-1;			
				if(j>=2 && retMat[i][j-1]==retMat[i][j-2]){
					exclude=retMat[i][j-2];
				}
				retMat[i][j]=getRand(min, max, exclude);
				exclude=min-1;
				if(i>=2 && retMat[i-1][j]==retMat[i-2][j]){
					exclude=retMat[i-1][j];
				}			
				retMat[j][i]=getRand(min, max,exclude);
			}
		}
		return retMat;
	}

	private int getRand(int min, int max, int exclude){
		int[] range= null;
		if(exclude<min ||exclude>max){
			range=new int[max-min+1];
		}else{
			range=new int[max-min];
		}
		int ptr=0;
		for(int i=min; i<=max; i++){
			if(i==exclude)
				continue;
			range[ptr++]=i;
		}
		int rand = ThreadLocalRandom.current().nextInt(1, (range.length) + 1)-1;
		return range[randomNum];
	}