The N problem isn't the name of the problem it's just a name I have for it. The reasoning behind it will become much more clear later down the line.
The problem
The problem is asking can you implement a Queue data structure from 2 stacks!
Quick up to speed on Queues and stacks!
Queues and stacks have advantages and disadvantages like many things in computer science, but this question is more concerned with the behavior of these two data structures rather than what's better for what scenario.
Queues
The behavior I was talking about above is the order in which data comes in and out. In a Queue whatever you put in first you will get the first out. (FIFO for short)
Stacks
Stacks are a bit different although it is still dealing with the order in which data moves around. A stack is first in last out. (FILO for short)
If you are still a bit lost hopefully these analogies will help you. In the country of England if you were waiting for something in an orderly fashion then you would be in a queue. Makes a bit more sense when you think about if you were the first chap in line you would get the first fish and chips(FIFO)! Now with stacks, I think about how cars make it from manufacturing plants to dealerships. Car carriers, those giant trucks that can carry 5-6 cars on the trailer. It is impossible to take the first car that you put on that truck off, so you must take the last one off first (FILO).
Back to the problem
So now that we have a better grasp of the parts, the problem appears. Being quick on your feet is one of your expertise. After all, you are an engineer or at least trying your damnedest to be. So the idea of an array sneaks in your brian thoughts start to bubble. You sigh and pick up the maker to hit the whiteboard (Revision for the year 2020, no whiteboard just your childhood bedroom. Good luck trying to be professional with Mario posters over the wall). As you do that the interviewer, without looking up from his phone says you can't cheat and use arrays you have to use 2 stacks. Annnnnnnddddd we are back to freaking out.
So we have two stacks and those stacks deal with data! At this point I would ask my interviewer for this example could I use a finite set of data. ( Like 3 letters) Just so you could create a diagram for better understanding.
The methods we need
The methods that we need to implement are: add, remove, and peek. We will need these methods because they are properties of a queue.
Just one more thing
Before we get going we need two stacks. We can't make a queue out of two stacks unless we have the stacks themselves.
constructor() {
this.a = new Stack();
this.b = new Stack();
}
The add method
The add method has one purpose. All that this function is doing is taking the data and placing it in the first stack or in this case stack A. No crazy not voodoo yet! Here is what that would look like:
add(record) {
this.a.push(record);
}
The remove method
The remove method is a bit of a step-up at least for me in brainpower. It took me a while for me to understand what was really going on and why we were doing it! Here is how it breaks down. First, we will have a while loop that says "Are there any elements in stack A?" If the answer to that question is yes we would want that value and push that value into stack B. We will keep doing this until all the elements in stack A are pushed into stack B. Following that, we would set a value to the popped element in stack B. Following that, there is another while loop. In this while loop, we would check if there is an element in stack B. If there is then we would push that element back into stack A and return the value that we wanted. The code would look something like this:
remove(){
while (this.a.peek()) {
this.b.push(this.a.pop());
}
const record = this.b.pop();
while (this.b.peek()) {
this.a.push(this.b.pop());
}
return record;
}
The peek method
The peek method is extremely similar with only one difference. The return value instead of being a popped value will be a peeked one.
The code would look something like this:
peek(){
while (this.a.peek()) {
this.b.push(this.a.pop());
}
const record = this.b.peek();
while (this.b.peek()) {
this.a.push(this.b.pop());
}
return record;
}
n?
In this case, I am not referring to big O notation. This might sound crazy but I am actually referring to the letter itself, specifically lower case n.
Pull up the picture and I will tell you what I see. So to break down this even further I would say this problem has two parts. Addition of data to the stack and moving the data from one stack to another. Peek and remove are so similar that I would consider them the same sans that you get in the return from both of them. You would add the data in the top left of the letter. All of the information that you need is in stack A, the first line down. Well then with either peek or remove we would have to move the data to the next stack and back, the arch connecting both lines. Your peek and pop records come out of the same spot that the data came in completing the n.
I hope the weird diagram that I have show gives you a little bit better understanding when you see this problem again!
Thanks, Mike
Oldest comments (0)