0

Daily Challenge #43

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #43
  • Autor: Google
  • Trudność: 5/5
  • Główny problem: dziel i zwyciężaj
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ść

We can determine how “out of order” an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.
Given an array, count the number of inversions it has. Do this faster than O(N^2) time.
You may assume each element in the array is distinct.
For example, a sorted list has zero inversions. The array [2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1), and (4, 3). The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.

Implementacja: testy

[TestMethod]
public void DailyChallenge43()
{
    DailyChallenge43 daily = new DailyChallenge43();
    Assert.AreEqual(10, daily.Proceed( new int[] { 5, 4, 3, 2, 1 }));
    Assert.AreEqual(3, daily.Proceed(new int[] { 2, 4, 1, 3, 5 }));
}

Implementacja: algorytm

public int Proceed(int[] array)
{
    return ProceedIntern(array, new int[array.Length], 0, array.Length - 1);
}
 
private int ProceedIntern(int[] input, int[] temp, int left, int right)
{
    if (right <= left)
    {
        return 0;
    }
    int mid = (right + left) / 2;
    int inversions = ProceedIntern(input, temp, left, mid);
    inversions += ProceedIntern(input, temp, mid +1, right);
    inversions += ProceedIntern(input, temp, left, mid + 1, right);
    return inversions;
}
 
private int ProceedIntern(int[] input, int[] temp, int left, int mid, int right)
{
    int onLeft = left;
    int onRight = mid;
    int mergedIndex = left;
    int inversions = 0;
    while ((onLeft <= mid - 1) && (onRight <= right))
    {
        if (input[onLeft] <= input[onRight])
        {
            temp[mergedIndex++] = input[onLeft++];
        }
        else
        {
            temp[mergedIndex++] = input[onRight++];
            inversions += (mid - onLeft);
        }
    }
    FixArrays(input, temp, left, mid, right, onLeft, onRight, mergedIndex);
    return inversions;
}
 
private void FixArrays(int[] input, int[] temp, int left, int mid, int right, int onLeft,int onRight, int mergedIndex)
{
    while (onLeft <= mid - 1)
    {
        temp[mergedIndex++] = input[onLeft++];
    }
    while (onRight <= right)
    {
        temp[mergedIndex++] = input[onRight++];
    }
    for (onLeft = left; onLeft <= right; onLeft++)
    {
        input[onLeft] = temp[onLeft];
    }
}

Mission Completed

I zrobione, ale dzisiaj Cię trochę oszukałem. Nie zaimplementowałem tego zadanie teraz, zrobiłem to kiedyś bardzo dawno temu, a teraz tylko odkopałem to zadanko. Tak się złożyło, że coś podobnego już kiedyś rozwiązywałem, musiałem to tylko lekko zmodyfikować. Niemniej jednak zadanie to sprawiło mi bardzo dużo trudności wtedy, dlatego przydzieliłem 5 gwiazdek. Nie pamiętam jak doszedłem do rozwiązania, pewnie coś w necie podglądnąłem, ale wiem, że dało mi w kość. Tak więc, przyznaję się bez bicia i przydzielam 5 gwiazdek.

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.