How do you implement a Min Stack (tracking minimum in O(1))?

0-2 years experience

1. 1We need a stack that can return the current minimum in O(1). How would you implement push, pop, top, and getMin?
2. 2If you push the values 5, 2, 8, 1 onto your min stack, what does getMin return after each operation?

2-5 years experience

1. 1Our product uses a min stack to track the lowest price in a sliding window of user actions. If we now need a 'removeBottom' operation that removes the element at the bottom of the stack, how does that affect your design?
2. 2During a recent bug, getMin started returning the wrong value after a series of pops. Walk me through how you'd debug the issue.
3. 3What trade‑offs would you consider between using a separate auxiliary stack versus storing (value, currentMin) pairs in the main stack?

5-8 years experience

1. 1We are building a high‑throughput trading engine where each thread maintains its own min stack for price ticks. How would you ensure thread safety and minimal contention while preserving O(1) getMin?
2. 2If the stack must be persisted to disk for crash recovery, how would you modify the min‑stack design to allow efficient recovery of the current minimum?

8+ years experience

1. 1Our legacy system uses a linked‑list based stack with O(N) min retrieval. We want to migrate to a min stack across multiple microservices that share state via a distributed cache. What architectural considerations and migration steps would you propose?
2. 2When scaling the min‑stack service to handle billions of operations per day, what monitoring, sharding, or alternative data‑structure strategies would you evaluate to keep latency low and guarantee correctness?