PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates data-structure design and algorithmic skills including constant-time stack variants (min/max stacks), online algorithms for streaming median computation, upward-only path-sum reasoning in trees, and the ability to state time/space trade-offs and handle edge cases.

  • medium
  • TikTok
  • Coding & Algorithms
  • Machine Learning Engineer

Implement stack variants and path-sum check

Company: TikTok

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Coding tasks Solve the following algorithmic problems. ### 1) MinStack Design a stack supporting: - `push(x)`, `pop()`, `top()` - `getMin()` returning the minimum element currently in the stack All operations should run in **O(1)** time. ### 2) MaxStack Design a stack supporting: - `push(x)`, `pop()`, `top()` - `peekMax()` returning the maximum element currently in the stack - `popMax()` removing and returning the maximum element (if multiple maxima exist, remove the one closest to the top) State expected time complexities and trade-offs. ### 3) Streaming median (data stream) Given a very large stream of integers, support inserting numbers and querying the **current median** at any time. ### 4) Tree path sum with upward-only path Given a binary tree with **positive integer** node values and an integer `target`, determine whether there exists a **single-direction path that starts at any node and only moves upward to parent nodes** such that the sum of the nodes on that path equals `target`. Return `true/false`. Include any reasonable constraints you assume (e.g., number of nodes, value ranges) and handle edge cases (single node, skewed tree, large target).

Quick Answer: This question evaluates data-structure design and algorithmic skills including constant-time stack variants (min/max stacks), online algorithms for streaming median computation, upward-only path-sum reasoning in trees, and the ability to state time/space trade-offs and handle edge cases.

MinStack — O(1) getMin

Design a stack that supports `push(x)`, `pop()`, `top()`, and `getMin()` (return the current minimum), all in O(1) time. To make this executable, implement a driver `minStack(ops, args)` that replays a sequence of operations. `ops` is a list of method-name strings — the first is always `"MinStack"` (the constructor) — and `args` is a parallel list where `args[i]` is the argument list for `ops[i]` (`[x]` for `push`, `[]` otherwise). Return a list the same length as `ops`: the result of each call, using `null`/`None` for the constructor and for void operations (`push`). Assume `pop`/`top`/`getMin` are only called on a non-empty stack and `-10^9 <= x <= 10^9`.

Constraints

  • 1 <= number of operations <= 10^4
  • -10^9 <= x <= 10^9
  • pop, top, getMin are only called on a non-empty stack
  • The first op is always the constructor 'MinStack'

Examples

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

Expected Output: [None, None, None, None, -3, -3, 0, -2]

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

Input: (['MinStack','push','getMin','top','pop'], [[],[5],[],[],[]])

Expected Output: [None, None, 5, 5, 5]

Explanation: Single element: min, top, and pop all return 5.

Input: (['MinStack','push','push','push','getMin','pop','getMin','pop','getMin'], [[],[3],[3],[1],[],[],[],[],[]])

Expected Output: [None, None, None, None, 1, 1, 3, 3, 3]

Explanation: Duplicate minimums: after popping 1, the min correctly restores to 3.

Hints

  1. Keep a second stack that stores, at each level, the minimum of all elements at or below it.
  2. On push, the new running minimum is min(x, previous running minimum).
  3. Because the auxiliary stack mirrors the main stack, getMin is just its top.

MaxStack — peekMax and popMax

Design a stack supporting `push(x)`, `pop()`, `top()`, `peekMax()` (return the current maximum), and `popMax()` (remove and return the maximum; if several elements equal the maximum, remove the one closest to the top). Implement a driver `maxStack(ops, args)` that replays operations the same way as the MinStack driver: `ops[0]` is the constructor `"MaxStack"`, `args[i]` is the argument list for `ops[i]`. Return the list of results (`None` for the constructor and for void operations `push`). A straightforward implementation gives O(n) for `peekMax`/`popMax`; a balanced-BST + doubly-linked-list approach achieves O(log n).

Constraints

  • 1 <= number of operations <= 10^4
  • -10^9 <= x <= 10^9
  • pop, top, peekMax, popMax are only called on a non-empty stack
  • popMax removes the topmost occurrence when the maximum is duplicated

Examples

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

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

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

Input: (['MaxStack','push','peekMax','popMax','push','top'], [[],[7],[],[],[3],[]])

Expected Output: [None, None, 7, 7, None, 3]

Explanation: Push 7. peekMax/popMax -> 7 (now empty). Push 3. top -> 3.

Input: (['MaxStack','push','push','push','popMax','popMax','peekMax'], [[],[2],[2],[2],[],[],[]])

Expected Output: [None, None, None, None, 2, 2, 2]

Explanation: All equal maxima: popMax returns 2 twice, peekMax still 2.

Input: (['MaxStack','push','push','push','push','popMax','top'], [[],[1],[3],[3],[1],[],[]])

Expected Output: [None, None, None, None, None, 3, 1]

Explanation: Stack [1,3,3,1]. popMax removes the top-most 3 (index 2), leaving [1,3,1]. top -> 1.

