0

Daily Challenge #42

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #42
  • Autor: Amazon
  • Trudność: 1/5
  • Główny problem: optymalizacja
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ść

Implement a stack that has the following methods:
• push(val), which pushes an element onto the stack
• pop(), which pops off and returns the topmost element of the stack. If there are no elements in the stack, then it should throw an error or return null.
• max(), which returns the maximum value in the stack currently. If there are no elements in the stack, then it should throw an error or return null.
Each method should run in constant time.

Implementacja: testy

[TestMethod]
public void DailyChallenge42()
{
    DailyChallenge42 daily = new DailyChallenge42();
    daily.Push(1);
    Assert.AreEqual(1, daily.Max());
    daily.Push(-2);
    Assert.AreEqual(1, daily.Max());
    daily.Push(5);
    Assert.AreEqual(5, daily.Max());
    daily.Push(15);
    Assert.AreEqual(15, daily.Max());
    Assert.AreEqual(15, daily.Pop());
    Assert.AreEqual(5, daily.Max());
    Assert.AreEqual(5, daily.Pop());
    Assert.AreEqual(1, daily.Max());
    Assert.AreEqual(-2, daily.Pop());
    Assert.AreEqual(1, daily.Max());
    Assert.AreEqual(1, daily.Pop());
}

Implementacja: algorytm

private class Element
{
    public int Value;
    public int Max;
}
 
private LinkedList<Element> _elements = new LinkedList<Element>();
 
public void Push(int value)
{
    if (_elements.Count == 0)
    {
        _elements.AddLast(new Element() { Value = value, Max = value });
    }
    else
    {
        _elements.AddLast(new Element() { Value = value, Max = Math.Max(value, _elements.Last.Value.Max) }); 
    }
}
 
public int Pop()
{
    if(_elements.Last == null)
    {
        throw new ArgumentNullException();
    }
    Element element = _elements.Last.Value;
    _elements.RemoveLast();
    return element.Value;
}
 
public int Max()
{
    if (_elements.Last == null)
    {
        throw new ArgumentNullException();
    }
    return _elements.Last.Value.Max;
}

Mission Completed

I zrobione, zadanie banalne, może w innym języku stanowiłoby jakieś wyzwanie. W C# nie stanowiło problemu.

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.