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

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

Javin Paul Software Architect / Blogger / Infotech
Poznaj listę często zadawanych podczas rozmów kwalifikacyjnych zadań z kodowania list.
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. W przeszłości prezentowałem kilka pytań dotyczących struktur danych, algortymów rozwiązujących problemy dotyczące łańcuchów znaków oraz kilka przydatnych kursów online, przygotowujących do rozmowy kwalifikacyjnej. 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:


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.


Użyteczne zasoby do przeczytania przed rozmową kwalifikacyjną z zakresu kodowania 

Jeśli potrzebujesz zasobów, aby dobrze przygotować się do rozmowy kwalifikacyjnej z zakresu programowania i kodowania, przedstawiam Ci kilka kursów online i książek, które powinieneś sprawdzić:


Inne artykuły, które mogą Ci się przydać

10 książek o algorytmach które każdy programista powinien przeczytać

Top 5 książek o strukturach danych i algorytmach dla programistów Java

20+ zadań z zakresu kodowania z rozmów kwalifikacyjnych 

50+ zadań z zakresu struktur danych i problemów z algorytmami z rozmów kwalifikacyjnych

30+ zadań z zakresu tablic z rozmów kwalifikacyjnych

Od 0 do 1: struktury danych i algorytmy w języku Java

Analiza struktury danych i algorytmów - rozmowa kwalifykacyjna

10 książek które trzeba przeczytać przed rozmową kwalifykacyjną z zakresu programoania technicznego oraz kodowania


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.

Masz coś do powiedzenia?

Podziel się tym z 120 tysiącami naszych czytelników

Dowiedz się więcej