Stack Coding Problem
Filed under Microsoft · Also reported at Capgemini
Free read 1 of 3Confirm output expectations and format for stack-based traversal.
The question
Solve a coding problem utilizing a stack data structure (such as evaluating Reverse Polish Notation or Next Greater Element) and optimize the solution.
Constraints
- Input arrays or strings are well-formed.
- Operations run efficiently within linear time.
Examples
- Input
- nums = [2, 1, 2, 4, 3]
- Output
- [4, 2, 4, -1, -1]
- Why
- Next greater elements for each element in the array.
Approach
Confirm output expectations and format for stack-based traversal.
Nested loops to search for conditions ahead or behind, taking O(n^2) time.
Use a monotonic stack to process elements in linear O(n) time.
Empty array, single element array.
Solution
O(n) time, O(n) space
class Solution:
def nextGreaterElement(self, nums: list[int]) -> list[int]:
res = [-1] * len(nums)
stack = []
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
idx = stack.pop()
res[idx] = val
stack.append(i)
return res
Tips
- What they are testing: Test with strictly increasing arrays, strictly decreasing arrays, and duplicate elements.
- Common mistake: Storing values instead of indices in monotonic stack problems where indices are needed to update results.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.