CareerCup

What is missing are the constraints that array contains only unique numbers in range 0.. n-1. This make the problem very ease. Here is implementation with O(n) time complexity

void swap (int i, int j, int[] arr) {
	   char ch = arr[i];
	   arr[i] = arr[j];
	   arr[j] = ch;
   }
void swap (int i, int j, char[] arr) {
	   char ch = arr[i];
	   arr[i] = arr[j];
	   arr[j] = ch;
   }
   
   void permutate(int[] pos, char[] chars) {
	   int index = 0; 
	   while (index < chars.length) {
		   if(index != pos[index]) {			   
			   swap(index,pos[index],chars);
			   swap(index,pos[index],pos);
		   }
		   else {
			   index++;
		   }
	   }
   }

The constraints are the things that one should ask the interviewer.

ArrayList<Integer> arr1 = new ArrayList<Integer>();
		arr1.add(4);
		arr1.add(3);
		arr1.add(2);
		arr1.add(0);
		arr1.add(1);
		
		ArrayList<String> arr2 = new ArrayList<String>();
		arr2.add("E");
		arr2.add("D");
		arr2.add("C");
		arr2.add("A");
		arr2.add("B");
		
		Collections.sort(arr1);
		Collections.sort(arr2);
		
		System.out.println("ARR1: "+arr1.toString());
		System.out.println("ARR2: "+arr2.toString());

public static ArrayList<Integer> sortUpDownArray(ArrayList<Integer> A) {
		ArrayList<Queue<Integer>> sortedSubArrays = new ArrayList<Queue<Integer>>();
		// True for increasing and false for decreasing
		boolean isIncreasing = true;
		int start = 0;
		for (int i = 1; i <= A.size(); ++i) {
			if (i == A.size()
					|| // array is ended. Add the last subarray.
					A.get(i - 1) < A.get(i) && !isIncreasing
					|| A.get(i - 1) >= A.get(i) && isIncreasing) {
				if (isIncreasing) {
					Queue<Integer> sub = new PriorityQueue<Integer>();
					sub.addAll(A.subList(start, i - 1));
					sortedSubArrays.add(sub);
				} else {
					Queue<Integer> queue = new PriorityQueue<Integer>();
					queue.addAll(A.subList(start - 1, i));
					sortedSubArrays.add(queue);
				}
				start = i;
				isIncreasing = (isIncreasing ? false : true);
			}
		}
		return MergeSortedArrays(sortedSubArrays);
	}

	private static ArrayList<Integer> MergeSortedArrays(
			ArrayList<Queue<Integer>> listOfQueues) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		PriorityQueue<Integer> priQue = new PriorityQueue<Integer>(
				listOfQueues.size());
		for (Queue<Integer> aQueue : listOfQueues) {
			if (aQueue.size() > 0)
				priQue.add(aQueue.peek());
		}
		while (!priQue.isEmpty()) {
			Integer poppedItem = priQue.remove();
			result.add(poppedItem);
			for (Queue<Integer> queue : listOfQueues) {
				if (queue.contains(poppedItem)) {
					queue.poll();
					if (!queue.isEmpty())
						priQue.add(queue.peek());
					break;
				}
			}
		}
		return result;
	}

public static ArrayList<Integer> sortUpDownArray(ArrayList<Integer> A) {
		ArrayList<Queue<Integer>> sortedSubArrays = new ArrayList<Queue<Integer>>();
		// True for increasing and false for decreasing
		boolean isIncreasing = true;
		int start = 0;
		for (int i = 1; i <= A.size(); ++i) {
			if (i == A.size()
					|| // array is ended. Add the last subarray.
					A.get(i - 1) < A.get(i) && !isIncreasing
					|| A.get(i - 1) >= A.get(i) && isIncreasing) {
				if (isIncreasing) {
					Queue<Integer> sub = new PriorityQueue<Integer>();
					sub.addAll(A.subList(start, i - 1));
					sortedSubArrays.add(sub);
				} else {
					Queue<Integer> queue = new PriorityQueue<Integer>();
					queue.addAll(A.subList(start - 1, i));
					sortedSubArrays.add(queue);
				}
				start = i;
				isIncreasing = (isIncreasing ? false : true);
			}
		}
		return MergeSortedArrays(sortedSubArrays);
	}

	private static ArrayList<Integer> MergeSortedArrays(
			ArrayList<Queue<Integer>> listOfQueues) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		PriorityQueue<Integer> priQue = new PriorityQueue<Integer>(
				listOfQueues.size());
		for (Queue<Integer> aQueue : listOfQueues) {
			if (aQueue.size() > 0)
				priQue.add(aQueue.peek());
		}
		while (!priQue.isEmpty()) {
			Integer poppedItem = priQue.remove();
			result.add(poppedItem);
			for (Queue<Integer> queue : listOfQueues) {
				if (queue.contains(poppedItem)) {
					queue.poll();
					if (!queue.isEmpty())
						priQue.add(queue.peek());
					break;
				}
			}
		}
		return result;
	}

we sort second array by comparing ascii values so both implementation will exactly be same except second one needs a cast like (int)B[i].

Question should be to interviewer if second array has all caps and whats expected result if its not.