0

Daily Challenge #8

Cześć i czołem! Jak się masz? Dzisiaj w cyklu Daily Challenge pierwsze zadanie od Airbnb. Nie słyszałem nigdy o tej firmie, ale zadania dają łatwe, gdyż dzisiejsze wyceniłem 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:

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative. For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Tablice i rekurencja… hmm… to już chyba było? Co zrobić, do roboty

Testy

Jak zwykle na początku, napisałem Unit Testy. Testuję przykłady podane w zadaniu oraz dodatkowe, wymyślone przezemnie:

[TestMethod]
public void DailyChallenge8()
{
    DailyChallenge8 daily = new DailyChallenge8();
    Assert.AreEqual(13, daily.Proceed(new int[] { 2, 4, 6, 2, 5 }));
    Assert.AreEqual(10, daily.Proceed(new int[] { 5, 1, 1, 5 }));
    Assert.AreEqual(3, daily.Proceed(new int[] { 1, 1, 1, 1, 1, 1 }));
    Assert.AreEqual(9, daily.Proceed(new int[] { 1, 2, 3, 4, 5, -6 }));
    Assert.AreEqual(9, daily.Proceed(new int[] { 0, 0, 3, 0, 0, 3, 0, 0, 3 }));
}

Implementacja

Rozwiązanie, tradycyjnie już, rozrysowałem sobie na tablicy, co też wyłoniło algorytm:

Implementacja powstała “sama”:

public int Proceed(int[] array)
{
    if (array == null)
    {
        throw new ArgumentNullException(nameof(array));
    }
    return ProceedInternal(array);
}
 
private int ProceedInternal(int[] array)
{
    if (array.Length == 0)
    {
        return 0;
    }
    if (array.Length == 1)
    {
        return array[0];
    }
    if (array.Length == 2)
    {
        return Math.Max(array[0], array[1]);
    }
    int sumFirst = array[0] + ProceedInternal(array.Skip(2).ToArray());
    int sumSecond = array[1] + ProceedInternal(array.Skip(3).ToArray());
    return Math.Max(sumFirst, sumSecond);
}

Mission Complete

Kolejne przyjemne zadanie, które zajmuje około 5 min. Z niecierpliwością czekam na kolejne propozycje, mogą być troszeczkę trudniejsze. 😉

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.