Microsoft Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

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 -

/// <summary>
        /// function to sort a queue using an extra queue. 
        /// </summary>
        /// <param name="target">the target queue that contains all the unsorted elements</param>
        private static void SortQueueUsingExtraQueue(Queue<int> target)
        {
            if (target == null || target.Count < 2) return;

            var tmpQueue = new Queue<int>(); // the second Queue, this queue contains the sorted part of the target queue.
            var queueLength = target.Count; // length of the target queue. 
            var lastInput = target.Peek(); // element at the top of the "sorted" queue.
            var processedCount = 0; // currently processed item count. 
            bool sorted = false;

            while (!sorted)
            {
                // if the element element is lesser than the item on the top of the sorted queue, we move it from the target queue and push it into the sorted queue. 
                if (lastInput >= target.Peek())
                {
                    lastInput = target.Dequeue();
                    tmpQueue.Enqueue(lastInput);
                }
                
                // the poping element is bigger than the top element on the sorted queue, we put it back to the bottom of the queue and will process it later. 
                else
                {
                    target.Enqueue(target.Dequeue());
                }
                
                // continue if we still have item to process. 
                if (++processedCount != queueLength) continue;

                // once all item are processed, we check the length of the sorted queue, if the # of item equals the length of the orignal queue, means the sort is done. 
                if (tmpQueue.Count == queueLength)
                {
                    sorted = true;
                }

                // we dump all the elements to the target queue, if the sort is done, target queue ends up with all the element sorted, if not, target queue ends with element that is parcially sorted.
                // We will process on until all the elements are sorted. 
                while (tmpQueue.Count > 0)
                {
                    target.Enqueue(tmpQueue.Dequeue());
                    lastInput = target.Peek(); // don't forget to reset lastInput.
                }

                processedCount = 0;
            }

        }

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 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@i059069:
You are using: Queue1, Queue2 and tempQueue ??
There is no tempQueue in question !!!

- SK January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No Saurabh, he used only 2 Queues i.e. target and temp queue only.
Go through his code.

- Srigopal Chitrapu January 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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"

- SK January 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code is wrong (even sorting 1 queue with help of another queue). Test case: 4/9/5/11/8/3/2/7 , front of queue is 7.

- anonymous February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Ehsan January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- uuuouou January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SK January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- soysauce January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess he still what to keep the elements in their original queues .So I don't think your solution applies.

- i059069 January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Merge the two queues.

2. Sort it using Insertion sort technique.

- Anonymous January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- SK January 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SK January 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
    }
}

- Srigopal Chitrapu January 29, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More