Implement power and balance-parentheses algorithms

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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Implement power and balance-parentheses algorithms

Overview

Comments (0)