Design stack with O(1) minimum query

Q: Design stack with O(1) minimum query

This is a Coding & Algorithms interview question from Anthropic for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Design a stack-like data structure that supports the following operations, each in O(1) time:

push(x) : push integer x onto the stack
pop() : remove the top element (assume it’s non-empty when called)
top() : return the top element
getMin() : return the minimum value currently in the stack

Requirements

All operations must be worst-case O(1) .
The stack may contain duplicate values.

Clarifications to address

What should happen if getMin() is called on an empty stack? (Specify an approach: error/exception/sentinel.)
Are negative values allowed? (Assume yes.)

Design stack with O(1) minimum query

Requirements

Clarifications to address

Comments (0)