Implement stack variants and upward path sum
Company: Bytedance
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Answer the following coding questions.
1. **MinStack**: Design a stack that supports `push(x)`, `pop()`, `top()`, and `getMin()` such that each operation runs in **O(1)** time.
2. **MaxStack**: Design a stack that supports `push(x)`, `pop()`, `top()`, and `getMax()` such that each operation runs in **O(1)** time.
3. **Median of a data stream**: Design a data structure that processes a stream of numbers and supports:
- `addNum(x)`: insert a new number
- `findMedian()`: return the current median
Aim for efficient online updates.
4. **Binary tree upward path sum**: Given the root of a binary tree and a target sum, determine whether there exists a path whose values sum to the target, where the path:
- may start at **any node**,
- moves **only upward** toward ancestors,
- contains one or more nodes,
- and cannot revisit nodes.
Return `true` if such a path exists, otherwise `false`.
Quick Answer: This question set evaluates data structure design and algorithmic reasoning—specifically stack variants (MinStack/MaxStack), online median maintenance for data streams, and upward path-sum detection in binary trees—assessing competencies in invariants, constant-time operation design, streaming algorithms, and tree traversal-based sum reasoning.