20 zadań z zakresu list, które możesz dostać podczas rekrutacji

Często dzielę się potencjalnymi pytaniami rekrutacyjnymi z programistami, którzy aktywnie poszukują pracy. Szczególnie pytaniami dla początkujących i inżynierów komputerowych, którzy właśnie ukończyli studia, ale nie mają prawdziwego doświadczenia zawodowego. Dziś podzielę się listą często zadawanych podczas rozmów kwalifikacyjnych zadań z kodowania list.

Struktury danych są jedną z najważniejszych części rozmowy kwalifikacyjnej i to na ich podstawie często zapada decyzja o zatrudnieniu kandydata, dlatego też ćwiczenie zadań z zakresu struktur danych da Ci przewagę nad konkurentami. Uczyni Cię również lepszym programistą, ponieważ rozwiązując takie zadania, rozwijasz zmysł do logiki i kodowania.

Co to jest lista?

Lista jest powszechną strukturą danych, która uzupełnia strukturę danych tablicy. Podobnie jak tablica,również jest to liniowa struktura danych i w liniowy sposób przechowuje elementy. Jednak w odróżnieniu od tablicy, nie przechowuje ich w sąsiednich lokalizacjach. Zamiast tego są one rozproszone w pamięci i są powiązane ze sobą za pomocą węzłów.

Lista jest niczym innym jak listą węzłów, gdzie każdy węzeł zawiera zapisaną wartość i adres następnego węzła.

Ze względu na taką strukturę, łatwo jest dodawać i usuwać elementy z listy, ponieważ wystarczy zmienić link zamiast tworzyć tablicę. Jednak wyszukiwanie jest trudne i często wymaga O(n) czasu na znalezienie elementu w liście jednokierunkowej.

Występuje również w kilku odmianach, takich jak lista jednokierunkowa, która pozwala na przejście w jednym kierunku (tylko do przodu lub do tyłu). Lista dwukierunkowa, która pozwala na przejście w obu kierunkach (do przodu i do tyłu) i wreszcie lista cykliczna, która tworzy zamknięte koło.

Jak rozwiązywać zadania z list?

Aby rozwiązywać zadania z zakresu list, ważna jest dobra znajomość zagadnień związanych z rekurencyjnością, ponieważ lista jest rekurencyjną strukturą danych.

Jeśli weźmiesz jeden element z listy, pozostała struktura danych jest nadal listą i z tego powodu wiele problemów z listami ma prostsze rozwiązania rekurencyjne niż iteracyjne.

Są one również rozwiązywane przy użyciu techniki "dziel i zwyciężaj", która rozbija problem na podproblemy, aż do momentu, gdy podproblem da się rozwiązać.

Np. aby odwrócić listę, dzielisz ją do momentu, aż zostanie tylko jeden element. W tym momencie wiesz, jak odwrócić listę z jednym elementem, która jest niczym innym niż tym samym elementem.

Jest to bardzo podobne do rekurencyjności, a w rzeczywistości najmniejszy problem, który można rozwiązać, staje się podstawą rekurencyjnych rozwiązań.

Nie ma sensu rozwiązywać tych zadań z kodowaniem list, jeśli nie masz podstawowej wiedzy na temat struktur danych lub jeśli jej sobie ostatnio nie odświeżyłeś. W takim przypadku sugeruję, abyś najpierw przeszedł przez dobre kursy struktury danych i algorytmów lub przeczytał tę książkę, by przypomnieć sobie o co chodzi.

Jeśli potrzebujesz rekomendacji, poniżej znajduje się kilka wypróbowanych i przetestowanych przeze mnie zasobów, dzięki którym dogłębnie poznasz struktury danych i algorytmy:

