Interview Question
Developer Program EngineersTeam: India
Country: India
Interview Type: In-Person
Stack 1 grows from left to right. Stack 2 from right to left. Stack 3 in the center such that it grows in one direction initially and if finds no space, reverses and grows in the other direction.
Example.
s1 = {1,2,3}
s2 = {4,4}
s3 = {7,8,9}
Array of size 10 looks like this
[1,2,3, x, x,7,8,9,4,4]
stack 1 and stack 2 give warning when there is no space to fill a new element.
stack 3 tries to use free spaces on either side. Above if we push(stack3, 10)
It will reverse itself and insert 10 to the left.
[1,2,3, x,10,9,8,7,4,4]
^
So what will you do when I want to push something to stack 2 after you've completed that reverse operation? Reverse again? Seems like you might be doing a worst-case O(n) reverse for every push.
Yes.Agree with you. In terms of time it will do horribly when stacks start getting full.
First stack grows from left to right. Second from right to left and third in middle.
When an element is inserted into third stack insertion is done like pendulum movement i.e once from left and once from right.In this way we have less wastage of space on an average.
We keep left, middle,right pointers and if left == middle we can't insert in stack1 and right = middle we can't insert from right.
Start 1st stack from left, 3rd stack from right and 2nd stack from the middle. While doing operations on the stacks, we will try to maintain the invariant: the second stack occupies a contiguous chunk b/w the left chunk and the right chunk, and the 2 empty spaces b/w these 3 chunks are of equal size (or differ by atmost 1).
For example, here's a valid configuration of the array (*s denote empty locations):
{1,2,2,3,4,*,*,*,2,3,4,*,*,*,*,1,4}. And here's an invalid configuration: {1,2,3,4,5,*,2,1,3,*,*,*,1}.
If the invariant is maintained, whenever any 2 stacks meet, we have exactly 1 empty slot in the array, and then we can issue a warning "Stack getting full!".
Now how to maintain this invariant? For every element of the 2nd stack, we just need to maintain a variable which says whether the last element was added to the left or to the right. Also, while doing any push() or pop() operations on the 1st or 3rd stack, we need to push2(pop2()) i.e. pop an element of the 2nd stack and push it on the 2nd stack again (to 'refresh' the invariant).
I'm not completely sure if this works ;) but its O(N) extra space and O(1) for all push/pop operations.
The problem is that you're not maintaining any ordering information in the second stack. If I want to pop off the last 100 elements I inserted into stack 2, how will stack 2 know which ones they were? They were definitely some of the ones on the left and some of the ones on the right, but in what order and how many from each side? You've lost that information.
Here's a possible way to do it: consider the first third of the array to be devoted to elements of stack 1, the second third to stack 2, the last third to stack 3. If you run out of space devoted to any stack, double the size of the whole array.
To push on to the stack, we'll use a simple calculation like (totalArraySize * stackNumber / 3) + existingSizeOfGivenStack. To pop, we'll remove the element at (totalArraySize * stackNumber / 3) + existingSizeOfGivenStack - 1.
What's the complexity of resizing, you might ask? After resizing an array of n elements at a cost of O(n), each stack has n/3 capacity, and since that's doubled from before, previously the largest stack had n/6 elements. So there's at least n/6 free space in each stack, and it will be at least that many operations before we resize again.. So the O(n) cost of resizing is amortized over n/6 elements, for an O(1) cost per element. So pushing and popping is O(1).
The array of size n contains at least n/6 elements, so space usage is O(n) with the number of elements.
see: stackoverflow.com/questions/4770627/how-to-implement-3-stacks-with-one-array/4770793#4770793
- cobra July 08, 2012