Implement fast power and k-palindrome
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
The phone screen included two coding tasks:
1. **Fast exponentiation**
Given a floating-point number `x` and a signed integer `n`, compute `x` raised to the power `n`. Handle negative exponents correctly, and make the solution efficient for very large `|n|`.
Example:
- Input: `x = 2.0`, `n = -3`
- Output: `0.125`
The expected approach should run in `O(log |n|)` time.
2. **Palindrome after at most `k` deletions**
This was asked as a follow-up to the simpler version where only one deletion is allowed. Given a string `s` and an integer `k`, determine whether it is possible to delete at most `k` characters so that the remaining string is a palindrome.
Example:
- Input: `s = "abcdeca"`, `k = 2`
- Output: `true`
- Explanation: deleting `b` and `e` leaves `acdca`, which is a palindrome.
Write code for both tasks and discuss the time and space complexity of each solution.
Quick Answer: This question evaluates numerical algorithm design and string algorithm skills, focusing on efficient exponentiation with negative exponents and determining whether a string can become a palindrome after at most k deletions, while testing handling of edge cases and reasoning about time and space complexity.
Part 1: Fast Exponentiation
Given a floating-point number x and a signed integer n, compute x raised to the power n. Your solution must correctly handle negative exponents and should be efficient even when |n| is very large. A naive O(|n|) loop is too slow for this task.
Constraints
- -100.0 <= x <= 100.0
- -2^31 <= n <= 2^31 - 1
- If x == 0, then n > 0 to avoid division by zero
- Return 1.0 when n == 0
Examples
Input: (2.0, -3)
Expected Output: 0.125
Explanation: 2^-3 = 1 / (2^3) = 1 / 8 = 0.125.
Input: (2.0, 10)
Expected Output: 1024.0
Explanation: 2^10 = 1024.
Input: (-2.0, 3)
Expected Output: -8.0
Explanation: An odd exponent keeps the negative sign.
Input: (5.0, 0)
Expected Output: 1.0
Explanation: Any nonzero number raised to 0 is 1.
Input: (0.0, 5)
Expected Output: 0.0
Explanation: 0 raised to any positive exponent is 0.