Katkat
Back

Design a stack with max removal

LinkedInSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates data-structure design and algorithmic complexity analysis by requiring a stack-like structure that supports standard stack operations plus efficient maximum retrieval and targeted removal, assessing practical implementation skills and time-complexity reasoning at a practical application level.

Design a stack-like data structure for integers that supports the following operations efficiently:

  • push(x): insert x onto the stack.
  • pop(): remove and return the top element.
  • top(): return the top element without removing it.
  • peekMax(): return the maximum value currently in the stack.
  • popMax(): remove and return the maximum value currently in the stack. If the maximum value appears multiple times, remove the one closest to the top.

Implement the data structure and analyze the time complexity of each operation.