PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates implementation-level competencies with fundamental data structures and algorithms—stack-based bracket validation, interval merging with open/closed endpoint semantics, and arithmetic expression evaluation using stacks—while also measuring the ability to design comprehensive unit tests; category: Coding & Algorithms for a Machine Learning Engineer role. It is commonly asked to gauge practical coding ability, correctness under tricky edge cases and input semantics, and test-coverage awareness, representing a practical application-level assessment that also requires conceptual reasoning about invariants and boundary behavior.

  • Medium
  • Rippling
  • Coding & Algorithms
  • Machine Learning Engineer

Implement stack and interval algorithms with tests

Company: Rippling

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement three coding tasks and design your own unit tests for each. 1) Validate Bracket String with a Stack - Input: a string s containing only '(', ')', '[', ']', '{', '}'. - Output: return true if brackets are correctly matched and nested; otherwise false. - Constraints: O(n) time, O(n) auxiliary space; do not modify the input. - Edge cases to consider: empty string; strings starting with a closing bracket; long runs of the same bracket; deeply nested pairs. 2) Merge Intervals with Open/Closed Endpoints - Input: a list of intervals, each represented as (start: int, end: int, leftClosed: bool, rightClosed: bool) with start <= end. - Task: return the union of the intervals as a minimal, sorted list after merging any that overlap or “touch” under endpoint semantics. Two intervals [a,b] and [c,d] should merge if b > c, or if b == c and (the first is rightClosed OR the second is leftClosed). For example, [1,3] and [3, 5) merge to [1, 5), but [1, 3) and (3,5] remain separate. - Constraints: O(n log n) due to sorting; O(n) extra space. - Edge cases: zero-length intervals like [3,3]; mixed open/closed boundaries; duplicate intervals; very large lists. 3) Evaluate Arithmetic Expression Using Stacks - Input: a string expr containing non-negative integers, '+', '-', '*', '/', parentheses '()', spaces, and unary minus (e.g., "-3+5", "2*(-3+ 4)"). - Output: compute the integer result; division truncates toward zero. - Constraints: O(n) time, O(n) space; handle whitespace and unary operators correctly; assume the expression is valid and the intermediate results fit in 32-bit signed integer range. - Edge cases: multiple nested parentheses, consecutive operators with unary minus (e.g., "1+-2"), spaces in arbitrary places, long inputs. Testing requirement: For each task, write comprehensive unit tests you design yourself (at least 6 per task) covering typical cases, boundary conditions, and tricky edge cases.

Quick Answer: This question evaluates implementation-level competencies with fundamental data structures and algorithms—stack-based bracket validation, interval merging with open/closed endpoint semantics, and arithmetic expression evaluation using stacks—while also measuring the ability to design comprehensive unit tests; category: Coding & Algorithms for a Machine Learning Engineer role. It is commonly asked to gauge practical coding ability, correctness under tricky edge cases and input semantics, and test-coverage awareness, representing a practical application-level assessment that also requires conceptual reasoning about invariants and boundary behavior.

Part 1: Validate Bracket String with a Stack

Given a string s containing only the characters '(', ')', '[', ']', '{', and '}', determine whether the brackets are correctly matched and properly nested. Return True if every opening bracket has a matching closing bracket in the correct order; otherwise return False.

Constraints

  • 0 <= len(s) <= 100000
  • s contains only '(', ')', '[', ']', '{', '}'
  • Target complexity: O(n) time and O(n) auxiliary space
  • Do not modify the input string

Examples

Input: "()[]{}"

Expected Output: True

Explanation: All brackets are matched and appear in valid order.

Input: "([{}])"

Expected Output: True

Explanation: This is a properly nested bracket string.

Input: "([)]"

Expected Output: False

Explanation: The bracket types cross, so nesting is invalid.

Input: "]{"

Expected Output: False

Explanation: The string starts with a closing bracket, so it cannot be valid.

Input: ""

Expected Output: True

Explanation: An empty string has no mismatched brackets.

