Monday, November 2, 2015

Zenefits: mini Stack

Implement a min stack, which supports push(), pop() and getMin() in ave. O(1).

Requirements: 
1. You cannot use the Stack.
2. You can only use one "stack".

Solution:
Implement a doubly linked list, to mimic the stack. Move head pointer when push or pop an element. Use another pointer to maintain the min. If the min gets popped, we need to iterate over the linked list to get the next min element. So the amortized time for GetMin() is O(1).

Code (Java):
public class MinStack {
    private ListNode head = null;
    private ListNode min = null;
    
    public void push(int x) {
        ListNode newNode = new ListNode(x);
        
        if (head == null) {
            head = newNode;
        } else {
            head.next = newNode;
            newNode.prev = head;
            head = newNode;
        }
        
        // Update the min value
        if (min == null || newNode.val <= min.val) {
            min = newNode;
        }
    }
    
    public int pop() {
        ListNode node = head;
        
        head = head.prev;
        // Be careful only one node in the list
        if (head != null) {
            head.next = null;
        }
        
        // Find out the new min
        if (min == node) {
            ListNode p = head;
            min = head;
            while (p != null) {
                if (p.val < min.val) {
                    min = p;
                }
                p = p.prev;
            }
        }
        
        return node.val;
    }
    
    public int getMin() {
        return min.val;
    }
    
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        
        minStack.push(4);
        minStack.push(2);
        minStack.push(3);
        minStack.push(1);
        
        System.out.println(minStack.getMin()); // Return 1
        System.out.println(minStack.pop()); // Return 1
        System.out.println(minStack.getMin()); // Return 2
        System.out.println(minStack.pop()); // Return 3
        System.out.println(minStack.pop()); // Return 2
        System.out.println(minStack.getMin()); // Return 4
        System.out.println(minStack.pop()); // Return 4
    }
}

No comments:

Post a Comment