So basically, Im asked to sort a queue, and i can only use one helper queue , and am only allowed constant amount of additional memory.
How would i sort a queue using only one additional queue ?
7
-
Did you try anything yet? if so , please post itIndieTech Solutions– IndieTech Solutions2015-03-03 02:15:40 +00:00Commented Mar 3, 2015 at 2:15
-
I have not, not really sure how to start… ??user4625838– user46258382015-03-03 02:16:44 +00:00Commented Mar 3, 2015 at 2:16
-
what language are you using? is this a homework?IndieTech Solutions– IndieTech Solutions2015-03-03 02:18:54 +00:00Commented Mar 3, 2015 at 2:18
-
No, this was for a job interview and i didnt get it right, just wondering what the right answer was.user4625838– user46258382015-03-03 02:22:09 +00:00Commented Mar 3, 2015 at 2:22
-
You will need to follow a recursive approach. have a look at this : gist.github.com/abhishekcghosh/049b50b22e92fefc5124IndieTech Solutions– IndieTech Solutions2015-03-03 02:28:22 +00:00Commented Mar 3, 2015 at 2:28
|
Show 2 more comments
1 Answer
Personally, I don't like interview questions with arbitrary restrictions like this, unless it actually reflects the conditions you have to work with at the company. I don't think it actually finds qualified candidates or rather, I don't think it accurately eliminates unqualified ones. When I did technical interviews for my company, all of the questions were realistic and relevant. Setting that aside.
While there are surely several ways to solve this, and using recursion is certainly one, I would hope that if you tried to solve it with recursion they would have asked you to do it over without recursion, considering they are placing limits on the memory you can use and the data structures. Otherwise, they might as well as given you two queues, a stack and as much memory as you want.
Here is an example of one way to solve it. At the end of this, queueB should be sorted. It uses just one extra local variable. This was done in C#.
queueB.Enqueue(queueA.Dequeue());
while (queueA.Count > 0)
{
int next = queueA.Dequeue();
for (int i = 0; i < queueB.Count; ++i)
{
if (queueB.Peek() < next)
{
queueB.Enqueue(queueB.Dequeue());
}
else
{
queueB.Enqueue(next);
next = queueB.Dequeue();
}
}
queueB.Enqueue(next);
}