Hints

  1. Use a stack to store opening brackets as you scan from left to right.
  2. When you see a closing bracket, the top of the stack must be the matching opening bracket.

Part 2: Merge Intervals with Open/Closed Endpoints

You are given a list of intervals. Each interval is represented as a 4-tuple: (start, end, leftClosed, rightClosed), where start and end are integers and start <= end. The booleans indicate whether each endpoint is closed (included) or open (excluded). Return the union of all intervals as a minimal sorted list after merging any intervals that overlap or touch under endpoint semantics. Two intervals should merge if the first interval ends after the second starts, or if they meet at the same point and at least one of those touching endpoints is closed. Intervals with start == end are non-empty only when both endpoints are closed; otherwise they represent the empty set and should be ignored.

Constraints

  • 0 <= number of intervals <= 200000
  • For every interval, start <= end
  • If start == end and not both endpoints are closed, the interval is empty
  • Target complexity: O(n log n) time due to sorting and O(n) extra space

Examples

Input: [(1, 3, True, True), (3, 5, True, False)]

Expected Output: [(1, 5, True, False)]

Explanation: [1,3] and [3,5) touch at 3, and at least one touching endpoint is closed, so they merge.

Input: [(1, 3, True, False), (3, 5, False, True)]

Expected Output: [(1, 3, True, False), (3, 5, False, True)]

Explanation: [1,3) and (3,5] do not overlap and do not merge because neither interval includes 3.

Input: [(1, 4, True, False), (2, 4, False, True)]

Expected Output: [(1, 4, True, True)]

Explanation: The intervals overlap, and the merged interval keeps the shared end 4 as closed because one interval includes it.

Input: []

Expected Output: []

Explanation: An empty input list produces an empty union.

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

Expected Output: [(1, 5, True, False), (5, 7, False, True)]

Explanation: The empty interval (3,3) is discarded, duplicates are absorbed, [1,2) merges with [2,5), and (5,7] remains separate because 5 is excluded from both sides.

Hints

  1. Sort intervals by starting position, with closed left endpoints before open ones when starts are equal.
  2. When two merged intervals end at the same value, the merged right endpoint is closed if either interval includes that endpoint.

Part 3: Evaluate Arithmetic Expression Using Stacks

Given a valid arithmetic expression string expr, compute and return its integer value. The expression may contain non-negative integers, '+', '-', '*', '/', parentheses '()', spaces, and unary minus. Division must truncate toward zero. You should handle operator precedence, parentheses, whitespace, and unary minus correctly.

Constraints

  • 1 <= len(expr) <= 100000
  • expr contains digits, spaces, '+', '-', '*', '/', and parentheses
  • The expression is valid
  • Intermediate and final results fit in 32-bit signed integer range
  • Target complexity: O(n) time and O(n) space

Examples

Input: "1 + 2 * 3"

Expected Output: 7

Explanation: Multiplication happens before addition.

Input: "((42))"

Expected Output: 42

Explanation: Nested parentheses around a single number should still evaluate correctly.

Input: "-3+5"

Expected Output: 2

Explanation: The leading minus is unary, so the expression is (-3) + 5.

Input: "1+-2"

Expected Output: -1

Explanation: The second minus is unary, so the expression is 1 + (-2).

Input: "2*(-3 + 4) + 7 / 2"

Expected Output: 5

Explanation: (-3 + 4) = 1, so 2*1 = 2, and 7/2 truncates toward zero to 3, giving 2 + 3 = 5.

Hints

  1. Use one stack for numbers and one for operators, applying operators by precedence.
  2. Treat unary minus as a separate operator with higher precedence than binary + and -.
Last updated: Apr 29, 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
  • AI Coding 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

  • Implement a Searchable Logger Pipeline - Rippling (hard)
  • Implement an In-Memory File System - Rippling
  • Compare Complete and Partial Poker Hands - Rippling (medium)
  • Implement Courier Delivery Cost Tracking - Rippling (medium)
  • Implement Article Vote Tracking - Rippling (medium)