Discussion: using two stacks to implement a queue of me as an interviewer summary
- 2020-04-02 00:57:50
- OfStack
Two years ago, I saw an interview question from the Internet: implement a Queue with two stacks. Feel good, often take the interview, a few years down, do this problem should have dozens of people. Here is a summary of some of the statistics and feelings about the performance and reactions of the interviewees.
Described in C++, the title looks something like this:
Given the following Stack class and its three methods Push, Pop and Count, please use two stacks to implement the Enqueue and Dequeue method of the Queue class.
This question should not be difficult, compared to the beauty of programming in the Microsoft "turn the pancake" of the interview questions, the difficulty is far from. Moreover, due to time constraints, I generally do not ask candidates to write code, only to describe clear ideas. In this case, we mainly investigate three points:
1. Can you find a clear enough way to solve the problem in a short time?
2. Can you clearly describe your own thoughts and thoughts in one-way presentation (whether the presentation ability meets the requirements)?
3. Is it possible to consider certain specific details?
Overall, taking 10 people as an example, the actual result is roughly:
1.8 people can find the answer, 2 people can't find the answer (even after giving the necessary hints, one brother who claimed to study in MIT for 2 years and then worked at Google America for 8 months did not).
Of the 2.8 people who found the answer, six found it the same way, and two found other variants.
3. One of these eight people can think of both popular methods and variations without being prompted.
The idea for most people is to always maintain s1 as storage space and s2 as a temporary buffer.
When you join the team, press the element into s1.
When leaving the queue, "pour" the elements of s1 into s2 one by one (pop up and press in), pop up the top element of s2 as the outgoing element, and then "reverse" the remaining elements of s2 back to s1 one by one.
See the following schematic diagram:
Some variations of the above ideas include:
When entering the team, first determine whether s1 is empty. If not, it means that all elements are in s1. At this time, enter the team element directly into s1. If it is empty, the elements of s2 should be "reversed" to s1 one by one and then pressed into the queue elements.
When leaving the queue, first determine whether s2 is empty. If not, directly pop out the top element of s2 and leave the queue. If it is empty, "pour" the elements of s1 into s2 one by one, and pop the last element out of the queue.
Some people can think of both the popular method and the variety, it should be said that the brain is relatively clever.
Compared with the first method, the variant s2 seems to be more "lazy". After each team exit, the elements are not "reversed" to s1. If we still leave the team next time, the efficiency will be higher. I sometimes ask candidates to analyze and compare the performance of different methods. I feel that (without further research), the time complexity and space complexity of the above two methods should be the same in general (no more than a few judgments) when the entry and exit operations are randomly distributed.
The really high performance is actually another variant. That is:
When you join the team, press the element into s1.
When out of the queue, determine whether s2 is empty. If not, the top element will pop up directly. If it is empty, "pour" the elements of s1 into s2 one by one, and pop the last element out of the queue.
This idea avoids the repeated "down" stack, only "down" once when needed. But in the actual interview few people say, may be less time.
At first glance, the above ideas seem to be all right, but there is a detail to consider. Regardless of the method and the situation, it is important to consider what to do when there are no elements available to queue (when two stacks are empty, the queue operation must cause an exception). Ignoring these judgments or exception handling when actually writing code can cause problems. So, can consider these details, also reflects the personal quality.
Personally, this question really helps me to identify the candidates. But for the interview, after all, still want to see the comprehensive quality of the interviewer, a (or a few) problem is not desirable.
Described in C++, the title looks something like this:
Given the following Stack class and its three methods Push, Pop and Count, please use two stacks to implement the Enqueue and Dequeue method of the Queue class.
class Stack
{
...
public:
void Push(int x); // Push an element in stack;
int Pop(); // Pop an element out of stack;
int Count() const; // Return the number of the elements in stack;
...
};
class Queue
{
...
public:
void Enqueue(int x);
int Dequeue();
private:
Stack s1;
Stack s2;
...
};
This question should not be difficult, compared to the beauty of programming in the Microsoft "turn the pancake" of the interview questions, the difficulty is far from. Moreover, due to time constraints, I generally do not ask candidates to write code, only to describe clear ideas. In this case, we mainly investigate three points:
1. Can you find a clear enough way to solve the problem in a short time?
2. Can you clearly describe your own thoughts and thoughts in one-way presentation (whether the presentation ability meets the requirements)?
3. Is it possible to consider certain specific details?
Overall, taking 10 people as an example, the actual result is roughly:
1.8 people can find the answer, 2 people can't find the answer (even after giving the necessary hints, one brother who claimed to study in MIT for 2 years and then worked at Google America for 8 months did not).
Of the 2.8 people who found the answer, six found it the same way, and two found other variants.
3. One of these eight people can think of both popular methods and variations without being prompted.
The idea for most people is to always maintain s1 as storage space and s2 as a temporary buffer.
When you join the team, press the element into s1.
When leaving the queue, "pour" the elements of s1 into s2 one by one (pop up and press in), pop up the top element of s2 as the outgoing element, and then "reverse" the remaining elements of s2 back to s1 one by one.
See the following schematic diagram:
< img style = "border = 0 BACKGROUND - IMAGE: none; BORDER - BOTTOM: 0 px; BORDER - LEFT: 0 px; PADDING - LEFT: 0 px; PADDING - RIGHT: 0 px; DISPLAY: inline. BORDER - TOP: 0 px; BORDER - RIGHT: 0 px; PADDING - TOP: 0 px "title = 2 stacks1queue border = 0 Alt = 2 stacks1queue SRC =" / / files.jb51.net/file_images/article/201305/201305291459392.jpg "width = 640 height = 233 >
Above train of thought, feasibility is undoubted. But there is one detail that can be optimized. That is, when the elements of s1 are "poured" into s2 one by one during queue exit, the original elements at the bottom of s1 stack can be directly popped back as queue elements without "pouring" into s2 (i.e., only "pour" s1.count ()-1). This reduces the need for a single push. About half of them, when prompted, were aware of the problem.Some variations of the above ideas include:
When entering the team, first determine whether s1 is empty. If not, it means that all elements are in s1. At this time, enter the team element directly into s1. If it is empty, the elements of s2 should be "reversed" to s1 one by one and then pressed into the queue elements.
When leaving the queue, first determine whether s2 is empty. If not, directly pop out the top element of s2 and leave the queue. If it is empty, "pour" the elements of s1 into s2 one by one, and pop the last element out of the queue.
Some people can think of both the popular method and the variety, it should be said that the brain is relatively clever.
Compared with the first method, the variant s2 seems to be more "lazy". After each team exit, the elements are not "reversed" to s1. If we still leave the team next time, the efficiency will be higher. I sometimes ask candidates to analyze and compare the performance of different methods. I feel that (without further research), the time complexity and space complexity of the above two methods should be the same in general (no more than a few judgments) when the entry and exit operations are randomly distributed.
The really high performance is actually another variant. That is:
When you join the team, press the element into s1.
When out of the queue, determine whether s2 is empty. If not, the top element will pop up directly. If it is empty, "pour" the elements of s1 into s2 one by one, and pop the last element out of the queue.
This idea avoids the repeated "down" stack, only "down" once when needed. But in the actual interview few people say, may be less time.
At first glance, the above ideas seem to be all right, but there is a detail to consider. Regardless of the method and the situation, it is important to consider what to do when there are no elements available to queue (when two stacks are empty, the queue operation must cause an exception). Ignoring these judgments or exception handling when actually writing code can cause problems. So, can consider these details, also reflects the personal quality.
Personally, this question really helps me to identify the candidates. But for the interview, after all, still want to see the comprehensive quality of the interviewer, a (or a few) problem is not desirable.