PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • easy
  • TikTok
  • Coding & Algorithms
  • Data Scientist

Implement stacks, streaming median, and upward path sum

Company: TikTok

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

Round 1: Discuss how to deploy multimodal models under compute and GPU memory constraints. Follow-up: Given existing captions and embeddings, how to speed up video retrieval. What is overfitting and how to mitigate it. Coding: Implement MinStack that returns the minimum value in O(1) time. Round 2: Discuss methods to mitigate overfitting in deep learning and the principles behind Dropout. Compare different normalization methods and how to handle them during inference. Discuss the application of reinforcement learning in LLM post-training (RLHF). Coding: Implement MaxStack. Follow-up: How to compute the median in real-time from a data stream, and how to modify MaxStack to achieve this. Round 3: Explain Dropout again and why it maintains distribution consistency. Coding: Given a binary tree, determine whether there exists a path starting from any node, moving only upward, whose sum equals a target value.

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

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

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

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

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

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

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

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

Input: (['getMin','top','pop'], [0,0,0])

Expected Output: [None, None, None]

Explanation: Edge case: all operations on an empty stack return None.

Input: (['push','getMin','top'], [42,0,0])

Expected Output: [None, 42, 42]

Explanation: Single element: it is both the min and the top.

Input: (['push','push','push','pop','pop','getMin','top'], [1,-1,-1,0,0,0,0])

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

Explanation: Push 1,-1,-1 then pop twice; remaining stack is [1] so min and top are 1.

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

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

Expected 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.

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

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

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

Input: (['peekMax','popMax','pop','top'], [0,0,0,0])

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

Explanation: Edge case: every query on an empty stack returns None.

Input: (['push','peekMax','popMax','peekMax'], [7,0,0,0])

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

Explanation: Single element becomes the max; after popMax the stack is empty so peekMax is None.

Input: (['push','push','push','popMax','popMax','peekMax'], [-1,-3,-2,0,0,0])

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

Explanation: All-negative values: popMax peels off -1 then -2, leaving -3 as the max.

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

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

Expected 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.

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

Expected Output: [None]

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

Input: (['addNum','findMedian'], [5,0])

Expected Output: [None, 5.0]

Explanation: A single element is its own median (as a float).

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

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

Explanation: Negatives, even count: sorted [-4,-3,-2,-1], median (-3 + -2)/2 = -2.5.

Input: (['addNum','addNum','addNum','findMedian','addNum','addNum','findMedian'], [6,10,2,0,4,8,0])

Expected Output: [None, None, None, 6.0, None, None, 6.0]

Explanation: After 6,10,2 sorted [2,6,10] median 6.0; after 4,8 sorted [2,4,6,8,10] median 6.0.

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

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

Expected Output: true

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

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

Expected Output: true

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

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

Expected Output: false

Explanation: No upward chain (3, 3+1, 2, 2+1, 1) reaches 100.

Input: ([], 0)

Expected Output: false

Explanation: Edge case: an empty tree has no path.

Input: ([10], 10)

Expected Output: true

Explanation: A single node is itself a length-1 upward path equal to the target.

Input: ([-2, None, -3], -5)

Expected Output: true

Explanation: Negative values: node -3 -> parent -2 gives -3 + -2 = -5.

Input: ([3, 9, 20, None, None, 15, 7], 23)

Expected Output: true

Explanation: Node 20 (index 2) -> root 3: 20 + 3 = 23.

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.
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)
  • Solve common string/DP/stack problems - TikTok (medium)
  • Find the longest palindromic substring - TikTok (easy)
  • Implement stack variants and path-sum check - TikTok (medium)
  • Maximize sum with no adjacent elements - TikTok (medium)