0

Daily Challenge #51

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #51
  • Autor: Google
  • Trudność: 2/5
  • Główny problem: znajomość struktur danych
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ść Daily Challenge #51

Implement an LRU (Least Recently Used) cache. It should be able to be initialized with a cache size n, and contain the following methods:
• set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least recently used item.
• get(key): gets the value at key. If no such key exists, return null.
Each operation should run in O(1) time.

Implementacja #51: testy

[TestMethod]
public void DailyChallenge51()
{
    DailyChallenge51<string, int> daily = new DailyChallenge51<string, int>(3);
    daily.Set("a", 1);
    daily.Set("b", 2);
    daily.Set("c", 3);
    Assert.AreEqual(1, daily.Get("a"));
    Assert.AreEqual(2, daily.Get("b"));
    Assert.AreEqual(3, daily.Get("c"));
    daily.Set("a", 4);
    daily.Set("d", 5);
    Assert.AreEqual(4, daily.Get("a"));
    Assert.AreEqual(5, daily.Get("d"));
    Assert.AreEqual(0, daily.Get("b"));
 
    daily.Set("e", 1);
    daily.Set("f", 2);
    daily.Set("g", 3);
    Assert.AreEqual(0, daily.Get("a"));
    Assert.AreEqual(0, daily.Get("d"));
    Assert.AreEqual(0, daily.Get("c"));
}

Implementacja #51: algorytm

public class DailyChallenge51<Key,Value>
{
    private uint _n;
    private LinkedList<KeyValuePair<Key, Value>> _items = new LinkedList<KeyValuePair<Key, Value>>();
    private Dictionary<Key, LinkedListNode<KeyValuePair<Key, Value>>> _cache = new Dictionary<Key, LinkedListNode<KeyValuePair<Key, Value>>>();
 
    public DailyChallenge51(uint n)
    {
        _n = n;
    }
 
    public void Set(Key key, Value value)
    {
        if (_cache.ContainsKey(key))
        {
            _items.Remove(_cache[key]);
            _cache[key] = _items.AddLast(new KeyValuePair<Key, Value>(key, value));
 
        }
        else
        {
            if (_items.Count == _n)
            {
                _cache.Remove(_items.First.Value.Key);
                _items.RemoveFirst();
 
            }
            _cache[key] = _items.AddLast(new KeyValuePair<Key, Value>(key, value));
        }
    }
 
    public Value Get(Key key)
    {
        if (_cache.TryGetValue(key, out LinkedListNode<KeyValuePair<Key, Value>> value) == false)
        {
            return default(Value);
        }
        _items.Remove(value);
        _items.AddLast(value);
        return value.Value.Value;
    }
}

Mission Completed

Po serii “jedynek”, zadanie dosyć ciekawe, ale też nie jakieś wymagające. Wyceniłem na dwie gwiazdki.

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.