Implement stack variants and path-sum check

Q: Implement stack variants and path-sum check

This question evaluates data-structure design and algorithmic skills including constant-time stack variants (min/max stacks), online algorithms for streaming median computation, upward-only path-sum reasoning in trees, and the ability to state time/space trade-offs and handle edge cases.

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

Coding tasks

Solve the following algorithmic problems.

1) MinStack

Design a stack supporting:

push(x) , pop() , top()
getMin() returning the minimum element currently in the stack

All operations should run in O(1) time.

2) MaxStack

Design a stack supporting:

push(x) , pop() , top()
peekMax() returning the maximum element currently in the stack
popMax() removing and returning the maximum element (if multiple maxima exist, remove the one closest to the top)

State expected time complexities and trade-offs.

3) Streaming median (data stream)

Given a very large stream of integers, support inserting numbers and querying the current median at any time.

4) Tree path sum with upward-only path

Given a binary tree with positive integer node values and an integer target, determine whether there exists a single-direction path that starts at any node and only moves upward to parent nodes such that the sum of the nodes on that path equals target.

Return true/false.

Include any reasonable constraints you assume (e.g., number of nodes, value ranges) and handle edge cases (single node, skewed tree, large target).