How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Anthropic.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Design stack with O(1) minimum query | Anthropic Coding Question

Design stack with O(1) minimum query

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

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

Quick Answer: This question evaluates understanding of stack-based data structures, constant-time operation constraints, and handling edge cases such as empty queries, duplicate entries, and negative values.

Implement a stack that supports the following operations in O(1) time each: - push(x): Push integer x onto the stack - pop(): Remove the element on top of the stack (no return value) - top(): Return the top element of the stack, or None if the stack is empty - min(): Return the minimum element currently in the stack, or None if the stack is empty You are given a sequence of operations. Execute them in order and return a list of results for only the operations that produce output (top and min). Note: pop does NOT produce output.

Constraints

1 <= len(operations) <= 2 * 10^5
For 'push', -10^9 <= value <= 10^9
Each operation must run in O(1) time
pop on an empty stack should do nothing

Examples

Input: ([('push', 5), ('push', 2), ('push', 2), ('min', None), ('pop', None), ('min', None), ('top', None)],)

Expected Output: [2, 2, 2]

Explanation: After pushing 5,2,2: min=2. Pop removes top 2, min remains 2, top is 2.

Input: ([],)

Expected Output: []

Explanation: No operations produce output.

Input: ([('min', None), ('top', None), ('pop', None), ('push', -1), ('min', None), ('top', None)],)

Expected Output: [None, None, -1, -1]

Explanation: min/top on empty return None. pop on empty does nothing. After push -1, min/top are -1.

Input: ([('push', 3), ('push', 1), ('push', 2), ('min', None), ('pop', None), ('min', None), ('pop', None), ('min', None), ('top', None)],)

Expected Output: [1, 1, 3, 3]

Explanation: Stack evolves: [3,1,2] min=1; pop-> [3,1] min=1; pop-> [3] min=3; top=3.

Input: ([('push', 2), ('push', 2), ('min', None), ('pop', None), ('min', None), ('pop', None), ('min', None)],)

Expected Output: [2, 2, None]

Explanation: Duplicate minimums handled: min=2; pop keeps min=2; pop empties stack so min=None.

Hints

Maintain a second stack that tracks the minimum value at each depth of the main stack.
When pushing a value, also push the new minimum so far; when popping, pop from both stacks.

Quick Overview

This question evaluates understanding of stack-based data structures, constant-time operation constraints, and handling edge cases such as empty queries, duplicate entries, and negative values.