Coding questions · Meta

Implement power and balance-parentheses algorithms

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.

Design and implement two algorithms:

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.
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.

Fast Exponentiation by Squaring

Return x raised to integer n using exponentiation by squaring.

Examples

Example 1

Input: (2, 10)
Output: 1024.0

Explanation: Positive exponent.

Example 2

Input: (2, -2)
Output: 0.25

Explanation: Negative exponent.

Hints

Choose a representation that makes the requested operation direct.
Handle empty inputs and boundary cases first.

Minimum Remove to Balance Parentheses

Remove the minimum number of parentheses to make s valid, preserving other characters.

Examples

Example 1

Input: ('lee(t(c)o)de)',)
Output: 'lee(t(c)o)de'

Explanation: Remove extra close.

Example 2

Input: ('a)b(c)d',)
Output: 'ab(c)d'

Explanation: Remove unmatched close.

Hints

Choose a representation that makes the requested operation direct.
Handle empty inputs and boundary cases first.