Coding questions · Meta
Implement string dedup and mirror tree traversal
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.
- 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.
String Cleanup By Group Deletions
Repeatedly delete groups whose length is at least k and return the final string.
Examples
Example 1
Input: ('abbbaaccz', 2)
Output: 'abz'
Explanation: Cascading deletions leave z.
Example 2
Input: ('deeedbbcccbdaa', 3)
Output: 'aa'
Explanation: k=3 deletion variant.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Mirror Boundary Traversal
Trees are [value,left,right]. Return left boundary bottom-up, root, and right boundary top-down without duplicates.
Examples
Example 1
Input: ([1,[2,[4,None,None],[5,None,None]],[3,None,[6,None,None]]],)
Output: [4, 2, 1, 3, 6]
Explanation: Left boundary bottom-up, root, then right boundary top-down.
Example 2
Input: ([1,None,None],)
Output: [1]
Explanation: Single root appears once.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.