Implement stack and tree algorithms
Company: Bytedance
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Solve the following algorithm problems:
1. Design a `MinStack` data structure that supports `push(x)`, `pop()`, `top()`, and `getMin()` in `O(1)` time.
2. Design a `MaxStack` data structure. Support the standard operations `push(x)`, `pop()`, `top()`, `peekMax()`, and `popMax()`.
3. Given a stream of numbers arriving one by one, compute the median in real time after each insertion. Explain the data structure you would use, and discuss whether ideas from the `MaxStack` design can be adapted to support this functionality efficiently.
4. Given a binary tree with integer node values and an integer `targetSum`, determine whether there exists a path whose nodes sum to `targetSum`, where the path may start at any node and may move only upward through parent links. In other words, every valid path must lie on a single ancestor chain, but it does not need to start at the root.
Quick Answer: This question evaluates proficiency with stack and tree data structures, algorithm design for constant-time operations, and online/streaming median maintenance, and is commonly asked to assess a candidate's ability to augment data structures, manage time/space trade-offs, and reason about ancestor-chain path sums.