Amazon Interview Question
SDE1sCountry: United States
import java.util.ArrayList;
public class Stack
{
private ArrayList<Integer> stack;
public Stack()
{
stack = new ArrayList<Integer>();
}
public int push (int value)
{
stack.add(value);
return stack.size() - 1;
}
public int pop ()
{
int value = stack.get(stack.size() - 1);
stack.remove(stack.size() - 1);
return value;
}
public int getMiddle ()
{
return stack.get(stack.size()/2);
}
public int deleteMiddle ()
{
int value = stack.get(stack.size()/2);
stack.remove(stack.size()/2);
return value;
}
}
For the sake of brevity, the middle element is the 3 when there are 6 elements in the ArrayList. i.e [0,1,2,3,4,5]
Use flag to check if the length of the stack is even or odd and then accordingly update the mid element
class Stack {
int top;
StackNode middle;
StackNode last;
boolean flag;
Stack() {
top = 0;
middle = null;
last = null;
flag = false;//odd elements -true
}
void push(int data) {
StackNode newNode = new StackNode();
newNode.data = data;
if (last == null) {
last = newNode;
middle = newNode;
flag = true;
} else {
StackNode temp = last;
last = newNode;
temp.next = newNode;
newNode.previous = temp;
flag = !flag;
if (flag) {
middle = middle.next;
}
}
}
void print() {
StackNode temp = last;
while (temp != null) {
System.out.println(temp.data);
temp = temp.previous;
}
}
int getMiddle() {
return middle.data;
}
void deletMiddle() {
StackNode temp=middle;
middle.previous.next=middle.next;
middle.next.previous=middle.previous;
flag=!flag;
if(!flag){
middle=temp.previous;
}
}
}
class StackNode {
int data;
StackNode next;
StackNode previous;
StackNode() {
previous = null;
next = null;
}
}
AFAIK, ArrayList(java) or vector(c++) can be used to implement the stack(push and pop on the last element). Indexing the middle element of either would be a constant time operation.
Implement it using doubly linklist... and use an int variable to store the address of current number of elements in stack and a pointer variable to store the address of middle element.
- Hector January 09, 2014