0

Daily Challenge #17

Cześć! Dzisiaj w serii pierwsza zadanie, które wyceniłem na 5 gwiazdek oraz takie, które niestety mnie pokonało. Nie dałem rady spełnić wszystkich wymagań w zadaniu. Autorem zadania jest firma Google.

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 ma następująco treść:

Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.

For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:

  • 10 = max(10, 5, 2)
  • 7 = max(5, 2, 7)
  • 8 = max(2, 7, 8)
  • 8 = max(7, 8, 7)

Do this in O(n) time and O(k) space. You can modify the input array in-place and you do not need to store the results. You can simply print them out as you compute them.

Zadanko samo w sobie banalne, gdyby nie ograniczenie czasowe na O(n). To ograniczenie właśnie mnie pokonało, udało mi się osiągnąć O(n*k). W prawdzie napisałem algorytm, który wykonuje zadanie w czasie O(n), ale nie działa dla wszystkich k, więc jest zły.

Testy

Dzisiaj w przypadku testów mam kilka przypadków, ponieważ dosyć długo walczyłem z algorytmem, chciałem sprawdzić każdy przypadek:

[TestMethod]
public void DailyChallenge17()
{
    DailyChallenge17 daily = new DailyChallenge17();
    int[] result = daily.Proceed(new int[] { 10, 5, 2, 7, 8, 7 },3);
    int[] expected = new int[] { 10, 7, 8, 8 };
    for (int i = 0; i < expected.Length; ++i)
    {
        Assert.AreEqual(expected[i], result[i]);
    }
    result = daily.Proceed(new int[] { 10, 5, 2, 7, 8, 7, 12, 9 }, 4);
    expected = new int[] { 10, 8, 8, 12,12 };
    for (int i = 0; i < expected.Length; ++i)
    {
        Assert.AreEqual(expected[i], result[i]);
    }
 
    result = daily.Proceed(new int[] { 10, 5 , 6, 1, 13, 8, 7, 9, 17, 2, 2, 16, 18, 1, 5, 3, 2, 7, 11},5);
    expected = new int[] { 13, 13, 13, 13, 17, 17, 17, 17, 18, 18, 18, 18, 18, 7, 11 };
    for (int i = 0; i < expected.Length; ++i)
    {
        Assert.AreEqual(expected[i], result[i]);
    }
}

oraz kod do sprawdzania złożoności:

[TestMethod]
public void DailyChallenge17_Perf()
{
    DailyChallenge17 daily = new DailyChallenge17();
    int n = 10000000;
    Random random = new Random();
    int[] test_0 = Generate(n);
    int[] test_1 = Generate(n * 2);
    int[] test_2 = Generate(n * 4);
    long sw_0, sw_1, sw_2;
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();
    daily.Proceed(test_0, 12);
    stopwatch.Stop();
    sw_0 = stopwatch.ElapsedMilliseconds;
 
    stopwatch.Reset();
    stopwatch.Start();
    daily.Proceed(test_1, 12);
    stopwatch.Stop();
    sw_1 = stopwatch.ElapsedMilliseconds;
 
    stopwatch.Reset();
    stopwatch.Start();
    daily.Proceed(test_2, 12);
    stopwatch.Stop();
    sw_2 = stopwatch.ElapsedMilliseconds;
 
    Trace.WriteLine($"For {n}: {sw_0} ms");
    Trace.WriteLine($"For {n * 2}: {sw_1} ms");
    Trace.WriteLine($"For {n * 4}: {sw_2} ms");
 
    Trace.WriteLine($"*2, time *{sw_1 / (float)sw_0}");
    Trace.WriteLine($"*4, time *{sw_2 / (float)sw_0}");
 
}
 
private int[] Generate(int n)
{
    Random random = new Random();
    int[] result = new int[n];
    for(int i = 0; i< n; ++i)
    {
        result[i] = random.Next(1, 1000);
    }
    return result;
}

Implementacja

Implementacja podstawowej wersji jest bardzo prosta, prezentuje się tak:

public int[] Proceed(int[] input, int k)
{
    if (k <= 0 || k > input.Length)
    {
        throw new ArgumentOutOfRangeException();
    }
    if (k == 1)
    {
        return input;
    }
    if (k == input.Length)
    {
        return new int[] { input.Max() };
    }
    int[] result = new int[input.Length - k + 1];
    for (int i = 0; i <= input.Length - k; ++i)
    {
        result[i] = input.Skip(i).Take(k).Max();
    }
    return result;
}

Moje próby walki z algorytmem doprowadziły do takiej wersji:

public int[] Proceed(int[] input, int k)
{
    if (k <= 0 || k > input.Length)
    {
        throw new ArgumentOutOfRangeException();
    }
    if (k == 1)
    {
        return input;
    }
    if (k == input.Length)
    {
        return new int[] { input.Max() };
    }
    int[] result = new int[input.Length - k + 1];
    for (int i = k - 2; i >= 0; --i)
    {
        input[i] = Math.Max(input[i], input[i+1]);
        
    }
    result[0] = input[0];
    for(int i = 1; i <= input.Length - k; ++i)
    {
        int last = i + k -1;
        input[i + k - 2] = Math.Max(input[last-1], input[last]);
        if (input[i + k - 2] >= input[i])
        {
            result[i] = input[i + k - 2];
            for(int j = i+1; j < i + k - 2;++j)
            {
                input[j] = result[i];
            }
        }
        else
        {
            result[i] = input[i];
            input[i + 1] = Math.Max(input[i + 1], input[i + k - 2]);
        }
    }
    return result;
}

Druga wersja algorytmu działa jedynie dla k <= 5. Wygenerowałem tablicę z milionem elementów, a następnie porównałem wyniki obydwu algorytmów (z czego wiem, że pierwszy na pewno działa). Dla k większego od 5, algorytm drugi przestawał działać.

Wyniki sprawdzające złożoność obliczeniową zostały umieszczone niżej.

Dla algorytmu I (k = 4, k = 12):

For 10000000: 245 ms
For 20000000: 476 ms
For 40000000: 948 ms
*2, time *1.942857
*4, time *3.869388

For 10000000: 714 ms
For 20000000: 1384 ms
For 40000000: 2741 ms
*2, time *1.938375
*4, time *3.838936

Dla algorytmu II (k = 4, k = 12):

For 10000000: 263 ms
For 20000000: 469 ms
For 40000000: 910 ms
*2, time *1.78327
*4, time *3.460076

For 10000000: 283 ms
For 20000000: 547 ms
For 40000000: 1078 ms
*2, time *1.932862
*4, time *3.809187

Jak widać wersja I ma złożoność O(n*k), ponieważ czas obliczeń przy 3-krotnym zwiększeniu k, wzrósł 3-krotnie. Wersja II charakteryzuje się lepszą złożonością O(n), ale niestety jak wspomniałem wcześniej, algorytm nie działa dla wszystkich k.

Mission Failed

No niestety, zostałem pokonany, co powiem szczerze, bardzo mnie boli. Zadanie wydaje mi się proste, ale coś mi umyka, nie mogę go rozwiązać. Analizowałem to ok. dwóch godzin, ale niestety nic nie wymyśliłem lepszego.

Wskazówka ukrywa się pod stwierdzeniem, że mogę modyfikować tablicę oraz mogę trzymać dodatkowo k rekordów. Może jakaś tablica przesunięć jest tutaj rozwiązaniem? Nie wiem.

Jeżeli Ty masz pomysł jak rozwiązać to zadanie, to daj proszę znać. Jeżeli mnie olśni, to zmodyfikuje wpis.

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.