Implement stacks, streaming median, and upward path sum

Q: Implement stacks, streaming median, and upward path sum

This multi-part question evaluates proficiency in data structure design (augmented stacks for min/max, data structures for streaming medians), order-statistics and real-time aggregation, and constrained binary-tree traversal for upward-only paths, while requiring clear time/space complexity analysis and edge-case reasoning; such prompts are commonly asked to assess efficient state management, invariant maintenance, and algorithmic trade-off reasoning in the Coding & Algorithms domain. The level of abstraction spans practical implementation and conceptual understanding, emphasizing implementation-level details and complexity analysis for data-structure augmentation, streaming algorithms, and constrained tree traversal.

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

Complete the following coding problems. State the time/space complexity and key edge cases for each.

1) MinStack

Design a stack that supports:

push(x)
pop()
top()
getMin() : returns the current minimum value in the stack

getMin() must run in O(1) time (all other operations should also be amortized O(1)).

2) MaxStack

Design a stack that supports:

push(x)
pop()
top()
peekMax() : returns the current maximum value in the stack
popMax() : removes and returns the current maximum value (if there are duplicates, pop the one closest to the top of the stack)

Describe your chosen data structure and its complexity.

3) Streaming Median from a Data Stream

Design a data structure that receives numbers from a continuous stream and supports:

addNum(x)
findMedian() : returns the median of all elements seen so far

Target efficiency: insertion O(log n), query O(1).

4) How to Modify MaxStack to Support Real-Time Median

Building on your MaxStack implementation, discuss how to adapt or extend the data structure so that it supports stack-like operations while also efficiently supporting findMedian(). Describe the additional structures needed, complexity, and how to maintain consistency.

5) Binary Tree: Upward-Only Path Sum

Given a binary tree and an integer targetSum, determine whether there exists a path such that:

The path can start from any node ;
Each step can only move from the current node to its parent (i.e., the path direction is strictly upward);
The sum of node values along the path equals targetSum .

Output: whether such a path exists (true/false).

Note: If the node structure does not include a parent pointer, assume the input provides root, and you need to handle the "upward" constraint during traversal.