Implement string dedup and mirror tree traversal
Overview
This question evaluates string-processing and tree-traversal algorithm skills, focusing on efficient group-deletion and streaming-capable string dedup operations and a mirrored boundary traversal of binary trees, and it tests algorithmic design, complexity guarantees, and correctness/termination reasoning.
Meta
Sep 6, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0
- String cleanup with group deletions (LeetCode-inspired): Given a string s consisting of lowercase letters, repeatedly delete any maximal contiguous group of two or more identical characters (e.g., "abbbaaccz" -> remove "bbb" and "aa" -> "ccz" -> remove "cc" -> "z"). Return the final string after all deletions. Design an O(n) time, O(n) space solution and explain why it terminates and is correct. Follow-up: support a parameter k >= 2 to delete any group whose length is at least k; and support streaming input where characters arrive one by one.
- Mirror boundary traversal of a binary tree (LeetCode-inspired): Given the root of a binary tree, output a "mirror boundary" list constructed as follows: (
- take the left boundary nodes (excluding the root) from the deepest leftmost leaf up to root.left (bottom-up); (
- then include root; (
- then take the right boundary nodes (excluding the root) from root.right down to the deepest rightmost leaf (top-down). Do not list any node more than once; if a node is both on a boundary and a leaf, include it once. Return the resulting list of node values. Provide an algorithm with time O(n) and space O(h), where h is the tree height.