0

Daily Challenge #2

Poniedziałek… czas na kolejne wyzwanie. Z racji, że w niedzielę nie przesiaduję przy komputerze, to na dzisiaj przypadnie realizacja kolejnego zadania z serii Daily Coding Problem. Dzisiejsze zadanie zostało zaproponowane przez Stripe. Przyznam, że dało mi w kość. Samo w sobie nie było trudne jak już zrozumiało się jedną ważną rzecz, ale zrozumienie tej rzeczy zajęło mi trochę czasu. Zadanie wyceniłem na 3 gwiazdki (było trochę trudniejsze od sobotniego).

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

Treść dzisiejszego zadania prezentuje się następująco:

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3. You can modify the input array in-place.

Zadanie wydawałoby się banalne, gdyby nie ograniczenia: liniowy czas i stała przestrzeń. Liniowy czas oznacza, że algorytm może mieć co najwyżej złożoność O(N). Czyli wszystkie algorytmy sortowania z miejsca odpadają. Dodatkowo stałe wykorzystanie RAM też mocno ogranicza pole działania, bo nie mogę posiłkować się inną tablicą.

A jednak jest jeden szczegół, który powoduje, że zadanie da się rozwiązać. Zadajmy sobie dwa pytania. Jaki może być najmniejszy możliwy wynik? Jaki może być największy możliwy wynik?

Odpowiedź na pierwsze jest oczywista. Taką liczbą może być liczba 1.

Odpowiedź na drugie jest bardziej złożona. Ale czy na pewno?  Jaka może być następna liczba całkowita z przekazanej tabeli o jakiejś długości? A no liczbą tą będzie co najwyżej Array.Lenght + 1. Dlaczego? Jeżeli wszystkie elementy w tabeli będą wypełniały dany przedział liczb całkowitych i pierwszą liczbą będzie 1, to wynikiem może być tylko liczba znajdująca się za ostatnią (w kolejności) liczbą z tabeli. To jest graniczny scenariusz. Z reguły liczba ta będzie na pewno mniejsza niż liczba elementów tablicy – jeżeli liczby nie zajmują całego przedziału, to w środku jest gdzieś luka. Luka ta będzie na pewno miała wartość mniejsza niż długość tablicy.

Przykłady

Przykłady (dla ułatwienia posortowane):

  • [0,1,2,3,4] => 5 – przypadek graniczny do maksa.
  • [-4,1,2,9] => 3 – luka zawsze przypada na liczbę o wartości mniejszej niżeli wielkość tablicy.
  • [3,4,6] => 1 – przypadek graniczny do minimum.

To rozumowanie prowadzi do jednego wniosku. Sprawdzając każdy z elementów tablicy, możemy go umieścić w tablicy na indexie o wartości liczby pomniejszonej przez 1. Czyli element o wartości 3 umieścilibyśmy na indexie 2. Oczywiście ma to sens tylko dla liczb większych od 0 i mniejszych od Array.Lenght. Trzeba jednak przy tym pamiętać, aby nie nadpisać ważnych danych.

Przejdźmy zatem do implementacji.

Testy

Na początku powstały testy sprawdzające algorytm:

[TestMethod]
public void DailyChallenge2()
{
    DailyChallenge2 model = new DailyChallenge2();
    Assert.AreEqual(2, model.Proceed(new int[] { 3, 4, -1, 1 }));
    Assert.AreEqual(3, model.Proceed(new int[] { 1, 2, 0 }));
    Assert.AreEqual(4, model.Proceed(new int[] { 1, 3, 2, 7, 6, -2, 5, -123, 24, 1, 5, 0 }));
    Assert.AreEqual(5, model.Proceed(new int[] { 3, 2, 4, -1, 1 }));
    Assert.AreEqual(5, model.Proceed(new int[] { 1, 2, 3, 4 }));
    Assert.AreEqual(1, model.Proceed(new int[] { -1, 4, 4, -4 }));
    Assert.AreEqual(1, model.Proceed(new int[] { 2, 2, 2, 2 }));
    Assert.AreEqual(1, model.Proceed(new int[] { 3, 2, 3, 2 }));
}

Tutaj ważny jest szczególnie 4 przypadek, który rozwala implementacje, który znaleźć można w Internecie. Pierwsza moja wersja algorytmu też się na tym wykładała, ciekawy byłem, czy ktoś popełnił taki błąd i nie sprawdził. Tak też było 😉

Implementacja

Algorytm rozwiązujący problem wygląda następująco:

public int Proceed(int[] input)
{
    int index = 0;
    foreach (int value in input)
    {
        CorrectValue(value, input, index++);
    }
    for (int i = 0; i < input.Length; ++i)
    {
        if (input[i] != i + 1)
        {
            return i + 1;
        }
    }
    return input.Length + 1;
}
 
private void CorrectValue(int value, int[] input, int previousIndex)
{
    if (value <= 0 || value > input.Length || input[value - 1] == value)
    {
        return;
    }
    int index = value - 1;
    int temp = input[index];
    int tempIndex = temp - 1;
    if (tempIndex == previousIndex)
    {
        // Break infinity loop caused by changing the same pair
        input[index] = value;
        input[previousIndex] = temp;
        return;
    }
    if (temp > 0 && temp <= input.Length)
    {
        // Do not replace important data
        CorrectValue(temp, input, tempIndex);
    }
    input[index] = value;
}

Złamię trochę tradycję i wytłumaczę część kodu, bo może nie być to oczywiste.

Działanie przebiega w dwóch etapach. Pierwszym jest przystosowanie tablicy, drugim znalezienie odpowiedniej wartości. Drugi etap pominę, bo jest banalny – poszukuję pierwszego inta, który nie występuje na swoim miejscu w tablicy.

Pierwszy etap jest ciekawy. Umieszczam element na odpowiednim indeksie, ale tutaj są dwa problemy:

  1. Zauważony podczas planowania: nie nadpisać danych, które mogą mieć znaczenie.
  2. Zauważony w testach po zaimplementowaniu fixa na pkt a): nie doprowadzić do nieskończonej pętli zamieniając dwa takie same elementy.

Rozwiązaniem problemu a) okazała się rekurencja. Nie zamieniam elementu dopóki nie jest to istotny element. Rekurencja niestety spowodowała nieskończoną pętlę. Ratuję się przed tym sprawdzając czy przypadkiem pary elementów nie mogę zamienić od ręki.

Algorytm przechodzi wszystkie przypadki testowe.

Mission Complete

Zadanie było jak dla mnie trudne. Nie dość, że ograniczenia były dość rygorystyczne, to jeszcze posiadało ukryte problemy, które wypłynęły dopiero przy implementacji. Nie wiem czy było to zamierzone, jak tak, to brawo dla osoby układającej to zadanie.

Trochę się obawiam, że moje rozwiązanie też ma luki, jak takie widzisz to daj znać. Ja ze swojej strony napisałem wszystkie UT, jakie przyszły mi do głowy.

Swoją drogą widać tutaj potęgi UT, bez których nie wykryłbym problemu z przypadkiem b).

Implementacja zadania zajęło mi coś koło 30 min (tak wiem, długo, na rozmowie pewnie bym już oblał :0). Wyceniłem je na 3 gwiazdki, chociaż nie wiem czy nie powinno być więcej, ale nie chcę w przyszłości zwiększać skali bo się okaże, że trafi mi się jakiś potwór 😉.

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.