Jun 292017

A valid mathematical expression can also have duplicate parenthesis as shown below:


Write code to find if an expression has duplicate parenthesis. You may assume that expression does not have any white spaces. Continue reading »

Sep 172013

We have seen how to implement Queue using a linked list and using Array as the base data structure.  The question here is that given two Stacks, say S1 and S2, and no other data structure, simulate the functionality of a Queue, hence use two stacks as the base data structure for a Queue.

i.e we should expose two functions enqueue and dequeue which will insert the element and return it in FIFO order (First In First Out). Continue reading »

Jul 262013

stackStack is a collection of objects where objects are inserted and removed in the Last-In-First-Out order. Element inserted at the end will be deleted first. It is a limited access data structure which essentially allows two operations push and pop.

Push: Inserting data at the top of stack.
Pop: deleting data from the top of stack.

The function call stack of C and C++ is a typical example of stack data structure. If we have three functions main, fun1 and fun2. main calling fun1 and fun1 calling fun2 as shown below. Continue reading »

Jul 262013

A better implementation of Stack is usually using linked list unless you are sure of the number of elements in array. But if you are just starting with data structures and are not familiar with linked list, you can try implementing stack in an array.

While using array to implement stack is easy, it has limitation that the stack cannot grow beyond a fixed size (of array).  Continue reading »

Jan 132013

Given a linear memory (in the form of an array). Implement two stacks such that memory is used in an optimal manner. i.e if user wants to push an element in either of the two stacks, then the implementation should not give error until the entire array is full (So cannot use half array for first stack and half for second).

Obviously, dividing the array in two parts and using one part for one Stack will not work. 

Let us use the first half for Stack-1 and second half for Stack-2. If the user only push in Stack-2 and does not use Stack-1 at all. Then after some time Stack-2 will be full and user will not be allowed to push in Stack-2. But half of the Array (used by Stack-1) is still empty. So this is not efficient usage of memory.

Continue reading »

Jul 052012

Stack is a LIFO(Last-In-First-Out) list of elements where Push & Pop operations takes constant time, O(1). Design a Stack such that the operation of getminimum() (function returning minimum element of the stack) also takes constant time.

Please note that it will only return the current minimum element from the stack and will not delete (pop) any element from the stack.

Continue reading »