Interview Q&A / Data Structures & Algorithms

1. How do you design a stack that returns the minimum element in O(1)?

   Keep a second stack of minimums. On each push, also push the smaller of the new value and the current minimum. Pop from both together, and the top of the second stack is always the minimum.

   IntermediateQuick answerCoding1 min read
2. How do you implement a queue using two stacks?

   Push new items onto an input stack. When you need to dequeue and the output stack is empty, pour everything from the input stack into the output stack, which reverses the order, then pop from the output stack.

   IntermediateQuick answerCoding1 min read
3. How do you design an LRU cache with O(1) get and put?

   Combine a hash map for instant lookup with an ordering of recent use. In JavaScript a Map remembers insertion order, so deleting and re-inserting a key on each access moves it to the newest end; the oldest key is evicted when full.

   AdvancedQuick answerCoding1 min read