Stack

List of questions on GeekForGeeks
Always use the methods defined for Stack Collection whenever possible. Like to check if the stack is empty or not use empty instead of stack.peek() != null.
Always check for edge case like what is stack is empty and raise and handle accordingly.
System.out.println(stack.toString());

  1. *Basic Implement a stack in Java  or  This
    ***Java Stack Collection Basic Stack Method and Example
    Stack st = new Stack();
       st.push(); st.pop(); st.peek(), st.search(); st.empty();


  2. **Infix to Postfix Conversion using Stack – Code eg, A * (B + C) becomes A B C + *
    Algo – http://csis.pace.edu/~wolf/CS122/infix-postfix.htm
    The rule is if the operator on the top of the stack has higher precedence than the one being read, pop and print the one on top and then push the new operator on. Three cases –
    1. if it’s not a operator.
    2. if it’s a ‘(‘. Pop all stack element until ‘)’ is encountered in stack
    3. check precedence of the operator being pushed. If  the top of stack has higher precedence than the precedence of operator being pushed, pop until the stack is empty OR ‘(‘ is encountered or the stack top has lower precedence.
    Basically the top of stack will have higher precedence operator. 
    At the end if any operator is left in stack add them to the final result. The final answer does not have bracket. We only push ‘(‘ to the stack. When a ‘)’ is encountered we pop all the operator till we find a ‘(‘ (we don’t add this to output string). As a result ‘(‘ and ‘)’ have the least precedence among operator.

    private static int precedence(char i) {
    if (i == ‘(‘ || i == ‘)’) return 1;
    else if (i == ‘-‘ || i == ‘+’) return 2;
    else if (i == ‘*’ || i == ‘/’) return 3;
    else return 0;
    }


  3. **Evaluation of Postfix Expression, eg, need to evaluate this – A B C + *
    Algo: Keep pushing all the operand to the stack. When an operator is encountered we pop the last two stack element, operate on that with the current operator and push the result back to the stack.
    Need to take care of the type conversion. Define the stack as Double and the variable and result as Double. like Double.parseDouble(‘the read value’)


  4. Reverse a String GFG
    Algo:
    1. Using Stack. O(n) extra space + O(n) time complexity
    2. Without extra space. Swap the characters from start and end and keep moving inwards.


  5. *** Find the Next greater element in an Array. Youtube.  Code –
    Algo: The idea is to keep inserting elements in the stack in a sorted manner(ascending manner). So while pushing if the element being pushed is greater than the top of stack, then that element is the next greater element for the element on the top of stack. So that will be a part of the output. Next we will push that element to the stack. At the end if all elements are pushed then the stack elements are in a ascending order, so none of the element in the stack has a greater element.


  6. *** Check for balanced parentheses in an expression
    Algo:

    – Whenever you encounter current character as ( or { or [, push it into the stack.
    – Whenever you encounter current character as ) or } or ], retrieve last element from stack and check if current character is in pair with last character retrieved from stack and if it is not in pair then expression is not balanced.
    – If we have empty stack in the end, it is balanced parentheses, else it is not balanced parentheses.


  7. *** Implement two stacks in an array 
    Algo:
    1. Divide the array into two part. A[0] to A[n/2] and A[n/2 + 1] to A[n-1]. This is not space efficient in the sense that if the first stack is full and second stack is empty and if we push to stack 1, we can’t although stack 2 is empty.
    2. This method efficiently utilizes the available space. It doesn’t cause an overflow if there is space available in arr[]. The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.


  8. **** How to efficiently implement k stacks in a single array? Youtube
    Algo: (Divide the array in slots of size n/k) A simple way to implement k stacks is to divide the array in k slots of size n/k each, and fix the slots for different stacks, i.e., use arr[0] to arr[n/k-1] for first stack, and arr[n/k] to arr[2n/k-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.


  9. **** Stock Span Problem  -The stock span is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days. The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.
    For example – If an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}.
    Algo: The algo that I personally scribbled out was correct. It’s just that it’s implementation is not as straight forward as I imagined. But this solution implements just the same thing. Kudos!
    We were pushing the stock price onto stack but we should be saving the stock index. Why ?
    So if we push the 5th stock to stack and the stack is empty (all the lower values stock then the 5th day stack were removed). So the 5th day stock span will be (5+1).
    Why 5 ? Bcoz it’s index is 5.
    If for eg the stack is not empty and the stack top has index 2. It means our span will be our current index – 2.
    Then we will push the new stock index to the stack.


  10. *** Reverse a stack using Recursion –
    Algo: So we first extract the last element like in a queue. The base condition will be as usual, till the stack is empty. Now if we push directly it will be pushed to the top. If that happens we will create the same stack again.
    So we will need to insert the element at the end of the stack. For this we will need another dedicated method which itself uses recursion to insert the element at the bottom of stack.


  11. ***  Sorting a Stack – Given a stack, sort the elements in the stack using one additional stack. Code
    Algo: We start with pushing the first element of old stack to new stack. Then for every element in the old stack we keep pushing it to the new stack. While pushing we ensure that the element being pushed is in the ascending order(top to bottom). To maintain this order we might need to move elements out of the new Stack and then push the new element in the correct order in the bottom. The element poped form the new stack will be pushed back to the old stack. Draw is on paper with a small example.
    Complexity O(n^2). Worst Case: if the stack is already sorted.


  12. **** The Celebrity Problem Youtube
    Algo:
    1. Using stack. We add all the guest to the stack. Now we pick the first two guest, A, B and ask if they know each other.
    – If A knows B, then A can’t be celebrity. Discard A, and B may be celebrity.
    – If A doesn’t know B, then B can’t be celebrity. Discard B, and A may be celebrity.
    – Repeat above two steps till we left with only one person.
    – Ensure the remained person is celebrity. (Why do we need this step?)
    The over all complexity is O(n)
    2. Using two pointers. The idea is to use two pointers, one from start and one from the end. Assume the start person is A, and the end person is B. If A knows B, then A must not be the celebrity. Else, B must not be the celebrity. We will find a celebrity candidate at the end of the loop. Go through each person again and check whether this is the celebrity.


  13. Design a stack with following operations. GFG
    a) push(Stack s, x): Adds an item x to stack s
    b) pop(Stack s): Removes the top item from stack s
    c) merge(Stack s1, Stack s2): Merge contents of s2 into s1.
    Time Complexity of all above operations should be O(1).
    Algo: It’s not possible using array in O(1). If we have two linked list it’s possible in O(1).


  14. *** Design and Implement Special Stack Data Structure –  Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.
    Algo:  Use two stacks: one to store actual stack elements and other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the minimum.
    The auxiliary array can be implemented in two ways.
    1. For each stack element we maintain an entry in auxiliary array for the minimum value.
    2. The problem with above approach is that there’s a lot of duplicate.We can push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack. Similarly during pop, if the pop off element equal to top of auxiliary stack, remove the top element of auxiliary stack.



  15. **** Design a stack that supports getMin() in O(1) time and O(1) extra space – the question just above attains the same thing in O(n) extra space. This solution is for O(1) space.
    So we have a stack and a variable that stores the minimum value(min) in the stack. The challenge is to update min whenever an item is pushed/popped from the stack. Since we can use only one variable here, we came up with a formula to generate the previous or next min element at each push/pop.
    So whenever an element is inserted and it’s value is less than the current min, we save this pushed value onto min and not stack. In stack we push a value given by this formula, if the value given is less than the current_min  =>
                                          2*value_given_for_push – current_min = y
    We insert y into stack and make current_min = value_given_for_push.
    Note: when we do this y will always be less then then value_given_for_push.
    At time of popping, we see if the value that needs to be popped is less then the current_min. It means that this value was inserted using the formula. So we know that the original value that should be popped should be current_min. So instead of popping the value from stack we pop current_min. Now we need to update the current_min( as when this value was pushed at that point, there was some other current_min, which will now again become current_min since this value is being popped). So we check the formula we used initially.  Just rearrange the terms.
    2*value_given_for_push – y = current_min
    here we know all variables except current_min.

    The solution is not something that you can come up in interview, so skipping it for now.


  16. ** Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis substring. Link. Code
    Algo: We only push the ‘(‘ index to stack and whenever find a ‘)’ we pop the last ‘(‘ index. We check the diff on the current index and the popped index.


  17. Merge Overlapping Intervals Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Let the intervals be represented as pairs of integers for simplicity.  Code

    An efficient approach is to first sort the intervals according to starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i]. Following is the detailed step by step algorithm.

    1. Sort the intervals based on increasing order of 
        starting time.
    2. Push the first interval on to a stack.
    3. For each interval do the following
       a. If the current interval does not overlap with the stack 
           top, push it.
       b. If the current interval overlaps with stack top and ending
           time of current interval is more than that of stack top, 
           update stack top with the ending  time of current interval.
    4. At the end stack contains the merged intervals.

  18. [Pending] Find maximum of minimum for every window size in a given array
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s