Katkat
Back

Implement stack variants and upward path sum

ByteDanceData Scientist · Onsite
HardData ScientistOnsiteCoding & Algorithms

Last updated

A four-part ByteDance Data Scientist onsite coding question: implement an O(1) MinStack, a MaxStack with peekMax/popMax, a streaming median finder, and a binary-tree upward (node-to-ancestor) path-sum check. It tests data-structure augmentation, streaming order statistics, and prefix-sum tree reasoning.

Question

Answer the following coding questions. They progress from augmented stacks to streaming statistics to tree path reasoning.

  1. MinStack — Design a stack that supports push(x), pop(), top(), and getMin(), where every operation runs in O(1) time.

  2. MaxStack — Design a stack that supports push(x), pop(), top(), peekMax() (return the maximum currently in the stack), and popMax() (remove and return the maximum). Aim for constant-time top/peekMax and efficient popMax. A getMax() accessor (return the current maximum without removing it) is equivalent to peekMax().

  3. Median of a data stream — Given a stream of numbers arriving one by one, design a data structure that supports:

  • addNum(x): insert a new number;
  • findMedian(): return the current median after each insertion. Aim for efficient online updates. Also discuss whether ideas from the MaxStack design can be adapted to maintain the running median efficiently.
  1. Binary tree upward path sum — Given the root of a binary tree with integer node values and an integer target sum, determine whether there exists a path whose values sum to the target, where the path:
  • may start at any node (not necessarily the root),
  • moves only upward from a node toward its ancestors (a single ancestor chain),
  • contains one or more nodes (a single node is a valid path),
  • and may not revisit any node.

Return true if such a path exists, otherwise false. You may preprocess parent pointers if helpful.