Microsoft Interview Question Software Engineer in Tests
Country: United States
Why not use a resizeable array and just access arr[size/2+1] when you want the middle element? Adjusting some middle pointer seems more complicated to me, though it is definitely an approach that will work.
I would rather use an ArrayList with functions defined something like this.
class Stack{
ArrayList mStack = new ArrayList();
public void push (int e){
mStack.add(0,e);
}
public int pop(){
return mStack.remove(0);
}
public int findmiddle(){
return mStack.get((mStack.size()/2)+1); // get method is of O(1);
}
} // End of class
}
}
Can we use hash table to build up the Stack with Keys as incremental value(1,2,3,...etc.,) and kee track of Top pointer and due to hash table it is dynamic as well.
Double linked list is the easy to implement solution for this problem.
Although balanced BST can also be used to solve this problem but at Left & Right height of the tree will grow by n/2 where n is the total number of nodes in the tree.
So BST to push and pop will not give best of BST, ultimately it will look like a double linked list
let's say
node
{
next
last
payload
count
}
initial ,
next =nil
last
=nil
payload
=nil
count=0
Using Double LL
Insert the node.
Calculate the mid point (n/2+1).
Place the start pointer at the mid point.
count++
PUSH
To push new nodes traverse backward from the start pointer till end
insert new node.
recalculate the mid-point.
Update start pointer & count++.
POP
Traverse backward from start pointer till you find the last node.
pop the node
Recalulate the mid point ,
Set start pointer,
count--
GetMiddle
return start->payload :)
If you implement stack as a dynamic array this is trivial. Otherwise have a balanced tree with nodes having index as rank. Then root will always be the middle element.
1. After push and pop operations, we need to adjust middle element value in "Middle" variable .
2. After push operation, no of element in stack are even no need to change middle element in "Middle" variable
3. After pop operation, no of element in stack are odd no need to change middle element in "Middle" variable
#define STACK_SIZE 100
class stack
{
int top;
int middle; // stores middle element
int S[STACK_SIZE];
stack()
{
top = -1 ;
middle = -1;
}
int getmiddle(int count);
public:
int findMidElement();
void push( int elem );
int pop(void);
};
int stack::findMidElement()
{
return middle;
}
void push (int elm )
{
if( top+1 == STACK_SIZE )
{
printf("\n stack overflow \n ");
return ;
}
S[++top] = elm;
// no of elements are odd in stack , then get correct middle element
if( (top + 1) % 2 == 1 )
{
middle = getmiddle( int (top/2) );
}
}
int stack::pop( void )
{
if ( top == -1 )
{
printf("\n stack underflow \n ");
return -1; // error
}
int elm = s[top--] ;
if( (top+1 ) % 2 == 0 )
{
middle = getmiddle(int (top/2));
}
return elm;
}
int stack::getmiddle(int count)
{
int elm, retElm;
if( count == 0)
{
elm = pop();
push(elm);
return elm;
}
elm = pop();
retElm = getmiddle(count-1);
push(elm);
return retElm;
}
Double linked list as said by Tintin.
#include <stdio.h>
#include <stdlib.h>
/* Structures */
typedef struct node {
int val ;
struct node *prev;
struct node *next ;
}node ;
typedef struct dlist {
int count ;
int midpos ;
node* start ;
node* end ;
node* middle ;
}dlist ;
dlist* init () {
dlist *head ;
head = (dlist *) malloc (sizeof(dlist)) ;
head->count = 0 ;
head->midpos = 0 ;
head->start = NULL ;
head->end = NULL ;
head->middle = NULL ;
return head ;
}
node* createNode (int val) {
node *ele ;
ele = (node *) malloc (sizeof(node)) ;
ele->val = val ;
ele->prev = NULL ;
ele->next = NULL ;
return ele ;
}
/* PUSH Operation */
dlist* push (dlist *head, int val) {
node* ele = createNode (val) ;
head->count ++ ;
if ( head->start == NULL ) {
head->start = ele ;
head->end = ele ;
head->middle = ele ;
} else {
head->end->next = ele ;
ele->prev = head->end ;
head->end = ele ;
if ( (head->count) & 1 )
head->middle = head->middle->next ;
}
return head ;
}
/* Pop Operation */
int pop (dlist **head) {
int val ;
node *temp ;
if ( (*head)->count == 0 ) {
printf ( "\nPopping can be performed!\n" );
return -1 ;
}
val = (*head)->end->val ;
(*head)->count -- ;
if ( (*head)->count == 0 ) {
(*head)->start = NULL ;
(*head)->end = NULL ;
(*head)->middle = NULL ;
return val ;
}
temp = (*head)->end ;
(*head)->end = (*head)->end->prev ;
(*head)->end->next = NULL ;
temp->prev = NULL ;
if ( (((*head)->count) & 1) == 0 )
(*head)->middle = (*head)->middle->prev ;
free ( temp ) ;
return val ;
}
void visit (dlist *head) {
node *temp ;
if ( head->count > 0 ) {
printf ( "\nStarting from bottom :\n" ) ;
for ( temp = head->start ; temp ; temp = temp->next )
printf ( "%d\t", temp->val ) ;
}
}
int menu () {
int opt ;
printf ( "\n1. push" ) ;
printf ( "\n2. pop" ) ;
printf ( "\n3. middle" ) ;
printf ( "\n4. Exit" ) ;
printf ( "\nEnter choice : \t" ) ;
scanf ( "%d", &opt );
if ( opt > 4 || opt < 1 )
return menu() ;
return opt ;
}
/* Get MIDDLE node */
void getMid (dlist *head) {
if ( head->count == 0 )
return ;
printf ( "\nMin element is :\t%d", head->middle->val ) ;
}
int main () {
dlist *head = init() ;
int opt , num ;
do {
opt = menu ();
switch ( opt ) {
case 1 : printf ( "\nEnter val :\t" ) ;
scanf ( "%d", &num );
push (head, num );
visit (head) ;
break ;
case 2 :
if ( (num = pop(&head)) != -1 )
printf ( "\nPopped val is :\t", num );
visit (head) ;
break ;
case 3 :
getMid (head) ;
break ;
}
} while ( opt != 4 ) ;
free ( head ) ;
return 0;
}
Using Doubly Linked List:
typedef struct DoublyLinkedListNode {
int Data;
DoublyLinkedListNode *Next;
DoublyLinkedListNode *Prev;
DoublyLinkedListNode(int n) {
Data = n;
Next = NULL;
Prev = NULL;
}
} DLstack;
class Stack {
public:
Stack ( ) ;
~Stack ( ) ;
int Pop ( ) ;
void Push ( int num ) ;
int Mid ( ) ;
void PopMid ( ) ;
void Display ( ) ;
bool isEmpty ( ) ;
private:
int top;
DLstack *stack;
DLstack *midNode; //Keeps track of middle element
DLstack *lastNode;
bool midFlag; //To check the behaviour of Mid Element
};
Stack::Stack() {
stack = NULL;
top = 0;
midNode = NULL;
lastNode = NULL;
midFlag = false;
}
Stack::~Stack() {
while( stack ) {
DLstack* temp = stack;
stack = stack->Next;
delete temp;
}
}
void Stack::Push(int n) {
DLstack *newNode = new DLstack(n);
if( !stack ) { // Stack is Empty
stack = newNode;
midNode = newNode;
lastNode = newNode;
midFlag = true;
}
else {
lastNode->Next = newNode;
newNode->Prev = lastNode;
lastNode = newNode;
//Update the Mid Element Node
midFlag = !midFlag;
if(midFlag)
midNode = midNode->Next;
}
top++;
}
int Stack::Pop() {
int nRet=0;
DLstack *temp = lastNode;
lastNode = lastNode->Prev;
if(lastNode)
lastNode->Next = NULL;
nRet = temp->Data;
delete temp;
top--;
//Update the Mid Element Node
midFlag = !midFlag;
if(midFlag)
midNode = midNode->Prev;
return nRet;
}
int Stack::Mid() {
return midNode->Data;
}
void Stack::PopMid() {
if( midNode ) {
DLstack *temp = midNode;
if( midNode->Prev )
midNode = midNode->Prev;
midNode->Next = temp->Next;
temp->Next->Prev = midNode;
delete temp;
midFlag = !midFlag;
if(midFlag)
midNode = midNode->Next;
top--;
}
}
void Stack::Display() {
DLstack* temp = stack;
while( temp ) {
cout<<temp->Data;
temp = temp->Next;
(temp!=NULL)?cout<<"<=>":cout<<"\n";
}
}
bool Stack::isEmpty() {
if( NULL == stack )
return true;
return false;
}
Design a stack with operations on middle element.
How to implement a stack which will support following operations in O(1) time complexity?
1. push() which adds an element to the top of stack.
2. findMiddle() which will return middle element of the stack.
3. pop() which removes an element from top of stack.
Push and pop are standard stack operations. If the number of elements to be pushed in the stack is 0 or negative, it should display Invalid Input.
could anyone please help me in writing the code
Have two stacks, insert element in each stack alternatively. The stack where new element to be inserted changed alternatively. Similar is true for pop operation. At any time the stack top other than stack where push and pop will be performed gives middle element.
A single linked list is enough since middle never goes to previous nodes:
class NODE
{
public:
NODE * next;
int value;
public:
NODE(int data)
{
value = data;
next = NULL;
}
};
class MyStack
{
private:
NODE * root;
NODE * tail;
NODE * middle;
bool even;
public:
MyStack()
{
root = NULL;
tail = NULL;
middle = NULL;
even = true;
}
void Push(int data)
{
NODE * node = new NODE(data);
if (tail == NULL)
{
root = node;
tail = node;
even = !even;
middle = node;
}
else
{
tail->next = node;
tail = node;
even = !even;
if (even) middle = middle->next;
}
}
int Pop()
{
if (root == NULL) throw;
NODE * node = root;
if (root == tail)
{
root = NULL;
tail = NULL;
middle = NULL;
even = !even;
}
else
{
root = root->next;
even = !even;
if (even) middle = middle->next;
}
int data = node->value;
delete node;
return data;
}
int findMiddle()
{
if (middle == NULL) throw;
return middle->value;
}
};
Will following statement ok for push as well as pop?
if (even) middle = middle->next;
I don't think so!!!
What we can do is have our Node class contain a field middle which will be integer. Now as we are pushing a new node on stack we can calculate middle element using middle=n/2+1. Thus we are keeping track of the middle element at each instance of Stack either while pushing or popping.
I think a double linked list would be easier, with the top being the head and another pointer pointing to the middle element, which can be adjusted with O(1) for every push and pop.
- Tintin April 21, 2012