• Data Structures and Algorithms: Deep Dive Using Javadla programistów Java.
• Algorytmy i struktury danych w Pythoniedla tych, którzy kochają Pythona.
• Warsztat Algorytmów JavaScript i struktury danych, które prowadzi Colt Steele dla programistów JavaScript.
• Opanowanie struktur danych i algorytmów przy użyciu C i C+++ dlatych, którzy są dobrzy w C/C++.
• Struktury danych w Javie: Odświeżenie tematu przed rozmową kwalifykacyjną, by odświeżyć sobie ważne koncepcje dotyczące struktur danych i algorytmów w Javie.

Jeśli wolisz książki, nie ma nic lepszego niż wprowadzenie do Algorytmów Thomasa H. Cormena. Jest to jedna z najbardziej wszechstronnych książek o strukturach danych i algorytmach.

Najczęściej zadawane pytania z zakresu kodowania list 

Oto niektóre z pytań najczęściej zadawanych na rozmowach kwalifikacyjnych. Tam, gdzie było to możliwe, podlinkowałem odpowiedzi, ale sugeruję, abyś najpierw spróbował rozwiązać problem na własną rękę, co pozwoli Ci pogłówkować i przy okazji czegoś się nauczyć. Kiedy już rozwiążesz problem lub próbowałeś to zrobić, ale utknąłeś, możesz przyjrzeć się rozwiązaniu i wyciągnąć z niego wnioski.

• Jak znaleźć środkowy element listy jednokierunkowej w jednym przejściu? (rozwiązanie)
• Jak sprawdzić, czy dana lista zawiera cykl? Jak znaleźć element początkowy cyklu? (rozwiązanie)
• Jak odwrócić listę? (rozwiązanie)
• Jak odwrócić listę jednokierunkową bez rekurencji? (rozwiązanie)
• W jaki sposób można usunąć zduplikowane elementy w nieposortowaniej liście? (rozwiązanie)
• Jak znaleźć długość listy jednokierunkowej? (rozwiązanie)
• Jak znaleźć trzeci element od końca w liście jednokierunkowej (rozwiązanie)
• Jak znaleźć sumę dwóch list za pomocą stosu? (rozwiązanie)
• Jak odwrócić listę w miejscu? (rozwiązanie)
• Jak dodać element na środku listy? (rozwiązanie)
• Jak sortować listę w Javie? (rozwiązanie)
• Jaka jest różnica między tablicą a listą? (odpowiedź)
• Jak usunąć n-ty element od końca listy? (rozwiązanie)
• Jak połączyć dwie posortowane listy? (rozwiązanie) 
• Jak przekonwertować posortowaną listę do binarnego drzewa wyszukiwania? (rozwiązanie)
• Mając listę i wartość x, podziel ją w taki sposób, że wszystkie elementy mniejsze niż x znajdowały się przed elementami większymi lub równymi x. (rozwiązanie)
• Jak usunąć duplikaty z posortowanej listy? (rozwiązanie)
• Jak znaleźć element, w którym zaczyna się przecięcie dwóch pojedynczo połączonych list? (rozwiązanie)
• Jak sprawdzić, czy dana lista jest palindromem? (rozwiązanie)
• Jak usunąć wszystkie elementy z listy liczb całkowitych, które odpowiadają podanej wartości? (rozwiązanie)

Powyższe pytania pomogą Ci rozwinąć umiejętności rozwiązywania problemów, a także poszerzyć wiedzę na temat struktur danych list.

Jeśli wciąż brakuje Ci zadań do rozwiązania, możesz również sprawdzić tę listę 30 pytań z zakresu list na rozmowę kwalifikacyjną, gdzie znajdziesz jeszcze więcej zadań praktycznych.

Podsumowanie

Dzięki, udało Ci się dotrzeć do końca artykułu. Powodzenia na rozmowie kwalifikacyjnej! Z pewnością nie będzie to łatwe, ale po przećwiczeniu tych pytań będziesz o krok bliżej sukcesu i pracy, o której zawsze marzyłeś. 


Oryginał tekstu w języku angielskim przeczytasz tutaj.