0

Daily Challenge #10

Cześć! Dzisiaj w cyklu Daily Challenge trafiło mi się zadanie, którego twórcą jest Twitter. Zadanie nie było szczególnie trudne, ale wymagało myślenia i znajomości struktur danych, dlatego też wyceniłem to zadnie na 2 gwiazdki.

Tak jak zawsze, kod jest dostępny na GitHubie.

Wpis ten należy do cyklu Daily Challenge. W cyklu tym rozwiązuję każdego dnia nowe zadanie. Zadanie te traktuję w taki sposób, jakbym dostał je na rozmowie kwalifikacyjnej i miał coś wymyślić. Implementuję pierwszą myśl jaka przyjdzie mi do głowy. Nie musi być ona (zazwyczaj nie będzie) najlepszym rozwiązaniem. Chodzi po prostu o zabawę i sprawdzenie jakbym sobie poradził z podobnym wyzwaniem. 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.

Zadanie

Dzisiejsze zadanie brzmi następująco:

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.
For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal]. Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

Natychmiast mi się spodobało, nie wiem sam czemu, może dlatego, że to jakaś odmiana od drzew i intów ;)? Problem pewnie rozwiązany na tysiące sposób w Internecie, ale dla zabawy napisałem to z głowy.

Testy

W przypadku testów, nie byłem zbytnio ambitny. Dokładne przetestowanie tego algorytmu wymagałoby sporo pracy, z założenia na rozmowie kwalifikacyjnej nie miałbym tyle czasu. Ograniczyłem się więc do testowania przykładu:

[TestMethod]
public void DailyChallenge10()
{
    DailyChallenge10 daily = new DailyChallenge10(new string[] { "dog", "deer", "deal" });
    var result = daily.Proceed("de").ToList();
    Assert.IsTrue(result.Contains("deer"));
    Assert.IsTrue(result.Contains("deal"));
    Assert.AreEqual(2, result.Count);
}

Implementacja

W implementacji założyłem, że szybkie ma być wyszukiwanie, a nie tworzenie słownika. Dlatego też, całą robotę zrzuciłem na konstruktor. Na początku podzieliłem słowa na słownik, gdzie indeksem jest pierwszy znak, a następnie posortowałem każdą listę. W rzeczywistym modelu, słowniki mogłyby schodzić do n-tego znaku, ale nie chciałem się tutaj zapuszczać aż tak daleko. Kod prezentuje się następująco:

private Dictionary<char, List<string>> _dictionary = new Dictionary<char, List<string>>();
 
public DailyChallenge10(IEnumerable<string> dictionary)
{
    if (dictionary == null)
    {
        throw new ArgumentNullException(nameof(dictionary));
    }
    foreach (string str in dictionary)
    {
        char firstChar = str[0];
        if (_dictionary.ContainsKey(firstChar) == false)
        {
            _dictionary[firstChar] = new List<string>();
        }
        _dictionary[firstChar].Add(str.ToLower());
    }
    foreach (var value in _dictionary.Values)
    {
        value.Sort(StringComparer.OrdinalIgnoreCase);
    }
}
 
public IEnumerable<string> Proceed(string prefix)
{
    if (string.IsNullOrWhiteSpace(prefix))
    {
        return new string[0];
    }
    if (_dictionary.TryGetValue(prefix[0], out List<string> sortedList) == false)
    {
        return new string[0];
    }
    bool bFound = false;
    List<string> result = new List<string>();
    foreach (string str in sortedList)
    {
        if (str.StartsWith(prefix))
        {
            bFound = false;
            result.Add(str);
        }
        else if (bFound)
        {
            // It's sorted. Remember?
            break;
        }
    }
    return result;
}

Mission Complete

Fajne zadanie, którego rozwiązanie zajęło mi około 5-10 min (łącznie z napisaniem kodu). Tak jak wspomniałem wcześniej, algorytm też nie jest super-optymalny dla wielkiego zbioru, ale powielenie strategii działania tj. podziel i posortuj, może przyspieszyć 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.