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

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at xAI during technical interviews.

Validate normalized palindromes with variants

Company: xAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a function isNormalizedPalindrome(s) that returns true if s reads the same forward and backward after removing non‑alphanumeric characters and case‑folding. Follow‑ups: ( 1) Support full Unicode normalization (e.g., NFKD), diacritics stripping, and locale‑specific case rules. ( 2) Handle a streaming input where s may not fit in memory; optimize for one pass and sublinear extra space. ( 3) Allow at most one character deletion to still count as a palindrome; generalize to up to k deletions. ( 4) Return the index pair of the first mismatch if not a palindrome. Discuss time/space complexity, edge cases, and unit tests.

Quick Answer: This question evaluates string-processing skills including Unicode normalization, case-folding and diacritics handling, streaming input processing, error-tolerant palindrome logic, and analysis of time/space trade-offs.

Part 1: Basic normalized palindrome

Given a string s, remove every non-alphanumeric character, case-fold the remaining characters, and determine whether the normalized result is a palindrome. An empty normalized string counts as a palindrome.

Constraints

0 <= len(s) <= 200000
s may contain letters, digits, spaces, punctuation, and Unicode characters
Use Unicode-aware alphanumeric checks and case folding

Examples

Input: ("A man, a plan, a canal: Panama!",)

Expected Output: True

Explanation: Normalization gives 'amanaplanacanalpanama', which is a palindrome.

Input: ("race a car",)

Expected Output: False

Explanation: Normalization gives 'raceacar', which is not a palindrome.

Hints

Build the normalized sequence first: keep only alphanumeric characters and apply case folding.
After normalization, palindrome checking is just a compare against the reversed sequence.

Part 2: Unicode-normalized palindrome with diacritics stripping and locale rules

Implement a Unicode-aware palindrome checker. First apply locale-specific case rules, then case-fold, then normalize with NFKD, remove combining marks (diacritics), keep only alphanumeric characters, and finally check whether the result is a palindrome. For this problem, locale-specific handling is required only for locale_code values 'tr' and 'az': map 'I' -> 'ı' and 'İ' -> 'i' before case folding. Any other locale_code should use default Unicode behavior.

Constraints

0 <= len(s) <= 100000
locale_code is one of 'default', 'tr', or 'az'
Use NFKD normalization and strip combining marks with Unicode-aware logic

Examples

Input: ("Noël, Léon", "default")

Expected Output: True

Explanation: After case folding, NFKD normalization, and diacritics stripping, the string becomes 'noelleon', which is a palindrome.

Input: ("I, ı", "tr")

Expected Output: True

Explanation: In Turkish, 'I' maps to 'ı', so the normalized form is 'ıı'.

Hints

The Turkish/Azeri dotted-I rule must be handled before generic case folding, otherwise 'I' and 'İ' lose their distinction.
Use unicodedata.normalize('NFKD', ...) and skip characters where unicodedata.combining(ch) is nonzero.

Part 3: Streaming normalized palindrome with one pass and O(1) extra space

You are given the input text as a stream of chunks in arrival order. The full normalized string may be too large to store. Keep only alphanumeric characters, case-fold them, and determine whether the normalized stream is a palindrome. Because exact one-pass checking with sublinear space is not expected for general inputs, implement a probabilistic solution using double rolling hashes with negligible collision probability.

Constraints

The total number of characters across all chunks can be very large
Each chunk must be processed in order and should not require storing the full normalized string
Use O(1) extra space beyond a constant number of integers

Examples

Input: (["A man, ", "a plan,", " a canal: Panama"],)

Expected Output: True

Explanation: The normalized stream is 'amanaplanacanalpanama'.

Input: (["race", " a car"],)

Expected Output: False

Explanation: The normalized stream is 'raceacar', which is not a palindrome.

Hints

Maintain both a forward polynomial hash and a reverse-position polynomial hash as characters arrive.
Use two different moduli to make collisions extremely unlikely.

Part 4: K-deletion normalized palindrome

Given a string s and an integer k, remove all non-alphanumeric characters, case-fold the remaining characters, and determine whether the normalized string can be turned into a palindrome by deleting at most k characters. This includes the one-deletion follow-up as the special case k = 1.

Constraints

0 <= len(s) <= 2000 after normalization
0 <= k <= 2000
An O(n^2) dynamic programming solution is expected

Examples

Input: ("abca", 1)

Expected Output: True

Explanation: Deleting 'b' or 'c' produces a palindrome.

Input: ("abc", 1)

Expected Output: False

Explanation: At least two deletions are needed.

Hints

Think in terms of the minimum number of deletions needed to make a substring a palindrome.
Equivalent viewpoint: minimum deletions = length - longest palindromic subsequence.

Part 5: Return the first mismatch index pair

Check whether a string is a palindrome after removing non-alphanumeric characters and case-folding. If it is a palindrome, return (-1, -1). Otherwise, return the zero-based pair of original string indices corresponding to the first mismatching normalized characters encountered by the standard left/right palindrome scan. If one original character expands to multiple characters during case folding, every expanded character should map back to that original index.

Constraints

0 <= len(s) <= 200000
Indices in the answer refer to positions in the original input string
Use Unicode-aware alphanumeric checks and case folding

Examples

Input: ("ab!ca",)

Expected Output: (1, 3)

Explanation: Normalized form is 'abca'; the first mismatch is 'b' vs 'c', from original indices 1 and 3.

Input: ("A man, a plan, a canal: Panama!",)

Expected Output: (-1, -1)

Explanation: The normalized string is a palindrome.

Hints

Store both the normalized characters and the original index each normalized character came from.
Then run a normal two-pointer palindrome check on the normalized list and return the mapped original indices at the first mismatch.

Quick Overview

This question evaluates string-processing skills including Unicode normalization, case-folding and diacritics handling, streaming input processing, error-tolerant palindrome logic, and analysis of time/space trade-offs.