Interview Cheat Sheets | Stacks Cheat Sheet
December 28th, 2023
Introduction to Stacks
This article will serve to further summarize the excellent overview of handling stacks in coding interviews from the tech interview handbook.
Overview on Stacks
A stack, an abstract data type, facilitates push and pop operations, adhering to the Last In, First Out (LIFO) principle. Being an abstract data type, stacks can be implemented using arrays or singly linked lists. They are crucial for nested function calls and depth-first search, where depth-first search algorithms can be implemented recursively or iteratively with a stack.
Implementations
| Language | API |
|---|---|
| C++ | std::stack |
| Java | java.util.Stack |
| Python | Simulated using List |
| JavaScript | Simulated using Array |
Time Complexity
| Operation | Big-O |
|---|---|
| Top/Peek | O(1) |
| Push | O(1) |
| Pop | O(1) |
| isEmpty | O(1) |
| Search | O(n) |
Corner Cases
- Empty stack: Popping from an empty stack
- Stack with one item
- Stack with two items
Essential Questions
- Valid Parentheses - My solution
- Implement Queue using Stacks - My solution
Recommended Practice Questions
- Implement Stack using Queues
- Min Stack - My solution
- Asteroid Collision
- Evaluate Reverse Polish Notation - My solution
- Basic Calculator
- Basic Calculator II
- Daily Temperatures
- Trapping Rain Water
- Largest Rectangle in Histogram