This problem was a prompt from the Cracking The Coding Interview book. The exercise is: "Describe how you could use a single array to implement t...
For further actions, you may consider blocking this person and/or reporting abuse
Hi Emma,
First and foremost, thanks a lot for sharing this. It's a cool implementation!
I came up with an alternative implementation, though. Which would allow for any Stack to take as much space as possible. I have not tested it, but I think that the following implementation accomplishes that:
The thing is that normally Stacks are implemented using linked data-structures. So, we could do the same thing here... The idea is to have each Stack to keep a linked list of the indeces that it's using. Then, every time that one of them releases an index, we keep that one in another internal linked-list (
_availableIdxs
) so that we have a way of knowing which indeces are not used... A "drawback" is thatisFull
is common for all of them, of course. There is a bit more overhead, but the time-complexity is still constant for all the operations (push
,peak
andpop
) and the memory usage would be a bit better... Another drawback would be the fact that a Stack can take all the available space, leaving nothing for the others :-)I'm just sharing this, because I thought you could find it interesting. I'm not trying to criticise your work. There is no such thing as a free lunch when it comes to software development, there are prons and cons to both implementations.
Love this thank you!!
Thanks for sharing your solution.
However, as an interviewer, my follow-up question would be, if you can get rid of the second array, as well as the two member variables.
:)
Besides the interview question, why would I want to implement 3 stacks with 1 array?
Honest question.
That is indeed the better question :D
LOL I have no freaking clue. I definitely wouldn't want to IRL. Was just an exercise.
For storing three stacks using one array, you are using an object containing two arrays.
To me a nicer answer would have been to use one array only, maybe using the array as the object itself :
multipleStacksArray.constructor === Array;
multipleStacksArray.pushToStack(stackNumber,value);
Anyways using indexed accesses to the array does not seem to comply to the demand, aka if you replace [] with {} in your class it will still work while not using arrays... Can you do it over using Javascript's native methods Array.push and Array.pop ? I would like to see such a clever implementation.
Yeah, I was a bit disappointed that the total number of arrays was two as well :) I’m on board with “one array” means one array..
It could be achieved by reserving the first n items of the single array to contain the sizes.
Not sure how I feel about using indexed access not complying with the demand. I mean it is an array, so I’m not really getting your point.
Would be thankful if you could elaborate further on your second point.
Well, to me, using indexes is cheating because it is the same as using objects. Since you can access the [topIndex] value you access the [topIndex-1] value : that is in opposition with the concept of stacks (LIFO).
You might as well have objects with named properties (i.e. multipleStacks.stack1.value1) and no array at all.
For the sole purpose of science I would have enjoyed an "only one stack" version where you have to unstack in a temporary stack untill reaching the desired value to access or update (loop of Array.pop then loop of Array.push).
For the sake of fulfilling the use case, for production usage, I would have made one object containing an array per stack (but a multimensional array is cheating as well) and not one object containing two objects.
TL;DR it seems very bad not to use Array.pop nor Array.push in a JavaScript exercice regarding stacks.
Well, I do not understand that complain.
The task was to implement a stack using an array, rather than to implement a stack using a stack.
So from my understanding, using indexed access is perfectly fine.
Doesn't this code override the last element in the stack instead of adding it, as
this.indexOfTop
returns the index of the last element?I’m thinking the same thing… if
indexOfTop
points at the top-most element, then setting that same index to the newvalue
just keeps overwriting that top-most element, no?Edit: I actually tried it the way I thought it should be (adding 1 to the value of
indexOfTop
) and it definitely does not do the right thing (the first element of every stack is empty, so everything is off by 1). And when I removed that code, it worked perfectly.So, now my only question is: How is it working!? How can
indexOfTop
be used to both show the top-most element and to insert a new element?Oh. I see it now 🤦🏻♂️!
It works because of the line immediately preceding that line:
That seems tricky – difficult to come back to later on and immediately understand how those lines work in concert. Perhaps it would be more straight-forward to swap those two lines and add 1 to the
indexOfTop
instead:It is a bit convoluted eh?
Yeah, maybe a little. Not too bad. Once I actually ran the code, I began to understand the cleverness at work.
This was a really fun article to play along with, Emma! Thanks for structuring it the way you did. Being a somewhat seasoned developer, I appreciated the flying overview at the beginning so that I could write up my own version of such a class with all the proper attributes and methods in place. I even took my own first stab at filling in those methods and guessing ahead at how you might fulfill each one’s responsibility. I came really close on a lot of it!
I also really appreciate how you break it down into really simple terms – with visuals! – so that beginners and those of us who appreciate the “why?” behind the “how?” could get a firm grasp on the concepts.
Thank you! 🙏🏼
Hey Emma, that's a nice solution, but wouldn't something like this work as well?
Stack 1 indices: N*3
Stack 2 indices: N*3 + 1
Stack 3 indices: N*3 + 2
So basically you split the array where position 0 is stack 1, 1 is stack 2, 2 is stack 3, 3 is stack 1 again, 4 is stack 2, etc.
This would allow your stacks to have an indefinite max length as well (as you'll never run in a case where a stack needs to take space from another one)
I was thinking the same thing but then you would end up with a sparse array. I guess it's not that big a deal in JS.
Excellent article!
Just one question:
In push method, shouldn't be
this.values[this.indexOfTop(stackNumber) + 1] = value;
instead of
this.values[this.indexOfTop(stackNumber)] = value;
?
Hi Emma,
thanks for your post (and code) on that coding interview question.
In my opinion, the applicant not only needs to know what a stack is, and how it's implemented, but also needs to be able to "flatten" a data structure into a (one-dimensional) range of memory, in that case a simple fixed-size array.
Thus, I modified your code a bit, to get rid of the second array and the member variable
_stackCapacity
.For simplicity, I also removed the support for arbitrary numbers of stacks, as its not requested by the interviewer' question.
Edit:
I just realized that you actually did that already, my bad!
I found this interesting, but in your leading paragraph you could probably add why you would use this. Is this simply meant to teach about stacks in general or do you have an example use case for Javascript at hand?
Sure! This was a prompt from the Cracking The Coding Interview book. The exercise is: "Describe how you could use a single array to implement three stacks.":)
This is a great example and breakdown and nice solution.
It did spawn some thinking though whether it's not feasible to take a more function-oriented approach (with some traditional OOP interspersed) to really hone in on the "a single array" part of the question. By extracting separate objects for the different queues, we can hold positions inside those objects instead, shifting the responsibility completely.
I thought of something like this:
We can then initiate an object that holds the values inside it, as well as a handler for each available stack.
The last argument is whether we want to clear the slots once used, or we simply leave out to keep them in-memory (to avoid an additional operation).
Once we have our Arrack we can handle each queue separately.
We then use the
queue(ob)
anddigest()
methods to put and get items from our queue.I lazily threw errors if we try to digest what we don't have, or put more objects than we're allowed (Python habit I'm afraid), but that could be tweaked.
Feedback is very welcome :)
Hey Emma,
it was a great article. Thank you for sharing your knowledge. I will try to make this kind of example to improve my JS skills :)
What about using the structure file headers have? Files usually store the size of a field as the first bytes in them. This way, one could implement a dynamic array of dynamic stacks within a single array.
I wrote this. It uses a single array which is the class in itself. Not really needed but really fun.
Here is an example:
And a test using
console.assert
.