Kategorie
Junior Developer

Trywialny problem rozgrzewkowy?

Na co możesz trafić na początku rozmowy kwalifikacyjnej? Może być to jakieś małe zadanie na rozgrzewkę. Tak, żeby wejść na właściwe tory. Podrzucam Ci jeden temat. Powiesz, że trywialny? Ok, mam nadzieję, że tak będzie.

Lecimy!

junior-hava-developer-handbook-what-to-know

Problem do rozwiązania

Ustalmy na wstępie. To zadanie jest proste. Jest to problem rozgrzewkowy. Także możesz założyć, że od razu stwierdzisz coś w rodzaju: hey, ale to jest banał, to przecież jest mega proste.

Ok, zadanie wygląda następująco:

Pewnie znasz podstawy geometrii.

Wyobraź sobie, że w pewnym miejscu przestrzeni masz wybrany punkt główny. Poza tym w przestrzeni jest mnóstwo innych punktów.

Twoim zadaniem jest napisanie metody, która znajdzie najbliższy punkt w przestrzeni względem punktu głównego.

Załóżmy, że mówimy o przestrzeni dwuwymiarowej.

Co powiesz? Prawda, że proste?

Co oceniam w tym zadaniu?

Tak, jak pisałem wcześniej w Oceniam zadanie rekrutacyjne Junior Programista istotnych jest tutaj kilka czynników:

  • dekompozycja problemu,
  • jasność opisywania kodu,
  • umiejętności kodowania,
  • ogólne działanie rozwiązania i kierunki do poprawy.

Dekompozycja

Wydaje się, że nie ma specjalnie co się zastanawiać:

  • Po pierwsze określamy wygląd naszej metody.
  • W dalszej kolejności zastanawiamy się, jak znaleźć odpowiedni punkt spełanijący kryteria zadania.

Wejście i wyjście

Przykładowa metoda może wyglądać następująco:

  public BestResult findNearestPoint(Point[] points, Point mainPoint) {
    // ...
  }

Do reprezentacji punktów w przestrzeni dwuwymiarowej utworzymy sobie taki rekord:

public record Point(double x, double y) {
}

Z kolei nasz wynik to odnaleziony najbliższy punkt oraz jego odległość od naszego punktu głównego:

public record BestResult(Point point, double result) {
}

Którego punktu szukamy?

Dobra… generalnie chciałbym w tym miejscu wprowadzić u Ciebie lekką wątpliwość. Tak, to zadanie jest proste. Jednak nawet w nim jest pewien haczyk.

Ale zacznijmy od początku. Wizualizacja naszej przestrzeni może wyglądać następująco:

Nie odkryjemy Ameryki stwierdzając, że:

A samą odległość między punktami możemy obliczyć dzięki pomocy twierdzenia Pitagorasa. Czyli będzie ona pierwiastkiem z sumy kwadratów a i b.

Rozwiązanie przychodzące od razu do głowy

Pierwsze rozwiązanie niczym nie zaskakuje:

  public BestResult findNearestPoint(Point[] points, Point mainPoint) {
    BestResult bestResult = new BestResult(null, Double.MAX_VALUE); // (1)

    for (int i = 0; i < points.length; i++) { // (2)
      Point current = points[i];

      double distance = Math.sqrt(
          Math.pow(current.x() - mainPoint.x(), 2) + Math.pow(current.y() - mainPoint.y(), 2)
      ); // (3)

      if (distance < bestResult.result()) { // (4)
        bestResult = new BestResult(current, distance); // (5)
      }
    }

    return bestResult;
  }

Ustawiamy początkowy wynik na maksymalną wartość dla typu double (1). Iterujemy po tablicy punktów (2). Dla każdego punktu wyznaczamy odległość od punktu głównego (3). Jeśli okaże się ona mniejsza od obecnego wyniku (4), to zmieniamy wynik na bieżący (5).

Wygląda dobrze. I tak też działa. Zadanie możemy uznać za rozwiązane.

Rozwiązanie bardziej optymalne?

Generalnie pierwsze rozwiązanie jest ok. Działa dobrze. Ale na rozmowie kwalifikacyjnej możesz trafić na pytanie: Ale czy Twoim zdaniem dałoby się coś z tego rozwiązania jeszcze wycisnąć?

(przemyśl to teraz przez kilka sekund)

A to rozwiązanie wygląda następująco:

  public BestResult findNearestPoint(Point[] points, Point mainPoint) {
    BestResult bestResult = new BestResult(null, Double.MAX_VALUE);

    for (int i = 0; i < points.length; i++) {
      Point current = points[i];

      double result =
          Math.pow(current.x() - mainPoint.x(), 2) + Math.pow(current.y() - mainPoint.y(), 2); // (1)

      if (result < bestResult.result()) {
        bestResult = new BestResult(current, result);
      }
    }

    return Objects.nonNull(bestResult.point()) ?
        new BestResult(bestResult.point(), Math.sqrt(bestResult.result())) :
        bestResult; // (2)
  }

