Palindrom — Zadanie rekrutacyjne #11

Czego szuka rekruter: normalizacja wejścia, porównanie dwóch wskaźników, obsługa Unicode
Poziom: Junior

Zadanie

Napisz funkcję, która sprawdza czy podany string jest palindromem. Palindrom to tekst brzmiący tak samo czytany od lewej do prawej i od prawej do lewej. Ignoruj spacje i wielkość liter.

Przykłady: "kayak", "Ala", "kobyła ma mały bok", "A man a plan a canal Panama"

Czego szuka rekruter

Rekruter sprawdza czy kandydat:

• Normalizuje wejście przed porównaniem (małe litery, usunięcie spacji/interpunkcji)
• Zna metodę dwóch wskaźników jako O(1) pamięci alternatywę dla odwracania
• Obsługuje null, pusty string, jeden znak
• Myśli o tym co “ignorować” — tylko spacje? Interpunkcję? Cyfry?

Edge cases

✅ Rozwiązanie 1 — odwracanie po normalizacji

static bool IsPalindrome(string? text)
{
    if (string.IsNullOrWhiteSpace(text))
        return false;
    
    // Normalizacja: tylko litery i cyfry, małe litery
    string normalized = new string(
        text.Where(c => char.IsLetterOrDigit(c))
            .Select(char.ToLowerInvariant)
            .ToArray());
    
    return normalized == new string(normalized.Reverse().ToArray());
}

Czytelne, ale tworzy dwa dodatkowe stringi — O(n) pamięci.

✅ Rozwiązanie 2 — dwa wskaźniki (O(1) pamięci)

static bool IsPalindromeTwoPointers(string? text)
{
    if (string.IsNullOrWhiteSpace(text))
        return false;
    
    int left = 0, right = text.Length - 1;
    
    while (left < right)
    {
        // Pomiń znaki niebędące literami/cyframi
        while (left < right && !char.IsLetterOrDigit(text[left]))
            left++;
        while (left < right && !char.IsLetterOrDigit(text[right]))
            right--;
        
        if (char.ToLowerInvariant(text[left]) != char.ToLowerInvariant(text[right]))
            return false;
        
        left++;
        right--;
    }
    
    return true;
}

Nie alokuje dodatkowej pamięci — sprawdza in-place porównując znaki od obu końców jednocześnie.

Normalizacja dla tekstu polskiego

char.ToLowerInvariant('Ą') zwróci 'ą' — ale char.IsLetter('ą') zwróci true, więc polskie znaki są obsłużone. Ważne żeby używać ToLowerInvariant (nie ToLower) dla deterministycznych wyników niezależnie od locale.

// "kobyła ma mały bok" po normalizacji → "kobylamamalybok"
// Reversed: "kobylamamalybok" → palindrom!

Testy jednostkowe

[Theory]
[InlineData("kayak", true)]
[InlineData("level", true)]
[InlineData("radar", true)]
[InlineData("Ala", true)]
[InlineData("kobyła ma mały bok", true)]
[InlineData("A man a plan a canal Panama", true)]
[InlineData("hello", false)]
[InlineData("race a car", false)]
public void IsPalindrome_ReturnsCorrectResult(string input, bool expected)
{
    Assert.Equal(expected, IsPalindrome(input));
}

[Theory]
[InlineData(null, false)]
[InlineData("", false)]
[InlineData("   ", false)]
public void IsPalindrome_EmptyOrNull_ReturnsFalse(string? input, bool expected)
{
    Assert.Equal(expected, IsPalindrome(input));
}

[Fact]
public void IsPalindrome_SingleChar_ReturnsTrue()
{
    Assert.True(IsPalindrome("a"));
}

Co powiedzieć na rozmowie

“Przed porównaniem normalizuję wejście — usuwam spacje, interpunkcję i konwertuję na lowercase. Dla wydajności wersja z dwoma wskaźnikami jest lepsza — nie tworzy dodatkowych stringów, sprawdza in-place od obu końców jednocześnie. ToLowerInvariant zamiast ToLower zapewnia deterministyczne wyniki niezależnie od locale systemu.”

Podsumowanie

Palindrom testuje normalizację wejścia i umiejętność wyboru podejścia (odwracanie vs dwa wskaźniki). Metoda dwóch wskaźników jest bardziej elegancka i wydajniejsza pamięciowo — warto ją znać jako standardowy wzorzec dla zadań “porównaj od obu stron”.