Mock Interview 😊
After solution 1...
Interviewer: what is the drawback of this solution?
Me: the time complexity to pop the max is O(n) because we have to scan the elements in stack backwards to find it
Interviewer: Can you improve the time complexity of the popMax() operation?
Me: (Yeah, I have seen a solution in LC...Lol, joke 😂, do not say that..). Yeah, so the key is that how we can improve the performance of finding and removing the max element?
To improve the performance in finding operation, we can use Tree structure. There are 2 options: 1. PriorityQueue and 2. Balanced Binary Search Tree(like TreeMap in Java). We cannot use PQ here because if we want to delete a element, it will O(n) time(O(n) to find it and O(logn) time to delete it). So TreeMap is a good option for us. It will take O(logn) time only.
To improve the performance in deleting operation in stack, we can use DoubleLinkedList acting as the stack, if we keep a mapping between the node in TreeMap and DoubleLinkedList, we can identify the node in DL and delete it. It will only take O(1) time. And the deleting in TreeMap is O(logn) as we discussed before.
Interviewer: Can you quickly write down the solution?
Me: (No it is 80 lines, I saw LCer said we cannot write 80 lines in the interview...Joke again 😊). Yeah sure! Dadada...
Note: we cannot use the built-in LinkedList in Java, it is indeed double linked list, but the delete operation takes O(n) time, Because it does not have interaction with TreeMap element. Element in LinkedList is wrapped in Node which is a private inner class in LinkedList. We cannot directly play with the Node. Refer: http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/LinkedList.java. So we have to implement one ourselves, and expose the Node class.
We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in O(logN) time.
class MaxStack:
def __init__(self):
self.stack = []
def push(self, x: 'int') -> 'None':
maxNum = max(x, self.peekMax()) if self.stack else x
self.stack.append([x, maxNum])
def pop(self) -> 'int':
return self.stack.pop()[0]
def top(self) -> 'int':
return self.stack[-1][0]
def peekMax(self) -> 'int':
return self.stack[-1][1]
def popMax(self) -> int: # like git rebase
maxNum = self.peekMax() #self.stack[-1][1]
# print(maxNum)
b = []
# pop them off the stack until we find the maxNum, so they come in reverse: O(n)
while self.stack[-1][0] != maxNum:
# print(self.stack.pop()[0])
b.append(self.stack.pop()[0])
# Remove the top element which is maximum
self.stack.pop()
# Push back the elements in the stack
while b:
self.push(b.pop())
return maxNum
from sortedcontainers import SortedDict
class Node:
def __init__(self, val, prev=None, nxt=None):
self.val = val
self.prev = prev
self.next = nxt
class DoubleLinkedList:
def __init__(self):
self.tail = Node(0)
self.head = Node(0, None, self.tail)
self.tail.prev = self.head
def add(self, val):
new_node = Node(val, None, self.tail)
new_node.prev = self.tail.prev
self.tail.prev.next = new_node
self.tail.prev = new_node
return new_node
def peek(self): return self.tail.prev.val
def unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
return node
def pop(self):
return self.unlink(self.tail.prev).val
class MaxStack:
def __init__(self):
self.list = DoubleLinkedList()
self.max = SortedDict()
def push(self, x: int) -> None:
node = self.list.add(x)
if x not in self.max: self.max[x] = []
self.max[x].append(node)
def top(self) -> int:
return self.list.peek()
def peekMax(self) -> int:
return self.max.peekitem()[0]
def pop(self) -> int:
val = self.list.pop()
self.max[val].pop()
if not self.max[val]: del self.max[val]
return val
def popMax(self) -> int:
val, addr = self.max.peekitem()
self.list.unlink(addr.pop())
if not addr: del self.max[val]
return val