Implement power and balance-parentheses algorithms
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Design and implement two algorithms:
1) Fast exponentiation: Implement a function pow(x, n) that returns a real number x raised to an integer exponent n using exponentiation by squaring in O(log |n|) time. Handle negative exponents, x = 0, n = 0, very large |n|, and discuss iterative vs. recursive trade-offs and numerical precision. Analyze time and space complexity.
2) Minimal-removal parentheses balancing: Given a string s consisting of lowercase letters and parentheses '()' only, remove the minimum number of parentheses to make s valid (properly nested). Return any one valid result. Provide an O(n) solution; compare a stack-based approach to a two-pass marking approach; justify minimality and analyze time and space complexity.
Quick Answer: This question evaluates algorithmic design and analysis skills, covering fast exponentiation with attention to numerical edge cases and precision, and minimal-removal parentheses balancing with string-processing and data-structure reasoning.