Różnica jest minimalna i prawie niewidoczna na pierwszy rzut oka. Mały szczegół.

Która z operacji w rozwiązaniu pierwszym może obciążać procesor i jest niepotrzebna?

W ramach wyliczenia odległości korzystamy z pierwiastka kwadratowego. To daje oczywiście dobry wynik, ale… jest zupełnie niepotrzebne.

Dlaczego?

Przede wszystkim w zadaniu należy nam na znalezieniu najbliższego punktu. Do znalezienia najbliższego punktu nie potrzebujemy znać odległości.

Odległość c otrzymujemy wyliczając pierwiastek kwadratowy z c2. Ale jeśli dla wszystkich punktów będziemy porównywać wyłącznie c2 to też znajdziemy najbliższy punkt. Bez konieczności pierwiatkowania.

Tym sposobem szukamy tego parametru (1) i dopiero na końcu, jak już mamy go znaleziony, obliczamy odległość do punktu (2). Czyli korzystamy z Math.sqrt(…) tylko raz.

Serio? A jaka jest różnica?

Na moim laptopie robiąc tę minimalną zmianę możemy uzyskać rozwiązanie o prawie 8,5% lepsze pod względem czasu wykonania tego algorytmu.

Przeprowadziłem mały test.

Pierwsze rozwiązanie wypadło tak:

Number of points: 200000000
Main point: Point[x=13839.0, y=36418.0]
Nearest point: Point[x=13842.0, y=36417.0]
Distance: 3.1622776601683795
Nanoseconds: 554692500

A drugie:

Number of points: 200000000
Main point: Point[x=13839.0, y=36418.0]
Nearest point: Point[x=13842.0, y=36417.0]
Distance: 3.1622776601683795
Nanoseconds: 507609900

Widać, że różnica w czasie wykonania na wstępnie wygrzanej maszynie JVM wyniosła 47082600 ns. Czyli drugie rozwiązanie było o prawie 8,5% lepsze.

Podsumowanie

Czy da się napisać to w Javie jeszcze efektywniej? Pewnie tak.

Ideą tego problemu jest zastanowienie się nad sensem problemu. Okazuje się, że instynktowne pierwsze rozwiązanie ma jednak niepotrzebną operację, która je spowalnia.

A teraz wyobraź sobie, że przetwarzana jest nie jedna tablica punktów dwuwymiarowych, a wiele różnorodnych tablic obiektów w przestrzeni trójwymiarowej. Na przykład w grze. Czy teraz widzisz różnicę i potrzebę optymalizacji?

Tak na marginesie, w aplikacjach korporacyjnych zwykle nie będziesz miał do czynienia z takimi optymalizacjami. Chyba, że będziesz pracować z JPA, wtedy zoptymalizujesz zapytania SQL, które będą jeszcze bardziej nieefektywne 😊

Skoro dotarłeś do końca artykułu to znaczy, że jego treść jest dla Ciebie pomocna i wartościowa. Mam prośbę, zostaw komentarz ze swoimi przemyśleniami lub oceń artykuł za pomocą gwiazdek na końcu (jeśli się podobał to daj 5, a jeśli nie to też 5 😁).

A jeśli chcesz poczytać o innym zadaniu rekrutacyjnym, to zapraszam do artykułu Oceniam zadanie rekrutacyjne Junior Programista.

W serii Junior Developer ukazały się następujące wpisy:

  1. Junior Developer w 2020 roku
  2. Top 10 umiejętności Junior Java Developera
  3. Junior Developer a Regular
  4. Co tak naprawdę sprawdza rozmowa kwalifikacyjna na stanowisko Junior Developer?
  5. Junior Developer 2020 – Podsumowanie

4.9 7 votes
Article Rating
Subscribe
Powiadom o
guest
2 komentarzy
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
kcybulski
kcybulski
2 miesięcy temu

Warto zacząć od dokładnego ustalenia wymagań oraz dostępnych danych:

  1. W jaki sposób dane są dostarczone? Czy to jest lista w pamięci czy musimy je jakoś pobrać?
  2. Jakiej dokładności oczekujemy? Może nie zawsze musimy odpowiadać najlepszym rozwiązaniem
  3. Czy dane są w jakiś sposób posortowane? Jeśli tak to w jaki?
  4. Co to znaczy „mnóstwo innych punktów”? To są setki czy miliardy?
  5. Czy będziemy tylko raz wyszukiwali najbliższego punktu na tych danych? Czy operacja będzie powtarzana?
  6. Co jeśli znajdziemy dwa takie punkty? Czy to może się zdarzyć?

Mając te odpowiedzi może zwykła pętla nie będzie jednak najlepszym rozwiązaniem 🙂

Last edited 2 miesięcy temu by kcybulski