Questions
8 of 18
What is a Stack? Explain LIFO.
Difficulty: 3/10
Memory Management, Call Stack, Undo/Redo Mechanisms
Stack and LIFO
A Stack is a linear data structure that follows the LIFO principle: Last In, First Out. The most recently inserted element is the first element removed. A stack typically exposes operations such as push, pop, and peek, all of which can be implemented in O(1) time.
javascript
- 1
Insertion and deletion happen at the same end, called the top.
- 2
LIFO means the newest element is processed first.
- 3
Typical operations are O(1).
- 4
Stacks can be implemented using arrays, dynamic arrays, or linked lists.
- 5
Common uses include function calls, expression evaluation, undo operations, and backtracking.
Scenario Questions
0-2 years experience
- 1Imagine you're building a simple text editor and need to implement a basic 'Undo' feature. How would you use a stack to keep track of the user's actions so that the most recent action is always reverted first?
- 2We have a string of code and want to make sure all the parentheses, curly braces, and square brackets are balanced and closed in the correct order. How would you walk through this string using a stack to validate it?
2-5 years experience
- 1We're building a multi-step wizard form where users can go forward and backward. A junior developer used a standard stack to track the history, but users are complaining that if they go back 5 steps and then enter a new branch, the forward history gets corrupted or behaves weirdly. How would you debug this, and is a stack still the right choice here?
- 2You are implementing a browser-like back/forward navigation service. You decided to use two stacks. Walk me through how you handle a user clicking 'Back', 'Forward', and then navigating to a completely new URL. What edge cases do we need to watch out for?
5-8 years experience
- 1We are designing a high-throughput undo/redo manager for a collaborative design tool like Figma. If users perform thousands of actions, a naive in-memory stack will eventually cause out-of-memory errors. How would you design a bounded stack or a tiered storage strategy to handle this at scale?
- 2In a multi-threaded environment, we have multiple worker threads pushing and popping tasks from a shared execution stack. How would you implement this stack to ensure thread safety while minimizing lock contention under heavy write loads?
8+ years experience
- 1Our microservices architecture uses a distributed saga pattern to manage multi-service transactions. When a step fails, we need to execute compensating transactions in reverse order—essentially a distributed LIFO rollback. How would you architect this rollback mechanism to handle network partitions, partial failures, and idempotent retries across teams?
- 2We are migrating a legacy monolithic application that relies heavily on deep, synchronous recursive call stacks to a reactive, non-blocking event-driven architecture. How do we redesign these deeply nested LIFO execution flows to prevent thread starvation and manage state across asynchronous boundaries?
Follow-up Questions
- How would you implement a stack where retrieving the minimum element always takes O(1) time?
- What are the memory and performance trade-offs of using an array-based stack versus a linked-list-based stack?
- How does the call stack behave during deep recursion, and how would you refactor a recursive algorithm to use an iterative stack to prevent stack overflow?