← Microsoft questions

Stack Coding Problem

Filed under Microsoft · Also reported at Capgemini

Free read 1 of 3

Confirm 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

  1. Confirm output expectations and format for stack-based traversal.

Solution

O(n) time, O(n) space

Python
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.