0

Daily Challenge #21

Witaj! Nowy tydzień, nowe zadanie. Z dniem dzisiejszym zmianie ulega forma prezentacji.

  • Zadanie numer: #21
  • Autor: Microsoft
  • 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ę kodu do granic możliwości, 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.

Treść

Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list. If there is more than one possible reconstruction, return any of them. If there is no possible reconstruction, then return null.
For example, given the set of words ‘quick’, ‘brown’, ‘the’, ‘fox’, and the string “thequickbrownfox”, you should return [‘the’, ‘quick’, ‘brown’, ‘fox’].
Given the set of words ‘bed’, ‘bath’, ‘bedbath’, ‘and’, ‘beyond’, and the string “bedbathandbeyond”, return either [‘bed’, ‘bath’, ‘and’, ‘beyond] or [‘bedbath’, ‘and’, ‘beyond’].

Implementacja: testy

[TestMethod]
public void DailyChallenge21()
{
    DailyChallenge21 daily = new DailyChallenge21();
    string[] result = daily.Proceed("thequickbrownfox", new string[] { "quick", "brown", "the", "fox" });
    Assert.IsTrue(IsEqual(new string[] { "the", "quick", "brown", "fox" }, result));
    result = daily.Proceed("bedbathandbeyond", new string[] { "bed", "bath", "bedbath", "and", "beyond" });
    Assert.IsTrue(IsAnyEqual(new List<string[]>
    {
        new string[] { "bed", "bath", "and", "beyond" },
        new string[] { "bedbath", "and", "beyond" }
    }, result));
}
 
private bool IsEqual(string[] expected, string[] current)
{
    if (expected.Length != current.Length)
    {
        return false;
    }
    for(int i = 0; i< expected.Length;++i)
    {
        if (expected[i] != current[i])
        {
            return false;
        }
    }
    return true;
}
 
private bool IsAnyEqual(IEnumerable<string[]> expected, string[] current)
{
    foreach(var e in expected)
    {
        if (IsEqual(e, current))
        {
            return true;
        }
    }
    return false;
}

Implementacja: algorytm

public string[] Proceed(string strText, IEnumerable<string> set)
{
    LinkedList<string> result = new LinkedList<string>();
    if (ProceedIntern(strText, set.ToList(), result))
    {
        return result.ToArray();
    }
    return null;
}
 
private bool ProceedIntern(string strText, List<string> leftWords, LinkedList<string> result)
{
    if (strText.Length == 0)
    {
        return true;
    }
    foreach(string word in leftWords)
    {
        if (strText.StartsWith(word))
        {
            result.AddLast(word);
            if (ProceedIntern(strText.Substring(word.Length), leftWords.Except(new string[] { word}).ToList(), result))
            {
                return true;
            }
            result.RemoveLast();
        }
    }
    return false;
}

Mission Completed

Zadanie wymagało skorzystanie z rekurencji, poza tym nie było w tym nic skomplikowanego, dłużej pisałem przypadki testowy niżeli sam algorytm ;).

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.