WorksApp Interview Question Software Engineer / Developers
Hi,
I would implement stack with array has the backing store.
I will then simply return array[0] as lowest element, array[n] as last element
and for the middle element it will array[n/2]
This will retain the functionality of stack as is and provide 3 extra functions that will exclusively operate on an Array.
Here is my implementation using a doubly linked list:
public class MidStack<E> {
private Node top;
private Node low;
private Node mid;
private boolean evenSize = true;
public E pop() {
if (top == null) throw new EmptyStackException();
E value = top.value;
top = top.next;
if (top != null) top.previous = null;
// modify low & pop references
if (top == null) {
low = null;
mid = null;
} else if (evenSize) {
mid = mid.next;
}
// even or odd stack size
evenSize = !evenSize;
return value;
}
public void push(E e) {
Node n = new Node();
n.value = e;
n.next = top;
if (top != null) top.previous = n;
top = n;
// modify low & pop references
if (low == null) low = top;
if (mid == null) {
mid = low;
} else if (!evenSize) {
mid = mid.previous;
}
// even or odd stack size
evenSize = !evenSize;
}
public E peekLowestElement() {
if (low == null) throw new EmptyStackException();
return low.value;
}
public E peekHighestElement() {
if (top == null) throw new EmptyStackException();
return top.value;
}
public E peekMiddleElement() {
if (mid == null) throw new EmptyStackException();
return mid.value;
}
public String toString() {
StringBuilder sb = new StringBuilder();
toString(top, sb);
return sb.toString();
}
private void toString(Node top, StringBuilder sb) {
if (top == null) return;
sb.append(top.value.toString());
if (top.next != null) {
sb.append("<-");
toString(top.next, sb);
}
}
private class Node {
E value;
Node previous;
Node next;
}
public static void main(String[] args) {
MidStack<Integer> list = new MidStack<Integer>();
list.push(8);
list.push(7);
list.push(6);
list.push(5);
list.push(4);
list.push(3);
list.push(2);
list.push(1);
System.out.println(list.toString());
System.out.println(list.peekHighestElement());
System.out.println(list.peekLowestElement());
System.out.println(list.peekMiddleElement());
list.pop();
System.out.println(list.toString());
System.out.println(list.peekMiddleElement());
list.pop();
System.out.println(list.toString());
System.out.println(list.peekMiddleElement());
}
}
All the operations will be done in O(1) time and O(1) space.
We gonna use a Doubly linked list.
-a pointer to keep lowest value record.
-top value can be easily fetched any time.
-a pointer to keep track of middle element based on a counter value(containing no. of nodes)
Whenever a node is added or popped the mid pointer is checked if it shall be moved or not.
class Node
{
Node prev;
Node next;
int info;
}
public class StackQues {
Node mid=null;
int count=0;
Node lowest=null;
Node start=null;
public void push(int data)
{
Node temp=new Node();
temp.info=data;
temp.next=start;
temp.prev=null;
count++;
if(start==null)
{
start=temp;
mid=start;
lowest=start;
return;
}
else
{
start.prev=temp;
start=temp;
if(count%2==0)
{
mid=mid.prev;
}
}
}
public int pop()
{
if(start==null)
{
return -1;
}
Node temp=start;
start=start.next;
count--;
if(start==null)
{
mid=null;
lowest=null;
}
else
{
start.prev=null;
if(count%2==1)
{
mid=mid.next;
}
}
return temp.info;
}
public void findmid()
{
if(mid==null)
{
System.out.println("Empty");
return;
}
System.out.println("mid: "+mid.info);
}
public void findlowest()
{
if(lowest==null)
{
System.out.println("Empty");
}
else
{
System.out.println("lowest: "+lowest.info);
}
}
public void findtop()
{
if(start==null)
System.out.println("Empty");
else
System.out.println("top: "+start.info);
}
use
Struct Stack_element{
int element;
int lowest;
int highest;
int count;
int middle_element;
};
so on every push fill these fields also. The complexity is O(1).
Extending @Junaid's answer:
We will keep an array of Struct_element pointers. With every push, we will update the min/max by looking at last-but-one'th element. If the value in peek()->max < data_to_push, max = data for next node. Similarly, If the value in peek()->min > data_to_push, min = data for next node. And middle value can be found by looking up in array at [peek()->count / 2 + 1]th index in the array.
Can we have a separate stack for min, max and middle element. So that they all operate on O(1) time . Suppose if, I push(11) to the stack, I add the 1st element to all the 3 stacks. Now, push(5)
- minstack - compares 11 with 5. Since 5 is less than 11, 5 is pushed to the minstack.
- maxstack - compares 11 with 5. since 11>5 , 5 is not pushed onto maxstack.
- middlestack - keep track of the number of elements pushed. when push(5), n=2 (number of elements in stack). middle=2 , so push 5 onto the middle stack.
Please advise if I am wrong. Also, can someone explain me, what happens for a stack with maximum number of elements.
Thanks.
I am not writing any code but I guess the logic should be
- Gaurav September 06, 2011peekHighestElement(): its just pop functon without removal of element.
peekLowestElement():keep the index or pointer of the first element until it get popped out itself,would need to modify push() for the first insertion.
peekMiddleElement():also keep a pointer or index of the middle , just update whenever push pop done
, we keep a pointer at the last element which on calling