Interview Note - Data Structure

Data Structure is a way to organize data. It provides some methods to handle data stream, e.g. insert, delete, etc.

Linear Data Structure

Queue & Stack

Min Stack
Use two stacks, one is storing the input, when calling pop() or peek(), pop from another stack, which stores the minimum values from top to bottom.

class MinStack {
    ArrayList<Integer> stack = new ArrayList<Integer>();
    ArrayList<Integer> minStack = new ArrayList<Integer>();
    public void push(int x) {
        stack.add(x);
        if(minStack.isEmpty() || minStack.get(minStack.size() - 1) >= x) {
            minStack.add(x);
        }
        return;
    }

    public void pop() {
        if(stack.isEmpty()) {
            return;
        }
        int elem = stack.remove(stack.size() - 1);
        if(!minStack.isEmpty() && minStack.get(minStack.size() - 1) == elem) {
            minStack.remove(minStack.size() - 1);
        }
        return;
    }

    public int top() {
        if(!stack.isEmpty()) {
            return stack.get(stack.size() - 1);
        }
        return 0;
    }

    public int getMin() {
        if(!minStack.isEmpty()) {
            return minStack.get(minStack.size() - 1);
        }
        return 0;
    }
}

Implement Queue by stacks
Use two stacks, one is for storing elements. When calling pop() or top(), pop the elements from the first stack and push them into the second one.

public class Solution {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public Solution() {
       // do initialization
       stack1 = new Stack<Integer>();
       stack2 = new Stack<Integer>();
    }
    
    public void push(int element) {
        stack1.push(element);
    }

    public int pop() {
        if(stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int top() {
        if(stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
}

Largest Rectangle in Histogram
Brute force: totally O(n^2) windows and O(n) to find the minimun one in each window, so we need O(n^3) time.
Improve: for each number, search both side of it until find two smaller number, calculate the result, O(n^2) cost.
Best: use a stack to store the index (all increased heights), when faced with a smaller one, pop out from tha stack and calculate the area until the value bigger than the peek() one. This method cost O(n) time, with O(n) space in worst case (two passes).

Read More