Nasza strona używa cookies. Dowiedz się więcej o celu ich używania i zmianie ustawień w przeglądarce. Korzystając ze strony, wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki. Rozumiem

Struktury danych, algorytmy i skuteczne rozwiązywanie problemów

Fabian Terh Software Engineering Intern (iOS) / Sea
Sprawdź, co musisz wiedzieć o strukturach danych, algorytmach i naucz się lepiej rozwiązywać problemy.
Struktury danych, algorytmy i skuteczne rozwiązywanie problemów

Ten artykuł czerpie z moich osobistych doświadczeń i wyzwań, które podjąłem praktycznie bez znajomości DSA (Digital Signature Algorithm) oraz jakichkolwiek strategii rozwiązywania problemów. Jako programista samouk, byłem o wiele bardziej zaznajomiony z programowaniem ogólnym, takim jak programowanie obiektowe, niż z umiejętnościami rozwiązywania problemów wymaganymi do pracy z DSA.

Wpis ten odzwierciedla również moją podróż przez cały semestr szkolny oraz zasoby, które wykorzystałem, by rozszerzyć swoją wiedzę o strukturach danych, algorytmach i poprawić umiejętność rozwiązywania problemów.


Znasz teorię, ale nie możesz jej wykorzystać w praktyce

Problem ten napotkałem już na początku semestru, kiedy nie byłem świadomy braków w mojej wiedzy. W miarę dobrze rozumiałem wtedy teorię, np. wiedziałem, czym jest i jak działa lista, znałem jej różne operacje i ich złożoność obliczeniową, obsługiwane przez nią ADT (abstrakcyjne typy danych) i jak operacje ADT zostały zaimplementowane. Jednak ze względu na własną nieświadomość, nie wiedziałem jak mogę wykorzystać listę w praktyce.


Różne rodzaje pytań

Przykład pytania dotyczącego struktur danych: opisz, jak wstawić węzeł w liście i określ złożoność obliczeniową.

A oto pytanie dotyczące algorytmów: wyszukaj element w zrotowanej i posortowanej tablicy oraz określ złożoność obliczeniową.

I na koniec pytanie dotyczące rozwiązywania problemów, które moim zdaniem jest bardziej wysokopoziomowe niż dwa poprzednie. Może krótko opiszę scenariusz i wymienię wymagania dotyczące problemu: w programowaniu konkurencyjnym może być konieczne przesłanie działającego kodu bez jawnego podawania struktur danych lub algorytmów. Innymi słowy, oczekuje się zastosowania najbardziej odpowiednich struktur danych i algorytmów, aby rozwiązać problem tak skutecznie, jak to możliwe.


Jak możesz ulepszyć swoje struktury danych, algorytmy i umiejętności rozwiązywania problemów?

Do ćwiczeń używam głównie trzech stron internetowych: HackerRank, LeetCode i Kattis. Są one w dużej mierze podobne, zwłaszcza pierwsze dwie. Każda strona skupia się jednak na czymś innym, co sprawia, że są one pomocne na swój wyjątkowy sposób.

Wyróżniłbym 3 typy umiejętności wymaganych do skutecznego rozwiązywania problemów:

  1. Znajomość struktur danych
  2. Znajomość algorytmów
  3. Wiedza, jak zastosować dwa powyższe w praktyce


Pierwsze dwa typy można uznać za "pierwotne" lub za bloki konstrukcyjne, które są podstawą dla trzeciego, który polega na dopasowaniu się do danego scenariusza. 


Znajomość struktur danych

Pod tym względem uznałem HackerRank za cenne źródło. Strona ta posiada bowiem sekcję poświęconą strukturom danych, którą można filtrować według typu takiego jak tablice, listy, (zrównoważone) drzewa, sterty itd.

Pytania dotyczą nie tyle rozwiązywania problemów, co pracy ze strukturami danych. Np.:

  1. Tablice: rotacja tablic, manipulacja tablicami
  2. Listy: odwracanie listy, wykrywanie cyklu
  3. Drzewa: zamiana węzłów, walidacja drzewa BST


Tak to właśnie wygląda. Niektóre pytania mogą nie mieć bezpośredniego zastosowania w rozwiązywaniu problemów, ale są świetne do zrozumienia pojęć, co jest niezwykle ważne.

HackerRank nie ma ogólnodostępnych „rozwiązań modelowych”, chociaż sekcja dyskusji jest zwykle pełna aluzji, wskazówek, a nawet działających fragmentów kodu. Do tej pory uważam, że są one zadowalające, chociaż być może będziesz musiał przejść przez kod linijka po linijce w IDE, aby naprawdę coś zrozumieć.


Znajomość algorytmów

HackerRank ma również sekcję dotyczącą algorytmów, chociaż wolę do tego LeetCode. Odkryłem, że różnorodność problemów LeetCode jest znacznie większa i bardzo podoba mi się, że wiele z nich posiada rozwiązania z wyjaśnieniem, a nawet złożoność obliczeniową.

Świetnym punktem wyjścia byłoby "100 najpopularniejszych pytań LeetCode". Oto niektóre z nich:


W przeciwieństwie do pytań dotyczących struktur danych, nie tyle chodzi o pracę z lub manipulację nimi, ale o to, w jaki sposób coś rozwiązać. Np. problem „łączenia kont” dotyczy przede wszystkim stosowania standardowych algorytmów UFDS, a problem „wyszukiwania wartości w zrotowanej i posortowanej tablicy” stanowi wariację problemu wyszukiwania binarnego. Z czasem uczysz się zupełnie nowych technik rozwiązywania problemów, tak jak w przypadku „techniki przesuwanego okna” dla problemu „znalezienia najdłuższej sekwencji rosnących liczb”.


Jak zastosować struktury danych i algorytmy w praktyce

Do poprawienia swoich ogólnych umiejętności rozwiązywania problemów używam Archiwum problemów Kattis. Zawiera ono wiele komplikacji programistycznych z różnych źródeł, np. z konkursów programistycznych na całym świecie. 

Kattis może być jednak niezwykle frustrujący, ponieważ nie ma tam sekcji rozwiązań ani żadnego forum dyskusyjnego (w przeciwieństwie do HackerRank i LeetCode). Ponadto, testy są prywatne. Mam tam sporo nierozwiązanych problemów, ponieważ po prostu nie mogę wykryć błędu.

Spośród tych trzech, Kattis lubię najmniej, jeżeli chodzi o ćwiczenia i naukę. Nie spędziłem na niej jednak aż tak dużo czasu.


Inne źródła

Geeksforgeeks to kolejne bardzo cenne źródło informacji o strukturach danych i algorytmach. Podoba mi się, że podawane są tam fragmenty kodu w różnych językach, zwykle w C ++, Java i Python. Można je skopiować i wkleić do swojego IDE, aby analizować kod linijka po linijce.

Na koniec mamy nasze stare dobre Google, które pewnie zaprowadziłoby Cię do GeeksForGeeks, albo do Youtube'a w celu uzyskania wizualnych wyjaśnień.


Podsumowanie

Ostatecznie jednak nie zawsze można chodzić na skróty. Musisz zacząć pisać, debugować i czytać poprawny kod innych ludzi, aby dowiedzieć się gdzie, jak i dlaczego coś jest niepoprawne. To może być trudne, ale im więcej prób, tym lepiej. 

Nie jestem jeszcze blisko poziomu, na którym chcę być, ale zdecydowanie przeszedłem już długą drogę, odkąd zacząłem. :)

Lubisz dzielić się wiedzą i chcesz zostać autorem?

Podziel się wiedzą z 130 tysiącami naszych czytelników

Dowiedz się więcej