Design Problems Collections


/*
Tracking current Maximum Element in a Stack
Given a Stack, keep track of the maximum value in it. The maximum value may be the top element of the stack,
but once a new element is pushed or an element is pop from the stack, the maximum element will be now from the rest of the elements.

Examples:

Input : 4 19 7 14 20
Output : Max Values in stack are
         4 19 19 19 20

Input : 40 19 7 14 20 5
Output :  Max Values in stack are
         40 40 40 40 40 40

Method 2 (Efficient): An efficient approach would be to maintain an auxiliary stack while pushing element in the main stack.
This auxiliary stack will keep track of the maximum element.
Below is the step by step algorithm to do this:

Create an auxiliary stack, say ‘trackStack’ to keep the track of maximum element
Push the first element to both mainStack and the trackStack.
Now from the second element, push the element to the main stack. Compare the element with the top element of the track stack,
if the current element is greater than top of trackStack then push the current element to trackStack otherwise push the top element
of trackStack again into it.
If we pop an element from the main stack, then pop an element from the trackStack as well.
Now to compute the maximum of the main stack at any point, we can simply print the top element of Track stack.
*/
class StackWithMax
{
    // main stack
    stack<int> mainStack;
 
    // tack to keep track of max element
    stack<int> trackStack;
 
public:
    void push(int x)
    {
        mainStack.push(x);
        if (mainStack.size() == 1)
        {
            trackStack.push(x);
            return;
        }
 
        // If current element is greater than
        // the top element of track stack, push
        // the current element to track stack
        // otherwise push the element at top of
        // track stack again into it.
        if (x > trackStack.top())
            trackStack.push(x);
        else
            trackStack.push(trackStack.top());
    }
 
    int getMax()
    {
        return trackStack.top();
    }
 
    int pop()
    {
        mainStack.pop();
        trackStack.pop();
    }
};
int main()
{
      StackWithMax s;
    s.push(20);
    cout << s.getMax() << endl;
    s.push(10);
    cout << s.getMax() << endl;
    s.push(50);
    cout << s.getMax() << endl;
      getchar();
    return 0;
}

/*
How to implement stack using priority queue or heap?
Solution:

In priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in
Last in First Out manner. The idea is to associate a count that determines when it was pushed. This count works as a key for the
priority queue.

So the implementation of stack uses a priority queue of pairs, with the first element serving as the key.
*/
typedef pair<int, int> pi;
#include <queue>
class Mystack
{
    // cnt is used to keep track of the number of
    //elements in the stack and also serves as key
    //for the priority queue.
    int cnt;
    priority_queue<pair<int, int> > pq;
public:
    Mystack():cnt(0){}
    void push(int n);
    void pop();
    int top();
    bool isEmpty();
};
// push function increases cnt by 1 and
// inserts this cnt with the original value. 
void Mystack::push(int n){
    cnt++;
    pq.push(pi(cnt, n));
}
// pops element and reduces count.
void Mystack::pop(){
    if(pq.empty()){ cout<<"Nothing to pop!!!";}
    cnt--;
    pq.pop();
}
// returns the top element in the stack using
// cnt as key to determine top(highest priority),
// default comparator for pairs works fine in this case 
int Mystack::top(){
    pi temp=pq.top();
    return temp.second;
}
 
// return true if stack is empty
bool Mystack::isEmpty(){
    return pq.empty();
}
int main()
{
    Mystack* s=new Mystack();
    s->push(1);
    s->push(2);
    s->push(3);
    while(!s->isEmpty()){
        cout<<s->top()<<endl;
        s->pop();
    }
      getchar();
    return 0;
} 

/*
Find maximum in a stack in O(1) time and O(1) extra space
Given a stack of integers. The task is to design a special stack such that maximum element can be found in O(1) time and O(1)
extra space.

Examples:

Given Stack :
2
5
1
64   --> Maximum

So Output must be 64 when getMax() is called.
*/

class MaxStack
{
      int maxElem;
      stack<int>st;
public:
      void push(int item)
      {
            if (st.empty())
            {
                  maxElem = item;
                  st.push(item);
            }
            else
            {
                  if (item<st.top())
                  {
                        st.push(item);
                  }
                  else
                  {
                        st.push(2*item - maxElem);
                        maxElem = item;
                  }
            }
      }
     
      int getMaxElem()
      {
            return(maxElem);
      }
     
      int top()
      {
            int x = st.top();
            if (x > maxElem)
            {
                  return (maxElem);
            }
            else
            {
                  return (x);
            }
      }

      void pop()
      {
            if (st.empty())
            {
                  cout<<"Stack is empty"<<endl;
            }
            else
            {
                  int x = st.top();
                  st.pop();
                  int max = maxElem;
                  if (x > maxElem)
                  {
                        maxElem = 2*maxElem - x;
                       
                  }                
            }
      }
};

int main()
{
      MaxStack stack;
      stack.push(8);
      stack.push(15);
      cout<<"maxElem = "<<stack.getMaxElem()<<endl;
      stack.push(4);
      cout<<"maxElem = "<<stack.getMaxElem()<<endl;
      stack.push(18);
      cout<<"maxElem = "<<stack.getMaxElem()<<endl;
      stack.push(16);
      cout<<"maxElem = "<<stack.getMaxElem()<<endl;
      stack.push(23);
      cout<<"maxElem = "<<stack.getMaxElem()<<endl;
      cout<<"Performing pop up operation"<<endl;
      stack.pop();
      cout<<"maxElem = "<<stack.getMaxElem()<<endl;
      stack.pop();
      stack.pop();
      cout<<"maxElem1 = "<<stack.getMaxElem()<<endl;
      getchar();
    return 0;

}  
































































































Comments

Post a Comment

Popular posts from this blog

[13 Feb 2020] Check if a given sequence of moves for a robot is circular or not

Check if a given sequence of moves for a robot is circular or not Link:  https://www.youtube.com/watch?v=f7Zd8hEbCz0 Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following. G - Go one unit L - Turn left R - Turn right Input: path[] = "GLGLGLG" Output: Given sequence of moves is circular Input: path[] = "GLLG" Output: Given sequence of moves is circular The idea is to consider the starting position as (0, 0) and direction as East (We can pick any values for these). If after the given sequence of moves, we come back to (0, 0), then given sequence is circular, otherwise not. N | | W -------------- E | | S The move ‘G’ changes either x or y according to following rules. a) If current direction is North, then ‘G’ increments y and doesn’t cha...
Read more

[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples : Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 In the given array all element appear three times except 2 which appears once. Input: arr[] = {10, 20, 10, 30, 10, 30, 30} Output: 20 In the given array all element appear three times except 20 which appears once. Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of...
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more