How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Implement fast power and k-palindrome

Quick Overview

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.

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.

Hints

Use the fact that x^n can be built from repeated squaring: x^8 = (((x^2)^2)^2).
For negative exponents, first convert the problem into computing a positive exponent of the reciprocal.

Part 2: Palindrome After At Most k Deletions

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. The empty string is considered a palindrome.

Constraints

0 <= len(s) <= 1000
0 <= k <= len(s)
s consists of lowercase English letters

Examples

Input: ("abcdeca", 2)

Expected Output: True

Explanation: Deleting 'b' and 'e' leaves 'acdca', which is a palindrome.

Input: ("acdcb", 1)

Expected Output: False

Explanation: At least 2 deletions are needed to make it a palindrome.

Input: ("", 0)

Expected Output: True

Explanation: The empty string is already a palindrome.

Input: ("abcd", 3)

Expected Output: True

Explanation: Delete three characters to leave any one character, which is a palindrome.

Input: ("racecar", 0)

Expected Output: True

Explanation: The string is already a palindrome.

Hints

Think about the minimum number of deletions needed to make a substring s[i...j] a palindrome.
If the two end characters match, move inward. If they do not match, try deleting one end or the other and take the better choice.

Quick Overview