# Interview Cake's Queues and Stacks

Largest stack, A queue with two stacks, Parenthesis matching, Bracket validator

### 1. Implement a stack with a method getMax() that returns the largest element in the stack in O(1) time.

Approach:

``````- We use two stack implementation themselves: one holds all the items and the
other holds all the maximum values after each push() and pop().
- That way, we could keep track of your maximum value up to date in constant
time.
``````

Cost:

``````- O(1) time, O(m) space where m is the number of operations performed on the
stack.
``````

### 2. Implement a queue with 2 stacks.

Approach:

``````- Use one stack for enqueuing item and the other to reverse the order them for
dequeuing/popping item.
``````

Cost:

``````- O(1) time, O(m) space m is the number of operations.
``````

### 3. Given a sentence as string, and the position of an opening parenthesis position, find the matching closing one position.

Example:

``````- Input: "I ((like) (nesting) parenthesis)", opening parenthesis position = 2
Output: 31, because the matching parenthesis of the one in position 2 is at
index 31.
``````

Approach:

``````- Iterate through the string and keep a count of matching parenthesis at each
step.
``````

Cost:

``````- O(n) time, O(1) space.
``````

### 4. Given a string, determine if its brackets are properly nested.

Example:

``````- Input: "{[]()}"
Output: true
- Input: "{[(])}"
Output: false
- Input: "{[}"
Output: false
``````

Approach:

``````- Use a stack to keep track of matching parenthesis as we iterate
through the string.
``````

Cost:

``````- O(n) time and O(n) space, where n is the number of operations.
``````