Google Interview Question Software Engineer in Tests
Space (not time) efficient. You could:
1) Define two stacks beginning at the array endpoints and growing in opposite directions.
2) Define the third stack as starting in the middle and growing in any direction you want.
3) Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.
You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.
| | <-- tosA
|-|
|-|
|-|
|-|
|-| <-- tosB, tosC
where tos = top of stack.
Below are points to solve:
1. stack C's content will reside between tosA and tosB
2. If we push any element in B before we push anything in C, then increase tos of both B and C together.
3. If 2 elements are pushed in stack B and 1 element in stack C, then structure would be :
| | <-- tosA
|-|
|-|
|3|<-- tosC
|6|<-- tosB
|5|
After popB, it will become :
| | <-- tosA
|-|
|-|
|3|<-- tosC
|6|
|5|<-- tosB
In that case, there will be confusion that 6 is part of stack C, hence move stack C's content down by 1.
4. Stack A - Top to Bottom
Stack B - Bottom to Top
Stack C - Bottom to Top
I just don't think there exists a perfect solution that absolutely avoids shifting and makes full use of array space...
There could be some "optimal" designs with tradeoff, depending on your design goal and some other factors.
E.X. say array element is huge. then you can use another int array, and implement a linklist, and solve to problem with highest efficiency.
Balaji is great.. I like his idea...
Every third location belongs to a specific stack.
Push and Pop pertaining to that stack adjusts the indexes in increments of 3 not usual 1.
Enuf, it works!
Idea is to efficiently use capacity. A possible approach would be to have 3 structs that track each stack {Start Pos,End Position, Number of Elements}. Array becomes an array of Stack records (ie a doubly linked list record { value,prev pos, end pos }. With this we can use the array for storage and simulate efficient stacks via linked lists with records allocated from the array.
Take numbers are of the form 3n , 3n+1 , 3n+2 . Now every entry corresponding to stack one will go to 3n places , every entry of stack 2 will go to 3n+1 and 3rd stack element will go to 3n+2 position. As these numbers are different for different n , we know which number belongs to which stack.
Have one array to store values.
Have another array to store the pointers to previous locations
Have one queue to store the pointers of free spaces available.
Maintain 3 top pointers of A,B,C.
upon adding an element of a stack , say A , get the next free element from queue, update the previous of the pointer (got from queue) to be current top and update the top.
While popping , update the current top pointers from previous array.
Add the popped element to the queue.
This does seems to work for N stacks in a single array
Consider an array of size N
** create a bit map of size N and each element is of size 2 bits.
** Four possible states with 2 bits
00 - empty, 01 - belongs to stack 1
10 - belongs to stack 2, 11 - belongs to stack 3
** Initialise the bitmap with 00
For push of stacki
search from left to right in bitmap
find the index of first empty element ( bit 00)
place the element in the array at that index
update the bit to corresponding task
For pop of stacki
start from right to left in bitmap
if the corresponding bitmap is equal to stack position
set it to 00
Please check with an example
This is a Good Question. We have solutions for 3 stacks what if we want to manage 4 to 5 stacks ? or we want add dynamically one more stack to the array ? How operating system is allocating memory to the processes on RAM (in our case simple Array). May be exploring on memory allocation and de-allocation algorithm might help for these kind of problems.
Corrected implementation for the problem...
Please let me know if I have missed something
public class ArrayStack
{
boolean [] freeIndex;
int [] stackPointers = {-1, -1, -1}; //array for holding pointers to individual stacks
int stackSize;
StackNode [] buffer;
public ArrayStack(int sz)
{
stackSize = 3*sz;
buffer = new StackNode[stackSize];
freeIndex = new boolean[stackSize];
for(int i=0; i<stackSize; i++)
freeIndex[i] = true;// all elements are free for alloc
}
private int getNextFreeIndex()
{
for(int i =0; i< stackSize; i++)
{
if(freeIndex[i])
return i;
}
System.out.println("Stack Array is FULL");
return -1;
}
public void push(int stackNum, int data)
{
int index = getNextFreeIndex();
if(index < 0)
{
System.out.println("Push failed....");
return;
}
int lastIndex = stackPointers[stackNum];
stackPointers[stackNum] = index;//new index
freeIndex[index] = false;
buffer[index] = new StackNode(stackNum, lastIndex, data);
}//push ends
public int pop(int stackNum)
{
if(stackPointers[stackNum] >= 0)
{
int item = buffer[stackPointers[stackNum]].data;
int lastIndex = stackPointers[stackNum];
stackPointers[stackNum] = buffer[stackPointers[stackNum]].prevIndex;
buffer[lastIndex]= null;
freeIndex[lastIndex]= true;
return item;
}
System.out.println("Stack is Empty");
return 0;
}
public String toString()
{
String rtStr = "";
for(int i=0; i<stackSize; i++)
{
rtStr += " Index:: "+i + "Node Element:: "+buffer[i];
}
return rtStr;
}
public static void main(String [] argc)
{
System.out.println("**** Array Stack ***");
ArrayStack arr1 = new ArrayStack(2);
System.out.println("Push 3 elements in each stack");
arr1.push(0, 5);
arr1.push(1, 15);
arr1.push(2, 25);
//System.out.println("array stack view "+ arr1);
System.out.println("Removing stack 1 element...");
arr1.push(2, 25);
arr1.push(2, 25);
arr1.push(2, 25);
System.out.println("Here stack is full....");
System.out.println("Now remove one elemenet and try again...");
arr1.pop(1);
arr1.push(0, 25);
System.out.println("array stack view "+ arr1);
}
}
This is a generic Class for N Stacks Using a Single Array.
I also added some special cases to test. but somehow It just work fine. If you find any issue just let me know.
cheers,
Axel
import java.lang.Exception;
public class NStackArray{
public int array[];
public int capacity;
public StackMetaData stacks[];
public int numberStacks;
public NStackArray(int nStacks){
this.capacity = nStacks; // by the fault the capacity will only hold 1 element for each stack.
this.array = new int[this.capacity];
this.numberStacks = nStacks;
this.initStacks();
}
public NStackArray(int initCapacity,int nStacks){
if((initCapacity%nStacks)==0){
this.capacity = initCapacity;
}else{
this.capacity = initCapacity + (nStacks - (initCapacity%nStacks));
}
this.array = new int[this.capacity];
this.numberStacks = nStacks;
this.initStacks();
}
private void initStacks(){
int stackSize = this.capacity/this.numberStacks;
this.stacks = new StackMetaData[this.numberStacks];
this.array = new int[this.capacity];
int initStartIndex = stackSize/-1;
int initTopIndex = (stackSize/-1) -1;
int initEndIndex =0;
for(int i = 0; i<this.stacks.length; i++){
initStartIndex+= stackSize;
initTopIndex += stackSize; // is TopIndex < startIndex Then Stack is empty
initEndIndex += stackSize;
this.stacks[i] = new StackMetaData();
this.stacks[i].startIndex = initStartIndex;
this.stacks[i].topIndex = initTopIndex;
this.stacks[i].endIndex = initEndIndex;
}
}
public void resizeStack(){
this.capacity *=this.numberStacks; // grows by the number stacks
//System.out.println("Seziing to " + this.capacity + " for No Stacks: " + this.numberStacks);
StackMetaData tmp[] = new StackMetaData[this.numberStacks];
int tmpStacks[] = new int[this.capacity];
int stackSize = this.capacity/this.numberStacks;
int initStartIndex = stackSize/-1;
int initEndIndex = 0;
for(int i = 0; i< tmp.length; i++)
{
initStartIndex+= stackSize;
initEndIndex += stackSize;
tmp[i] = new StackMetaData();
tmp[i].startIndex = initStartIndex;
tmp[i].endIndex = initEndIndex;
int temporalIndex = tmp[i].startIndex;
for(int index = this.stacks[i].startIndex; index <= this.stacks[i].topIndex; index++){
tmpStacks[temporalIndex++] = this.array[index];
}
tmp[i].topIndex = --temporalIndex; // if topIndex < start Index then Stack is empty
}
this.stacks = tmp;
this.array = tmpStacks;
}
public void push(int stackIndex, int value)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.stacks[stackIndex].topIndex >= this.stacks[stackIndex].endIndex -1)
{
this.resizeStack();
}
this.array[++this.stacks[stackIndex].topIndex] = value;
}
public int pop(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.stacks[stackIndex].topIndex >= this.stacks[stackIndex].startIndex){
int index = this.stacks[stackIndex].topIndex--;
int value = this.array[index];
this.array[index] = 0;
return value;
}else{
return -666; // or maybe return just null or an Exception
}
}
public int peek(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex > this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.stacks[stackIndex].topIndex >= this.stacks[stackIndex].startIndex){
return this.array[this.stacks[stackIndex].topIndex];
}else{
return -666; // or maybe return just null or an Exception
}
}
public boolean isEmpty(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
return this.stacks[stackIndex].topIndex < this.stacks[stackIndex].startIndex;
}
public int size(int stackIndex)throws Exception{
if(stackIndex < 0 || stackIndex >= this.numberStacks){
throw new Exception("Stack Out of Bounds Exception");
}
if(this.isEmpty(stackIndex))return 0;
else{
return this.stacks[stackIndex].topIndex - this.stacks[stackIndex].startIndex + 1;
}
}
public void printInfo() throws Exception
{
System.out.println("Number Stacks: " + this.numberStacks);
for(int i =0; i < this.stacks.length; i++){
System.out.println("STACK ID: " + (i+1));
System.out.println("Size: " + this.size(i));
for(int index = this.stacks[i].startIndex; index <= this.stacks[i].topIndex; index++){
System.out.print(this.array[index] + " -> " );
}
System.out.println("");
}
for(int i = 0; i<this.array.length; i++){
System.out.print(this.array[i] + " -> " );
}
System.out.println("");
}
class StackMetaData
{
public int startIndex;
public int topIndex;
public int endIndex;
//public int size; // topIndex -startIndex;
}
public static void main(String [] args){
try{
NStackArray stack = new NStackArray(3);
stack.printInfo();
for(int i = 1; i< 5; i++){
stack.push(0,i*1);
stack.push(1,i*2);
stack.push(2,i*3);
stack.printInfo();
}
stack.printInfo();
for(int i = 1; i< 5; i++){
System.out.println("peek(0)" + stack.peek(0));
System.out.println("peek(1)" + stack.peek(1));
System.out.println("peek(2)" + stack.peek(2));
//stack.printInfo();
}
stack.printInfo();
for(int i = 1; i< 5; i++){
System.out.println("POP(0)" + stack.pop(0));
System.out.println("POP(1)" + stack.pop(1));
System.out.println("POP(2)" + stack.pop(2));
stack.printInfo();
}
System.out.println("End**");
}catch(Exception ex){
ex.printStackTrace();
}
}
}
1st idea : a)Start 1st array from start, and push the element ahead. b) Start 3rd array from last and start pushing element backwards. c) Start 2nd array from middle and 1 element on right and than 1 element on left.
This way we can have 3 stack but prob would be once 2nd array got any element than the 1st and 2nd array will have calculated space only..
Idea 2 : Maintain another array of size equal to original array but this would be 2 bit array. So space would be minimized. we can have 00 for 1st array , 01 for 2nd array and 10 for third array.
So whenever an stack need to fill than keep a Global pointer to put element sequentially in array and correspondingly update the augmented array index corresponding to it . This way it will help to pop a rquired element from array ...
this method is nice in the sense that different stack will have space for element even a single space is left in array , so aray would be perfectly utilized but it will take some space for bit array .
Provide ur comments on this idea.
for idea 1, it seems not good. either stack 1 and stack3 could possible meet the stack 2 even if there is more free space. then the next step would be messy
I don't really understand the upvoted solution but here's an extension to the idea
S1: Starts from index = 0, and grows towards the middle
S2: Starts from index = n-1, and grows towards the middle (by decrementing the index)
S3: Starts from the middle (mid = n/2) and flip-flops on both sides mid+1, mid-1, mid+2, mid-1. This can be easily implemented by keeping track of a counter and the direction (essentially +1 or -1). In case the index where you want to "push" the element is already occupied, try finding an index on the same side, meaning that:
if mid + k is occupied, try mid - (k + 1) if that's also occupied, then it means both S1 and S2 are exerting pressure on the stack and pushing an element on S3 is not possible.
This solution works well when all three stacks are of equal size, guaranteeing fairness to each stack. It takes care of the situation when one stack dominates the other two.
Book offers solution to that problem. It is flawed though. It is easy to fix bug in that solution. Here is basic logic:
1. Use struct (or class) that hold data and previous index
2. Use array of N+1 elements where N is number of stacks and extra element is "stack" of deleted elements.
3. Use buffer of structs from #1.
Push(object data, int stackIndex)
if there are any deleted elements (i.e. index array's last element is greater than -1 then // grab deleted node Node deleted = buffer[index[DELETED]]; // store data w/ pointer to previous element buffer[index[DELETED]] = new Node(data, index[stackNum]); // update pointer to last element in current stack index[stackNum] = index[DELETED]; // update pointer to previous deleted element index[DELETED] = deleted.previosIndex; else buffer[index[stackNum]] = new Node(data, index[stackNum]); index[stackNum] = nextIndex; nextIndex++;Pop(int stackNum)
- Mark February 07, 2011int lastStackIndex = index[stackNum]; Node node = buffer[lastStackIndex]; index[stackNum] = node.previousIndex; // set deleted node's previous index to last deleted index buffer[lastStackIndex].previousIndex = index[DELETED]; // set last deleted index to currently deleted node index[DELETED] = lastStackIndex; return node._data;