Implement string dedup and mirror tree traversal
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
- 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:
(
1) take the left boundary nodes (excluding the root) from the deepest leftmost leaf up to root.left (bottom-up);
(
2) then include root;
(
3) 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.
Quick Answer: 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.