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.