Microsoft Interview Question
SDE1sCountry: United States
@i059069:
You are using: Queue1, Queue2 and tempQueue ??
There is no tempQueue in question !!!
@Srigopal Chitrapu:
I am not talking about his code. I am talking about his extended version where he is saying to use queue1, queue2 and tempQueue
extracting his sentence:
"use the second queue and the tempQueue to process elements for Queue1"
Time complexity : O((n1 + n2)^2) worst case, but for random input will be O(nlog(n)).
First off, I should say that I believe O(nlog(n)) for worst does not seem to be likely to exist. The Quicksort algorithm, which is in-place sorting, needs O(1) swapping between elements which we cannot do here. Nonetheless, It is just a guess.
I show the algorithm with an example. The attach the java code.
Lets assume Q1: [1 4 3 2] and Q2: [8 6 5 7] are the two queues where the
left most is head of line. I just show the steps
1- (dequeue Q2 into Q1)
Q1:[1 4 3 2 8 6 7 5] Q: [] (nQ2inQ1 = 4, nQ1inQ1 = 4)
2- Dequeue the first the head of line in Q1 into Q2.
Q1:[4 3 2 8 6 7 5] Q2:[1] (nQ1inQ1 = 3)
3- Dequeue all the elements from Q1. If it is larger than the last element
entering Q2, enqueue into Q2, otherwise, enqueue into Q1.
Q1:[3 2 8 6 7 5] Q2:[1 4] nQ1inQ1 = 3, nQ2inQ1 = 4, nQ1inQ2 = 2,
last_entered_Q2 = 4
Q1:[2 8 6 7 5 3] Q2:[1 4] nQ1inQ1 = 3, nQ2inQ1 = 4, nQ1inQ2 = 2,
last_entered_Q2 = 4
Q1:[8 6 7 5 3 2] Q2:[1 4].
4- Dequeue Q2 into Q1.
Q1:[8 6 7 5 3 2 1 4] Q2:[] nQ2inQ1 = 4, nQ1inQ1 = 4.
5- Repeat the process again for elements of Q2. You eventually get:
Q1[3 2 1 4 6 7 5 8] Q2:[]
6- Again doing it for elements of Q1. We get at the end
Q1[6 7 5 8 2 1 3 4] Q2:[]
7- Again (for Q2)
Q1[2 1 3 4 5 6 7 8] Q:[] (note that Q2 is sorted now)
8- Again (for Q1)
Q1:[5 6 7 8 1 2 3 4] Q:[]
9- In this round, we realize that Q2 is sorted. (no inversions)
10- In the next step, we find that Q1 is also sorted.
public class TwoQueueSorting {
public static void Sort(Queue<Integer> source, Queue<Integer> destination) {
// The following are state variables, not containers
int len_src = source.size();
int len_dest = destination.size();
int last_to_move_to_destination;
int n_queues_sorted = 0;
boolean working_on_source = true;
while (n_queues_sorted < 2) {
// Move everything to source
while (!destination.isEmpty())
source.add(destination.poll());
// Read from source.
last_to_move_to_destination = source.poll();
destination.add(last_to_move_to_destination);
boolean sorted = true;
int n_out = len_src - 1;
if (!working_on_source)
n_out = len_dest - 1;
for (int i = 0; i < n_out; i++) {
int new_out = source.poll();
if (new_out > last_to_move_to_destination) {
last_to_move_to_destination = new_out;
destination.add(new_out);
} else {
sorted = false;
source.add(new_out); // Not in order and has to return.
}
}
// Change the order for the next round, if it happens
working_on_source = !working_on_source;
if (sorted)
n_queues_sorted++;
}
}
}
Sample:
public class CareerCup {
public static void main(String[] args) {
int[] src = {10, 3, 5, 2, 8, 4};
int[] dst = {9, 3, 4, 1, 2, 12, 33, 98, 20};
ArrayDeque<Integer> source = new ArrayDeque<Integer>();
ArrayDeque<Integer> destination = new ArrayDeque<Integer>();
for (int i = 0; i < src.length; i++)
source.add(src[i]);
for (int i = 0; i < dst.length; i++)
destination.add(dst[i]);
TwoQueueSorting.Sort(source, destination);
System.out.print("Source:\n");
while(!source.isEmpty())
System.out.print(source.poll().toString() + " ");
System.out.print("\n");
System.out.print("destination:\n");
while(!destination.isEmpty())
System.out.print(destination.poll().toString() + " ");
System.out.print("\n");
}
}
run:
Source:
2 3 4 5 8 10
destination:
1 2 3 4 9 12 20 33 98
Suppose we have two queues as an array q[], we can do the following steps to sort them in order:
(1)Keep dequeuing q[0] and enqueue them into q[1], till q[0] is empty and q[1] has all the items.
>>> Now q[0] is empty and q[1] has all the items.
(2)Dequeue all items in q[1] and enqueue them into q[0], at the same time record how many items there are and the minimum item's position in the queue, let's say the there are N items in total, and the minimum is the Kth item in the queue now.
>>> Now q[0] has all the items and the minimum is the Kth item.
(3)Dequeue q[0] K-1 times and enqueue them into q[1], so that we have the minimum item in front of q[0]. Move all items in q[1] to q[0]. And then dequeue q[0] and enqueue it back.
>>> Now q[0] has all the items and the minimum is in the end.
(4)As for the second minimum item, just like repeating step 2 and step 3, but this time we only need to dequeue q[0] N-1 times at most to find out the second minimum item's position, because we already know the minimum is in the end! Then we can let the second minimum be the end of the queue, while the minimum is just in front of it.
>>> Now q[0] has all the items and the two minimums are in the end and in order.
(5)Repeat the procedure as stated above till the largest item is in the end of the queue and then the sorting is done.
this will sort data of 2 queues into single queue.
I guess question says to sort queues data in that queue itself...
We can do within queue with little modification in your algo..
1) mark end of every queue with a marker...
2) process data of one queue in one iteration and keep data from 2nd queue just as it is in queue
3) Q2 sorted data will go into Q1 in one iteration
4) Repeat above with queue reversal
5) Now, Q1 sorted data will go into Q2
6) swap Queue's data
Algo below
public Queue<Integer> sort(Queue<Integer> a, Queue<Integer> b){
if (a.isEmpty()&&b.isEmpty()){
return null;
}
//clear a queue
while (!a.isEmpty()){
b.add(a.poll());
}
//count total number and clear b queue
int i = 0;
while(!b.isEmpty()){
a.add(b.poll());
i++;
}
//add one element to b queue
b.add(a.poll());
// i-j is the size of b queue
int j = i-1;
while (j>0){
// if a head <= b head, add a head before b head
if (a.peek()<=b.peek()){
b.add(a.poll());
for (int x =i-j; x>0; x--){
b.add(b.poll());
}
}
else{
// move b head find the b head which is bigger than a head.
int x = i-j;
while(a.peek()>b.peek()){
if(x==0)
break;
b.add(b.poll());
x--;
}
// add a head to b queue
b.add(a.peek());
// move b head back to increasing order
while(x>0){
b.add(b.poll());
x--;
}
//delete a head
a.remove();
}
j--;
}
return b;
}
QueueSort (queue Q1, queue Q2)
{
Q1 end marker: q1_end
Q2 end marker: q2_end
Q2.enqueue (q2_end);
//Push all data from Q1 to Q2
while ( !Q1.empty() )
{
Q2.enqueue (Q1.dequeue() );
}
//put end marker for Q1's data
Q2.enqueue (q1_end);
//sort Q2's data into Q1
while (1)
{
small = e = Q2.dequeue ();
//process till Q2's end marker is not reached
while (e != q2endmarker() )
{
//remember smallest element and keep enqueuing rest of Q2 element in Q2 itself
e = Q2.dequeue();
if (e < small)
{
Q2.enqueue (small)
small = e
}
else
Q2.enqueue (e)
}
//again mark queue end
Q2.enqueue (q2_end)
//put smallest Q2's element in Q1
Q1.enqueue (small)
//Simply Dequeue and enqueue back Q1's all element into Q2
e = Q2.dequeue()
while (e != q1endmarker()) )
{
Q2.enqueue (e)
e = Q2.dequeue ()
}
//again mark queue end
Q2.enqueue (q1_end)
}
remove q1_end and q2_end from Q2
}
//after this function, Q2 is sorted in Q1
Function (Queue Q1, Queue Q2)
{
QueueSort (Q1, Q2);
QueueSort (Q2, Q1);
//Swap elements of both queue's. Function not implemented
swapQueue (Q1, Q2);
}
Copied from reply section in this post itself
We can do within queue with little modification in your algo..
1) mark end of every queue with a marker...
2) process data of one queue in one iteration and keep data from 2nd queue just as it is in queue
3) Q2 sorted data will go into Q1 in one iteration
4) Repeat above with queue reversal
5) Now, Q1 sorted data will go into Q2
6) swap Queue's data
Assume that we moved all elements from Queue2 to Queue1. Then perform the below steps.
1. Store the 'Queue1' count and peek 'Queue1' element and store it in 'queue1InitialTempElement'.
2. Repeat a loop till a flag 'IsSorted' becomes true.
3. Once enterted in loop dequeue element from the 'Queue1' and store it in 'queue1DequedElement'.
4. if 'queue1InitialTempElement' is grater than or equals to 'queue1DequedElement'.
4.1. Then store 'queue1DequedElement' value in 'queue1InitialTempElement'.
4.2. And enqueue 'queue1InitialTempElement' value in to 'Queue2'.
5. Else store 'queue1DequedElement' back to 'Queue1'.
6. Increment the 'lpCntProcessedElemnts' and check it if it is equals 'Queue1' length.
6.1. If they are not equal then continue the loop.
7. If the Queue2. Count is equals to 'Queue1' length.
7.1. If they are equal then make 'IsSorted' flag as true.
8. Reset 'lpCntProcessedElemnts' to zero.
9. Repeat loop till 'Queue2' Count is grater than zero and dequeue all elements from 'Queue2' and enqueue then to 'Queue1'.
10. Peek 'Queue1' element and store it in 'queue1InitialTempElement'.
11. End the loop of 'IsSorted' flag.
partial class QueueOperations
{
public void SortElementsUsing2Queues()
{
Queue<int> queue1 = new Queue<int>();
Queue<int> queue2 = new Queue<int>();
queue1.Enqueue(3);
queue1.Enqueue(2);
queue1.Enqueue(1);
queue1.Enqueue(6);
queue1.Enqueue(5);
queue1.Enqueue(4);
queue1.Enqueue(8);
queue1.Enqueue(10);
queue1.Enqueue(9);
queue1.Enqueue(7);
int queue1OriginalLength = queue1.Count;
int queue1DequedElement = 0;
int queue1InitialTempElement = queue1.Peek();
int lpCntProcessedElemnts = 0;
bool isQueueSorted = false;
while (isQueueSorted == false)
{
queue1DequedElement = queue1.Dequeue();
// If the queue1Element is less than or equals to the item on the top of the sorted queue, then push it queue2 else push it back to the bottom of queue1.
if (queue1InitialTempElement >= queue1DequedElement)
{
queue1InitialTempElement = queue1DequedElement;
queue2.Enqueue(queue1DequedElement);
}
else
{
queue1.Enqueue(queue1DequedElement);
}
// Continue if we still have items to process. Note Queue1 lenght will be changed based on partial elements sorted.
if (++lpCntProcessedElemnts != queue1OriginalLength)
{
continue;
}
lpCntProcessedElemnts = 0;
// If Queue2 length is equals to Queue1Lenght then queue is sorted.
if (queue2.Count == queue1OriginalLength)
{
isQueueSorted = true;
break;
}
// Queue2 will have partially sorted elements so push them back to queue1 to process them again.
while (queue2.Count > 0 )
{
queue1.Enqueue(queue2.Dequeue());
}
// Reset back the topSortedElement.
queue1InitialTempElement = queue1.Peek();
}
StringBuilder StringBuilderObj = new StringBuilder();
StringBuilderObj.Append("Sorted Elements from the Queue:\n");
while (queue2.Count > 0)
{
int queueElement = queue2.Dequeue();
queue1.Enqueue(queueElement);
StringBuilderObj.Append("\t" + queueElement);
}
//Queue2 will have sorted elements.
MessageBox.Show(StringBuilderObj.ToString());
}
}
this is just a extended version of "sort a queue with the help of an other queue."
First give the solution of "sort a queue with the help of an other queue", the idea here is if the item at the head of the target queue (first queue) is smaller than the item has been dequeued and pushed to the temp queue (second queue) , we dequeue the item from target queue and push it to the temp queue, otherwise dequeue it from target and enqueue it back to the target, process until we have worked thru all the elements, if all the elements are in the tmp queue (second queue) means the sort is done, otherwise redo the process until the sort is done .
Code as below -
To extend the solution to two queues and both with elements to be sorted, simply dump all the elements from queue 2 to queue 1, use the second queue and the tempQueue to process elements for Queue1, once all Queue 1 elements processed, use queue1 as the temp queue to process all elements in queue 2. Until all the elements in both queues sorted.
- i059069 January 15, 2014