Katkat
Back

Implement stack and interval algorithms with tests

RipplingMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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.

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.
  1. 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,
  1. merge to [1, 5), but [1,
  2. 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.
  1. 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.