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
  2. ***Java Stack Collection
    Basic Stack Method and Example
  3. **Infix to Postfix Conversion using Stack – Code
    Algo – http://csis.pace.edu/~wolf/CS122/infix-postfix.htm
    The rule for line 4 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. Below is the precedence function.
    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;
    }
  4. **Evaluation of Postfix Expression
    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’)
  5. *Reverse a String using Stack
  6. **Find the Next greater element in an Array. Youtube.  Code –
    We don’t need the stack at the end, so have that in mind.
  7. *Check for balanced parentheses in an expression
  8. [Pending] ***Maximum Rectangular Area in Histogram
  9. **Implement two stacks in an array – important thing here is to keep track of the array index, to prevent out of bound exception.
  10. **** How to efficiently implement k stacks in a single array? Youtube
    (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.
  11. ***Stock Span Problem  – 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!
    So here we are using two array and a stack. One is the stock array(this is the input). One result array to maintain the, Result 😉 n we use stack to maintain the last index in stock.
  12. *** Reverse a stack using Recursion – the mistake I made was that while inserting I didn’t check that the value’s were inserted the bottom because if we push anything to stack it will be at the top and not bottom.
  13. ***  Sorting a Stack. Code
  14. ** The Celebrity Problem Youtube – I liked the problem. Couldn’t directly think that it’s a stack implementation also. Multiple approach possible.
  15. How to create merge-able stack? – the details are not complete in the given question. So there are multiple options here.
    1. create a new array equal to the size of two array and combine both the array.
    2. create a linked list (how ? not sure). But can think in the direction with other input given during interview.
    3. circular list
  16. ** Design and Implement Special Stack Data Structure | Added Space Optimized Version – simple one but important. Asked in Adobe. The main idea here is to have an auxiliary stack which stores the minimum value in the stack at any point of times in the order of insertion.
  17. **** 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.
  18. ** Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis substring. Link. Code
    We only push the ‘(‘ index to stack and whenever find a ‘)’ we pop the last ‘(‘ index.
  19. [Pending] 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. For example, let the given set of intervals  Code

  20. Evaluation of Prefix Expression
  21. Infix  to Prefix Conversion using Stack
  22. Infix  to Postfix Conversion using Stack
  23. 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