JP Morgan Interview Question
fresherssCountry: United States
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;
}
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
- EPavlova January 17, 2016