The following is the questions asked by WePay. Honestly amazing engineers, meh workplace.
Create a type of queue like push/pop (FIFO) that has a function called Pops Max from the queue
- push items: (1, 5, 4, 10, 1)
- pop items => rets 1, queue is: 5, 4, 10, 1
- popMax => rets 10, queue is: 5, 4, 1
Used Tree to keep track of smallest node in LgN and Double-linkedList for removing item form queue in O(1).
Optimize runtime of this function. Trivial answer is O(n), come up with something better.
System Design: Build an Air Traffic Control System