cswork / libraryOpen practice workspace

Coding questions · TikTok

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.

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.

MinStack — Stack with O(1) getMin

Design a stack that supports push(x), pop(), top(), and getMin() (the current minimum), with getMin() running in O(1) time.

Since an online judge cannot drive a class directly, simulate the stack: you are given two parallel arrays operations (a list of operation names) and values (the argument for each operation; use any placeholder such as 0 for operations that take no argument). Apply the operations in order and return a list out where out[i] is the return value of the i-th operation: getMin and top return the requested value (or None if the stack is empty), while push and pop return None.

Implement the standard two-stack trick: alongside the value stack keep a min_stack whose top always holds the minimum of all values currently in the stack.

Constraints

  • operations[i] is one of 'push', 'pop', 'top', 'getMin'.
  • values[i] is the integer argument for 'push' and an ignored placeholder otherwise.
  • pop/top/getMin on an empty stack are tolerated and yield None.
  • -10^9 <= pushed value <= 10^9.

Examples

Example 1

Input: (['push','push','push','getMin','pop','top','getMin'], [-2,0,-3,0,0,0,0])
Output: [None, None, None, -3, None, 0, -2]

Explanation: Push -2,0,-3. getMin -> -3. Pop -3. top -> 0. getMin -> -2.

Example 2

Input: (['push','push','getMin','push','getMin','pop','getMin'], [5,5,0,3,0,0,0])
Output: [None, None, 5, None, 3, None, 5]

Explanation: Duplicate minimums: getMin stays correct after popping one of the equal minima.

Hints

  1. Keep a second stack that mirrors the main stack but stores the running minimum.
  2. On push, the new min-stack top is min(new value, previous min-stack top).
  3. Push and pop the two stacks together so they stay aligned; getMin is just min_stack[-1].

MaxStack — Stack with peekMax and popMax

Design a stack supporting push(x), pop(), top(), peekMax() (current maximum) and popMax() (remove and return the current maximum; on ties remove the one closest to the top).

Simulate it: given parallel arrays operations and values, apply each operation in order and return a list out where pop/top/peekMax/popMax yield the requested value (or None if the stack is empty) and push yields None.

A correct O(n)-per-popMax implementation scans for the topmost occurrence of the maximum and removes it. (A faster O(log n) design uses a balanced BST / two heaps with lazy deletion; either is accepted as long as the observable behavior matches.)

Constraints

  • operations[i] is one of 'push', 'pop', 'top', 'peekMax', 'popMax'.
  • popMax removes the topmost occurrence when the maximum is duplicated.
  • Operations on an empty stack yield None.
  • -10^9 <= pushed value <= 10^9.

Examples

Example 1

Input: (['push','push','push','top','popMax','top','peekMax','pop','top'], [5,1,5,0,0,0,0,0,0])
Output: [None, None, None, 5, 5, 1, 5, 1, 5]

Explanation: Stack [5,1,5]: top 5; popMax removes the topmost 5 -> [5,1]; top 1; peekMax 5; pop 1 -> [5]; top 5.

Example 2

Input: (['push','push','peekMax','popMax','peekMax'], [4,2,0,0,0])
Output: [None, None, 4, 4, 2]

Explanation: peekMax 4, popMax removes 4 -> [2], peekMax 2.

Hints

  1. popMax must respect stack order on ties: scan from the top and remove the first element equal to the maximum.
  2. After removing a non-top element, the elements above it shift down by one position — the stack order is otherwise preserved.
  3. For O(log n), pair a balanced BST keyed by value (mapping to a stack of insertion ids) with the main stack, and delete lazily.

Streaming Median from a Data Stream

Design a data structure that ingests numbers from a stream via addNum(x) and answers findMedian() (median of all numbers seen so far) with O(log n) insertion and O(1) query.

Simulate it: given parallel arrays operations and values, apply each operation in order and return a list out where each findMedian yields the current median as a float (or None if no numbers have been added) and each addNum yields None. With an even count the median is the average of the two middle values.

The standard solution keeps two heaps: a max-heap lo for the smaller half and a min-heap hi for the larger half, balanced so |lo| - |hi| is 0 or 1.

Constraints

  • operations[i] is 'addNum' or 'findMedian'.
  • values[i] is the integer for 'addNum' and an ignored placeholder for 'findMedian'.
  • findMedian before any addNum returns None.
  • Even count -> average of the two middle elements (a float).

Examples

Example 1

Input: (['addNum','addNum','findMedian','addNum','findMedian'], [1,2,0,3,0])
Output: [None, None, 1.5, None, 2.0]

Explanation: After 1,2 median is (1+2)/2=1.5; after adding 3 the sorted set is [1,2,3] so median is 2.0.

Example 2

Input: (['findMedian'], [0])
Output: [None]

Explanation: Edge case: querying before any number is added returns None.

Hints

  1. Split the data into a lower half (max-heap) and an upper half (min-heap).
  2. Always push to lo, immediately move lo's top to hi, then rebalance so lo holds the extra element on odd counts.
  3. Median is lo's top when sizes differ, else the average of both tops.

Binary Tree — Upward-Only Path Sum

Given a binary tree and an integer target, determine whether there exists a strictly-upward path whose node values sum to target. A path may start at any node and each step moves only from a node to its parent (node -> parent -> grandparent -> ...). Return True/False.

The tree is provided as a level-order (LeetCode-style) array tree, where tree[i] is the value of the node at array index i (or None for a missing node). In this array layout the parent of index i > 0 is at index (i - 1) // 2.

For each present node, walk upward toward the root accumulating the sum and check whether any prefix of that upward chain equals target.

Constraints

  • tree is a level-order array; tree[i] is None for a missing node.
  • The parent of node index i (>0) is (i - 1) // 2.
  • An empty tree (or tree[0] is None) returns False.
  • Node values and target may be negative.
  • A path can be a single node (length-1 chain).

Examples

Example 1

Input: ([5, 4, 8, 11, None, 13, 4, 7, 2], 22)
Output: true

Explanation: Node 7 (index 7) -> 11 (index 3): 7 + 11 + 4 = 22 climbing up to node 4 (index 1).

Example 2

Input: ([5, 4, 8, 11, None, 13, 4, 7, 2], 18)
Output: true

Explanation: Node 7 -> its parent 11: 7 + 11 = 18.

Hints

  1. In the array layout you do not need real parent pointers: parent(i) = (i - 1) // 2.
  2. From each node, accumulate the sum while climbing to the root and check for an exact match at every step.
  3. Because values can be negative you cannot prune early on overshoot — examine every prefix of each upward chain.