How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Bytedance during technical interviews.

Implement stack variants and upward path sum

Quick Overview

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.

Company: Bytedance

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

##### 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. 4. **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.

Quick Answer: 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.

MinStack Operations

Simulate a stack supporting push, pop, top, and getMin in O(1) time.

Constraints

operations contain push/pop/top/getMin

Examples

Input: ((('push', 3), ('push', 1), ('getMin',), ('push', 2), ('top',), ('pop',), ('getMin',)),)

Expected Output: [1, 2, 2, 1]

Explanation: Minimum tracks stack state.

Input: ((('getMin',), ('pop',)),)

Expected Output: [None, None]

Explanation: Empty stack operations return None.

Input: ((('push', 5), ('push', 5), ('pop',), ('getMin',)),)

Expected Output: [5, 5]

Explanation: Duplicate minimum.

Hints

Maintain a parallel stack of minimum values.

MaxStack Operations

Simulate push, pop, top, peekMax, and popMax; popMax removes the most recently pushed maximum on ties.

Constraints

For this grader, a list implementation is acceptable

Examples

Input: ((('push', 5), ('push', 1), ('push', 5), ('top',), ('popMax',), ('top',), ('peekMax',), ('pop',), ('top',)),)

Expected Output: [5, 5, 1, 5, 1, 5]

Explanation: Standard MaxStack behavior.

Input: ((('popMax',), ('push', 2), ('peekMax',)),)

Expected Output: [None, 2]

Explanation: Empty popMax returns None.

Input: ((('push', 3), ('push', 3), ('popMax',), ('pop',)),)

Expected Output: [3, 3]

Explanation: Tie removes the topmost maximum.

Hints

Track the stack order; popMax scans from the top for the maximum.

Median of a Data Stream

Return the running median after each inserted number.

Constraints

nums may contain duplicates and negatives

Examples

Input: ([1, 2, 3],)

Expected Output: [1.0, 1.5, 2.0]

Explanation: Increasing stream.

Input: ([5, 15, 1, 3],)

Expected Output: [5.0, 10.0, 5.0, 4.0]

Explanation: Even and odd counts.

Input: ([-1, -2, -3],)

Expected Output: [-1.0, -1.5, -2.0]

Explanation: Negative numbers.

Input: ([],)

Expected Output: []

Explanation: Empty stream.

Hints

Keep a max-heap for the lower half and a min-heap for the upper half.

Upward Path Sum in a Binary Tree

Given a level-order binary tree, return whether any ancestor-chain path sums to target.

Constraints

level_order uses None for missing nodes

Examples

Input: ([1, 2, 3, 4, 5], 7)

Expected Output: True

Explanation: Path 2 -> 5 upward has sum 7.

Input: ([1, -2, 3, None, 4], 2)

Expected Output: True

Explanation: Path -2 -> 4 has sum 2.

Input: ([5], 5)

Expected Output: True

Explanation: Single node path.

Input: ([], 1)

Expected Output: False

Explanation: Empty tree.

Hints

An upward path is the reverse of a suffix of the current root-to-node path.

Quick Overview