Hints

  1. The simplest correct approach scans the list for the maximum on demand.
  2. For popMax with duplicates, scan from the TOP downward and delete the first match so you remove the occurrence closest to the top.
  3. To reach O(log n), pair an ordered multiset (TreeMap of value -> stack of node ids) with a doubly linked list so you can delete an interior node in O(1) once located.

Streaming median (data stream)

Support inserting integers from a large stream and querying the current median at any time. Implement a driver `medianFinder(ops, args)` where `ops[0]` is the constructor `"MedianFinder"`, `addNum` carries `[x]`, and `findMedian` carries `[]`. Return the list of results: `None` for the constructor and for `addNum`, and a float median for each `findMedian`. The median of an even-sized set is the average of the two middle values (so always return a float, e.g. `42.0`, `1.5`).

Constraints

  • 1 <= number of operations <= 10^5
  • -10^9 <= x <= 10^9
  • findMedian is only called after at least one addNum
  • Even-sized median is the average of the two middle elements (return a float)

Examples

Input: (['MedianFinder','addNum','addNum','findMedian','addNum','findMedian'], [[],[1],[2],[],[3],[]])

Expected Output: [None, None, None, 1.5, None, 2.0]

Explanation: After {1,2}: median (1+2)/2 = 1.5. After {1,2,3}: median = 2.0.

Input: (['MedianFinder','addNum','findMedian'], [[],[42],[]])

Expected Output: [None, None, 42.0]

Explanation: Single element: median is that element as a float.

Input: (['MedianFinder','addNum','addNum','addNum','addNum','findMedian'], [[],[5],[15],[1],[3],[]])

Expected Output: [None, None, None, None, None, 4.0]

Explanation: Sorted {1,3,5,15}: median (3+5)/2 = 4.0.

Input: (['MedianFinder','addNum','addNum','findMedian','addNum','addNum','findMedian'], [[],[-1],[-2],[],[-3],[-4],[]])

Expected Output: [None, None, None, -1.5, None, None, -2.5]

Explanation: Negatives: {-2,-1} median -1.5; {-4,-3,-2,-1} median (-3+-2)/2 = -2.5.

Hints

  1. Maintain two heaps: a max-heap of the smaller half and a min-heap of the larger half.
  2. Keep their sizes balanced so they differ by at most 1; the small half holds the extra element when the count is odd.
  3. If sizes are equal the median is the average of both heap tops; otherwise it is the top of the larger (small) half.

Tree path sum — upward-only path

Given a binary tree of positive integers and an integer `target`, determine whether there exists a single-direction path that starts at any node and moves only upward (toward the root, through parent pointers) whose node values sum to `target`. Return `true`/`false`. The tree is given by two parallel arrays so it is serializable: `values[i]` is node i's value, and `parent[i]` is the index of node i's parent (or `-1` if node i is the root). A path is any node followed by a contiguous chain of its ancestors (length >= 1).

Constraints

  • 0 <= number of nodes <= 10^4
  • All node values are positive integers (1 <= value <= 10^9)
  • parent[i] is a valid index < i's... not required, but -1 marks the root
  • 1 <= target <= 10^14
  • An empty tree returns false

Examples

Input: ([5, 3, 8, 1], [-1, 0, 0, 1], 9)

Expected Output: True

Explanation: Node 3 (value 1) -> node 1 (value 3) -> node 0 (value 5) sums to 1+3+5 = 9.

Input: ([5, 3, 8, 1], [-1, 0, 0, 1], 8)

Expected Output: True

Explanation: Node 1 (value 3) -> node 0 (value 5) sums to 8; also single node 2 has value 8.

Input: ([5, 3, 8, 1], [-1, 0, 0, 1], 7)

Expected Output: False

Explanation: No upward path sums to 7.

Input: ([10], [-1], 10)

Expected Output: True

Explanation: Single node equals target.

Input: ([10], [-1], 5)

Expected Output: False

Explanation: Single node value 10 cannot reach 5 (positive values only).

Input: ([], [], 0)

Expected Output: False

Explanation: Empty tree -> false.

Input: ([2, 4, 6, 8], [-1, 0, 1, 2], 20)

Expected Output: True

Explanation: Skewed chain: node 3 (8) -> node 2 (6) -> node 1 (4) -> node 0 (2) = 20.

Input: ([2, 4, 6, 8], [-1, 0, 1, 2], 100)

Expected Output: False

Explanation: Target larger than the total sum of all nodes (20).

Hints

  1. An upward path is just a node plus a contiguous run of its parents — try each node as the path's lower endpoint.
  2. Walk from a start node up through parent pointers, accumulating the sum.
  3. Because all values are positive, the running sum is monotincreasing — stop early (break) once it exceeds target.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Parse a nested list from a string - TikTok (medium)
  • Implement stacks, streaming median, and upward path sum - TikTok (easy)
  • Solve common string/DP/stack problems - TikTok (medium)
  • Find the longest palindromic substring - TikTok (easy)
  • Maximize sum with no adjacent elements - TikTok (medium)