McAfee Interview Question
SDETsCountry: India
Interview Type: Written Test
For each Stack, start from the two extremes of the array and move towards the center of the array as elements are being added to them.
Full = When the stacks meet.
import java.lang.Integer;
public class TwoStacksInOneArray {
private Integer[] array ;
private Integer top1 ;
private Integer top2 ;
private Integer size ;
public TwoStacksInOneArray ( Integer size ) {
this.array = new Integer[size] ;
this.top1 = -1 ;
this.top2 = size ;
this.size = size ;
}
public void push1 ( Integer item ) {
if ( top1 < (top2 - 1) ) {
array[++top1] = item ;
}
else {
System.out.println( "Stack OverFlow. Unable to Push " + item );
}
}
public void push2 ( Integer item ) {
if ( top1 < (top2 - 1) ) {
array[--top2] = item ;
}
else {
System.out.println( "Stack OverFlow. Unable to Push " + item );
}
}
public Integer pop1 ( ) {
if ( top1 > -1 ) {
Integer item = array[top1--] ;
return item ;
}
else {
System.out.println( "Stack UnderFlow" );
return Integer.MIN_VALUE ;
}
}
public Integer pop2 ( ) {
if ( top2 < size ) {
Integer item = array[top2++] ;
return item ;
}
else {
System.out.println( "Stack UnderFlow" );
return Integer.MIN_VALUE ;
}
}
public String toString() {
String arr = new String() ;
arr = "[ " ;
for (int j = 0; j < array.length; j++) {
arr = arr + this.array[j] + " " ;
}
return arr + " ]";
}
public static void main(String[] args) {
TwoStacksInOneArray stack = new TwoStacksInOneArray(5) ;
stack.push1(1);
stack.push2(5);
stack.push1(2);
stack.push1(3);
stack.push1(4);
System.out.println( "Stack = " + stack.toString() );
stack.push2(6);
System.out.println( "Pop1 = " + stack.pop1() );
System.out.println( "Pop1 = " + stack.pop1() );
System.out.println( "Pop1 = " + stack.pop1() );
System.out.println( "Pop1 = " + stack.pop1() );
System.out.println( "Pop1 = " + stack.pop1() );
System.out.println( "Pop2 = " + stack.pop2() );
System.out.println( "Pop2 = " + stack.pop2() );
}
}
Output:
Stack = [ 1 2 3 4 5 ]
Stack OverFlow. Unable to Push 6
Pop1 = 4
Pop1 = 3
Pop1 = 2
Pop1 = 1
Stack UnderFlow
Pop1 = -2147483648
Pop2 = 5
Stack UnderFlow
Pop2 = -2147483648
I would propose the following: First stack (left stack) will start at the beginning of the array while the other one (right stack) will start at the end and will grow backwards. Throw an exception when the stacks meet each other.
A sample code is shown below:
public class DoubleStack<E>{
E[] a;
int i, j, N;
pubic DoubleStack(int N) {
this.a = (E[]) new Object[N];
this.i = 0;
this.j = N-1;
this.N = N;
}
// Left stack
public void pushLeft(E e) {
checkSpace();
a[i++] = e;
}
public E popLeft() {
if (i == 0)
throw new IndexOutOfBoundsException("Left stack is empty");
E e = a[i];
a[i--] = null; // avoid loitering
return e;
}
// Right stack
public void pushRight(E e) {
checkSpace();
a[j--] = e;
}
public E popRight() {
if (j == N-1)
throw new IndexOutOfBoundsException("Right stack is empty");
E e = a[j];
a[i++] = null; // avoid loitering
return e;
}
private void checkSpace() {
if(i == j) throw new IndexOutOfBoundsException("Stack is full")
}
}
class OneArrayTwoStack {
private int[] array;
// index points to the last pushed element
private int index1; // 1 is for left stack
private int index2;
public OneArrayTwoStack(int size) {
if (size <= 0) {
System.err.println("Size should be greater than 0");
System.exit(1);
}
array = new int[size];
index1 = -1;
index2 = array.length;
}
public boolean isStack1Empty() {
if (index1 == -1) {
return true;
}
return false;
}
public boolean isStack2Empty() {
if (index2 == array.length) {
return true;
}
return false;
}
public boolean pushOnStack1(int value) {
if(isStack1Full()) {
throw new Exception("Stack is full!");
}
array[index1++] = value;
}
public boolean pushOnStack2(int value) {
if (isStack2Full()) {
throw new Exception ("Stack is full!");
}
array[index2--] == value;
}
public int popFromStack1() {
if (isStack1Empty()) {
throw new Exception ("Stack is empty");
}
return array[index1--];
}
public int popFromStack2() {
if (isStack2Empty()) {
throw new Exception ("Stack is empty");
}
return array[index2++];
}
public int peekIntoStack1() {
if (isStack1Empty()) {
throw new Exception ("Stack is empty");
}
return array[index]1;
}
public int peekIntoStack2() {
if (isStack2Empty()) {
throw new Exception ("Stack is empty");
}
return array[index2];
}
public boolean isStack1Full() {
return isArrayFull();
}
public boolean isStack2Full() {
return isArrayFull();
}
private boolean isArrayFull() {
if (index1 + 1 == index2) {
return true;
}
return false;
}
}
class StackFromArray {
private int[] arr;
private int[] pointer;
private int stackSize;
public StackFromArray(int stacksSize) {
arr = new int[stacksSize*2];
this.stackSize = stacksSize;
pointer = new int[]{-1, stacksSize-1};
}
public boolean isEmpty(int stackNum) {
if(pointer[stackNum - 1] == (stackNum - 1) * stackSize -1) {
return true;
}
return false;
}
public boolean isFull(int stackNum) {
if(pointer[stackNum-1] == ((stackNum - 1) * stackSize + stackSize -1)) {
return true;
}
return false;
}
public void push(int stackNum, int data) {
if(isFull(stackNum)) {
System.out.println("Stack: " + stackNum + " is full. Cannot push " + data);
return;
}
arr[++pointer[stackNum - 1]] = data;
}
public int pop(int stackNum) {
if(isEmpty(stackNum)) {
System.out.println("Stack: " + stackNum + " is Empty.");
return -1;
}
return arr[pointer[stackNum - 1]--];
}
public int peek(int stackNum) {
if(isEmpty(stackNum)) {
System.out.println("Stack: " + stackNum + " is Empty.");
return -1;
}
return arr[pointer[stackNum-1]];
}
public void display(int stackNum) {
for(int i = ((stackNum - 1) * stackSize); i <= ((stackNum - 1) * stackSize + stackSize -1); i++) {
System.out.println("-------");
System.out.println("| " + arr[i] + " |");
}
System.out.println("-------");
}
}
public class ImplementTwoStackInSingleArray {
public static void main(String[] args) {
StackFromArray mStack = new StackFromArray(5);
mStack.pop(1);
mStack.push(1, 10);
System.out.println(mStack.pop(1));
mStack.pop(1);
mStack.push(1, 10);
mStack.push(1, 20);
mStack.push(1, 30);
mStack.push(1, 40);
mStack.push(1, 50);
mStack.push(1, 60);
mStack.display(1);
mStack.pop(2);
mStack.push(2, 10);
System.out.println(mStack.pop(2));
mStack.pop(2);
mStack.push(2, 110);
mStack.push(2, 220);
mStack.push(2, 330);
mStack.push(2, 440);
mStack.push(2, 550);
mStack.push(2, 660);
System.out.println(mStack.pop(2));
mStack.push(2, 660);
mStack.display(2);
}
}
Even indices = stack 1
- SK January 22, 2015Odd indices = stack 2
Keep 2 pointers - one for top of each stack
This is, I think easier to implement than the stacks starting from the ends and meeting inwards, but it will not work very well if one stack if being underutilized