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!
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:
- Junior Developer w 2020 roku
- Top 10 umiejętności Junior Java Developera
- Junior Developer a Regular
- Co tak naprawdę sprawdza rozmowa kwalifikacyjna na stanowisko Junior Developer?
- Junior Developer 2020 – Podsumowanie
Warto zacząć od dokładnego ustalenia wymagań oraz dostępnych danych:
Mając te odpowiedzi może zwykła pętla nie będzie jednak najlepszym rozwiązaniem 🙂
Bardzo fajne pytania! Moim zdaniem są mega! Jestem ciekawy, jakie inne rozwiązanie przychodzi Ci do głowy w kontekście możliwych odpowiedzi?