0

Daily Challenge #45

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #45
  • Autor: Amazon
  • Trudność: 2/5
  • Główny problem: rekurencja
Wpis ten należy do cyklu Daily Challenge. Od poniedziałku do piątku, codziennie, o 7:30 publikuję rozwiązanie jednego zadania. Zadania rozwiązywane w ramach tego cyklu są zadaniami przeznaczonymi na rozmowy kwalifikacyjne. Są treściwe, krótkie i wymagają jakichś konkretnych umiejętności. Przedstawione problemy realizuję właśnie w ten sposób. Nie wymyślam najlepszego algorytmu, nie optymalizuję ani refaktoryzuję kodu, tylko implementuję pierwszą myśl. Robię to dla zabawy i chęci sprawdzenia swoich możliwości. Zaimplementowane rozwiązanie nie jest z reguły tłumaczone, jeżeli masz pytania możesz je zadawać w komentarzach. Wszystkie zadania udostępniane są subskrybentom Daily Coding Problem. Moje implementacje (również tego zadania) dostępne są na GitHubie. Pamiętaj, że implementacje przedstawione w ramach tego cyklu nie nadają się do kodu produkcyjnego, traktuj to bardziej jako ‘proof of concept’.

Treść

Given a string, find the longest palindromic contiguous substring. If there are more than one with the maximum length, return any one.
For example, the longest palindromic substring of “aabcdcb” is “bcdcb”. The longest palindromic substring of “bananas” is “anana”.

Implementacja: testy

[TestMethod]
public void DailyChallenge45()
{
    DailyChallenge45 daily = new DailyChallenge45();
    Assert.AreEqual("bcdcb", daily.Proceed("aabcdcb"));
    Assert.AreEqual("anana", daily.Proceed("bananas"));
}

Implementacja: algorytm

public string Proceed(string text)
{
    if (IsPalindrom(text))
    {
        return text;
    }
    return ProceedIntern(text, null);
}
 
private string ProceedIntern(string text, bool? onRight)
{
    if (text.Length <= 1)
    {
        return text;
    }
    string strLeft = text.Substring(0, text.Length - 1);
    if (IsPalindrom(strLeft))
    {
        return strLeft;
    }
    string strRight = text.Substring(1, text.Length - 1);
    if (IsPalindrom(strRight))
    {
        return strRight;
    }
    string rightPalindrom = string.Empty;
    string leftPalindrom = string.Empty;
    if (onRight.HasValue == false || onRight.Value)
    {
        rightPalindrom = ProceedIntern(strRight, true);
    }
    if (onRight.HasValue == false || onRight.Value == false)
    {
        leftPalindrom = ProceedIntern(strLeft, false);
    }
    return leftPalindrom.Length > rightPalindrom.Length ? leftPalindrom : rightPalindrom;
}
 
private bool IsPalindrom(string text)
{
    int l = 0;
    int h = text.Length - 1;
    while (text[l] == text[h])
    {
        if (l >= h)
        {
            // palindrom
            return true;
        }
        l++;
        h--;
    }
    return false;
}

Mission Completed

No i zrobione. Podobne zadanie już kiedyś było, ale tam chyba chodziło o utworzenie palindromu, no generalnie to było łatwiejsze. Dwie gwiazdki, bo jednak musiałem rozpisać sobie na tablicy. Jak mogłeś zauważyć, algorytm jest zoptymalizowany, aby nie rozwijać wszystkich w prawo i w lewo, gdyż ciągi znaków się powtarzają. Bez optymalizacji byłby czytelniejszy.

Jeżeli Ty chciałbyś podesłać jakieś ciekawe zadanie, to nie krępuj się proszę i ślij na p.bogdanski@devmight.pl. Pamiętaj, że zadanie powinno nadawać się na rozmowę kwalifikacyjną, więc nie może to być problem, którego rozwiązanie zajmuje kilka godzin. Dzięki!

Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.