Katkat
Back

Implement string dedup and mirror tree traversal

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.