0

Daily Challenge #15

Witaj w serii Daily Challenge! Dzisiaj rozwiążemy zadanie od firmy Twitter, które wyceniłem na 2 gwiazdki, tylko 2, ponieważ w języku C# implementacja nie była kłopotem.

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:

You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

  • record(order_id): adds the order_id to the log
  • get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N.

You should be as efficient with time and space as possible.

Wyjaśnię tylko, że założyłem działanie w trybie ciągłym tj. jak uruchomię aplikację to żyje ona przez cały czas. Jeżeli aplikacja miałaby trzymać coś na dysku, to potrzebne byłyby metody zapisujące i wczytujące dane z dysku. Autor zadania tego nie nakazał, więc tego nie robiłem.

Testy

Po poprzednich zadaniach – gdzie nie było testów – czas wrócić do tradycji i utworzyć metodę testową dla przyszłego kodu. Metoda testuje podstawowe funkcje (aż 2), nie sprawdza zajętości pamięci i czasu (co wydaje mi się logiczne). Kod metody testowej wygląda tak:

[TestMethod]
public void DailyChallenge15()
{
    DailyChallenge15 daily = new DailyChallenge15(10);
    daily.Record(new Order { ID = Guid.NewGuid() });
    daily.Record(new Order { ID = Guid.NewGuid() });
    daily.Record(new Order { ID = Guid.NewGuid() });
    daily.Record(new Order { ID = Guid.NewGuid() });
    Assert.AreEqual(4, daily.GetLast(10).Length);
    daily.Record(new Order { ID = Guid.NewGuid() });
    daily.Record(new Order { ID = Guid.NewGuid() });
    Assert.AreEqual(6, daily.GetLast(6).Length);
    Assert.AreEqual(3, daily.GetLast(3).Length);
    Guid lastGuid = Guid.NewGuid();
    daily.Record(new Order { ID = lastGuid });
    Assert.AreEqual(lastGuid, daily.GetLast(1)[0].ID);
}

Implementacja

Jak wspomniałem we wstępie, rozwiązanie zadania w C# jest stosunkowo proste, a to dlatego, że w bibliotekach standardowych jest potrzebna nam struktura danych. To, że tam jest nie znaczy, że wiadomo, której użyć.

Kod miał być tak efektywny pamięciowo i wydajnościowo jak się da. Do takich zadań nadaje się LinkedList, a to dlatego, że:

  • dodawanie elementów ma złożoność O(1),
  • usuwanie elementów ma złożoność O(1).

Czyli nie ważne ile ostatnich rekordów chcemy trzymać, dodawanie nowego zawsze zajmie tyle samo czasu , a wszystkie rekordy zajmą tylko tyle pamięci ile potrzebują.

Na potrzeby zadania utworzyłem prostą klasę Order, można ją rozszerzać, ale na potrzeby zadanie wystarczy tylko właściwość ID. Kod prezentuje się następująco:

public class Order
{
    public Guid ID { get; set; }
}
 
LinkedList<Order> _orders = new LinkedList<Order>();
private readonly int _limit;
private int _records;
 
public DailyChallenge15(int n)
{
    _limit = n;
    _records = 0;
}
 
public void Record(Order order)
{
    _records++;
    _orders.AddFirst(order);
    if (_records > _limit)
    {
        _orders.RemoveLast();
    }
}
 
public Order[] GetLast(int i)
{
    return _orders.Take(i).ToArray();
}

Mission Complete

Kolejne “przyjemne” zadanie rozwiązane. Główny problem polegał na znalezieniu struktury danych, chociaż z drugiej strony, jeżeli czytasz moją serię o algorytmach i strukturach danych to nie powinieneś mieć z tym problemów. Jeżeli takiej struktury nie dostarczałby .NET, to trudność byłaby większa.

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.