30 najlepszych struktur danych i algorytmów Wywiad Pytania i odpowiedzi [Dla nowicjuszy i doświadczonych]

Struktury danych i algorytmy należą do najważniejszych przedmiotów w świecie informatyki i inżynierii. Jeśli pojawisz się na rozmowę kwalifikacyjną z inżynierem oprogramowania, możesz mieć pewność, że zmierzysz się z serią pytań specjalnie poświęconych strukturom danych i algorytmom – oto jak ważne są one!

Algorytmy leżą u podstaw wszystkiego, co dzieje się w informatyce i nauce o danych. Od uczenia maszynowego przez sztuczną inteligencję do Blockchain – wszystkie technologie działają na algorytmach. A algorytmy potrzebują do działania struktur danych. Tak więc połączona wiedza na temat struktur danych i algorytmów może pomóc Ci wyróżnić się z tłumu podczas rozmowy kwalifikacyjnej.

Wyzwaniem jest jednak to, że DSA jest rozległą domeną. Tutaj nauka nigdy się nie kończy i zawsze jest coś nowego, co musisz zrozumieć. Chociaż ciągłe podnoszenie umiejętności jest obowiązkowe w przypadku struktur danych i algorytmów, dzisiaj przyjrzymy się niektórym podstawowym elementom DSA, które pomogą Ci zmierzyć się z wywiadami technicznymi.

Najważniejsze struktury danych i algorytmy Wywiad Pytania i odpowiedzi

1. Co rozumiesz o „Strukturach danych”?

Struktury danych można zdefiniować jako techniki służące do systematycznego definiowania, przechowywania i uzyskiwania dostępu do danych. Stanowią najważniejszy element każdego algorytmu. W zależności od typu struktur danych przechowują one różne rodzaje danych i są dostępne na różne sposoby. Aby algorytm zwrócił wynik, musi operować i manipulować zbiorem struktur danych w zorganizowany i wydajny sposób, aby uzyskać ostateczny wynik.

2. Jak odróżnić strukturę plików od struktury danych?

W strukturach plików dane są przechowywane na dyskach zgodnie ze standardowymi zasadami przechowywania plików i nie są kompatybilne z zewnętrznymi aplikacjami innych firm. Z drugiej strony w strukturach danych dane są przechowywane zarówno na dysku, jak i w pamięci RAM w dostosowanych zasadach przechowywania, które są wysoce kompatybilne z aplikacjami zewnętrznymi.

3. Jakie są rodzaje struktur danych?

Struktury danych można ogólnie podzielić na dwie kategorie:

• Linear: W tym przypadku wszystkie elementy są przechowywane sekwencyjnie, a pobieranie odbywa się liniowo. Układ jest niehierarchiczny, a każdy element ma jednego następcę i jednego poprzednika. Przykład — tablice, połączone listy, stosy, kolejki itp.
• Nieliniowe: tutaj przechowywanie nie odbywa się w kolejności liniowej – tzn. wszystkie elementy niekoniecznie mają tylko jednego następcę i poprzednika. Zamiast tego elementy w nieliniowych strukturach danych są połączone z co najmniej dwoma elementami w sposób nieliniowy. Przykład – drzewa, wykresy, stosy.

4. Jakie są kluczowe obszary wykorzystania struktur danych?

Struktury danych są prawie wymagane we wszystkich dziedzinach informatyki, o których można pomyśleć, zwłaszcza w algorytmach i optymalizacji algorytmów. Oto kilka innych obszarów, w których Struktury danych są szeroko stosowane:

• Projekt systemu operacyjnego
• Analiza numeryczna
• Uczenie maszynowe i sztuczna inteligencja
• Projektowanie i rozwój kompilatora
• Zarządzania bazami danych
• Analiza leksykalna
• Programowanie graficzne
• Algorytmy wyszukiwania i sortowania i nie tylko.

5. Wyjaśnij strukturę danych stosu i podaj obszary jej użycia.

Stos to po prostu uporządkowana lista, która umożliwia wstawianie i usuwanie tylko z jednego z końców – znanego jako „góra”. Jest to rekurencyjna struktura danych, która ma wskaźnik do swoich „górnych” elementów, który informuje nas o najwyższym elemencie stosu. W oparciu o strategię wyszukiwania elementów, Stack jest również znany jako Last-In-First-Out, ponieważ ostatni element wepchnięty na stos będzie na górze i będzie pierwszym, który wyskoczy. Oto kilka zastosowań struktury danych stosu:

• Cofanie się
• Zarządzanie pamięcią
• Powrót funkcji i wywołanie
• Ocena wyrażenia

6. Jakie operacje można wykonać na stosie?

Struktura danych stosu obsługuje następujące trzy operacje:

• push() — aby wstawić element na najwyższą pozycję stosu.
• pop() — aby wydobyć jeden element ze szczytu stosu.
• peek() — po prostu sprawdza element znajdujący się na górze stosu bez wyjmowania go ze stosu.

7. Co rozumiesz o wyrażeniach Postfix?

Wyrażenie Postfix to wyrażenie, w którym operatory podążają za operandami. Jest to niezwykle korzystne pod względem obliczeniowym, ponieważ nie wymaga grupowania wyrażeń podrzędnych w nawiasy ani nawet uwzględniania pierwszeństwa operatorów. Wyrażenie a+b jest po prostu reprezentowane jako ab+ w przyrostku.

8. W jaki sposób elementy tablicy 2D są przechowywane w pamięci?

Elementy tablicy 2-D można przechowywać w pamięci na dwa sposoby:

• Row-Major: W tej metodzie najpierw wszystkie wiersze tablicy są nieprzerwanie przechowywane w pamięci. Najpierw pierwszy rząd jest całkowicie zapisany, potem drugi i tak dalej aż do ostatniego.
• Column-Major: W tym przypadku wszystkie kolumny tablicy są stale przechowywane w pamięci. Najpierw pierwsza kolumna jest przechowywana w całości, potem druga kolumna i tak dalej.

9. Zdefiniuj strukturę danych listy połączonej.

Listy połączone to kolekcje węzłów — które są losowo przechowywanymi obiektami. Każdy węzeł ma dwa wewnętrzne elementy – pole danych i pole łącza. Pole Dane zawiera wartość, którą ma dany węzeł, podczas gdy pole Link ma wskaźnik do następnego węzła, z którym ten węzeł jest połączony. W zależności od sytuacji, listę połączoną można uznać zarówno za liniową, jak i nieliniową strukturę danych.

10. Pod jakimi względami listy połączone są lepsze niż tablice?

Listy połączone są lepsze niż tablice w następujący sposób:

• Rozmiary tablic są ustalane w czasie wykonywania i nie można ich później modyfikować, ale listy połączone można rozszerzać w czasie rzeczywistym, zgodnie z wymaganiami.
• Listy połączone nie są przechowywane w pamięci w sposób ciągły, w wyniku czego są znacznie bardziej wydajne pod względem pamięci niż tablice, które są przechowywane statycznie.
• Liczba elementów, które można przechowywać na dowolnej połączonej liście, jest ograniczona tylko do dostępnego miejsca w pamięci, podczas gdy liczba elementów jest ograniczona rozmiarem tablicy.

11. W języku programowania C, którego wskaźnika użyjesz do zaimplementowania heterogenicznej połączonej listy?

Heterogeniczne listy połączone, jak sama nazwa wskazuje, zawierają różne typy danych. W rezultacie nie jest możliwe użycie tutaj zwykłych wskaźników. Tak więc wskaźniki Void są zwykle używane w takim scenariuszu, ponieważ mogą wskazywać na dowolny rodzaj wartości.

12. Co to jest lista podwójnie połączona?

Jak sama nazwa wskazuje, lista podwójnie połączona to lista połączona, która ma węzły połączone zarówno z kolejnymi, jak i poprzedzającymi węzły. W rezultacie węzły listy podwójnie połączonej mają trzy, a nie dwa pola:

• Pole danych
• Następny wskaźnik (do wskazywania następnego węzła)
• Poprzedni wskaźnik (do wskazywania poprzedniego węzła)

13. Wyjaśnij strukturę danych kolejki z niektórymi jej aplikacjami.

Kolejka to uporządkowana lista, która pozwala na wstawianie i usuwanie elementów nie z jednego, ale z dwóch końców – zwanych TYLNYM i PRZEDNIM. Wstawianie odbywa się od strony FRONT, natomiast kasowanie od strony TYLNEJ. W wyniku tego kolejka jest często nazywana „pierwsze weszło-pierwsze wyszło” (FIFO). Oto kilka rozpowszechnionych zastosowań kolejek jako struktury danych:

• Do list oczekujących na pojedyncze zasoby, takie jak procesor, drukarka, dysk itp.
• Do asynchronicznego przesyłania danych, np. plik IO, gniazda, potoki.
• Jako bufory w większości aplikacji do odtwarzania multimediów.
• W systemach operacyjnych do obsługi przerw.

14. Czy możesz wymienić niektóre wady implementacji kolejek za pomocą tablic?

Podczas implementacji kolejek z tablicami występują głównie dwie wady:

• Złe zarządzanie pamięcią, ponieważ tablice są statycznymi strukturami danych, więc implementacja kolejek z tablicami usuwa wiele funkcji kolejek.
• Problem z rozmiarem, ponieważ rozmiary tablic są definiowane podczas definicji tablicy. Jeśli więc chcemy dodać do naszej kolejki więcej elementów niż rozmiar tablicy, nie będzie to możliwe.

15. Jakie warunki należy spełnić, aby element znalazł się w kolejce okrężnej?

Oto kilka istotnych warunków dotyczących wstawiania do kolejek kołowych:

• Jeśli (tył + 1)%maxsize == przód -> oznacza to, że kolejka jest pełna -> brak możliwości wstawiania.
• Jeśli tył != max – 1, wartość tył zostanie zwiększona do maxsize i nowa wartość zostanie wstawiona na końcu.
• Jeśli przód != 0 i tył == max -1 –> oznacza to, że kolejka nie jest pełna. Tak więc wartość rear ustawiana jest na 0, a nowy element jest wstawiany do tylnego końca kolejki okrężnej.

16. Co to jest dequeue?

Double-Ended Queue lub deque to uporządkowany zestaw elementów, który ułatwia wstawianie i usuwanie z obu końców – tylnego i przedniego. Dzięki temu jest to jeszcze bardziej elastyczne niż struktura danych kolejki.

17. Zdefiniuj strukturę danych drzewa i wymień niektóre typy drzew.

Drzewo to nieliniowa, rekurencyjna struktura danych zawierająca różne węzły. Jeden konkretny węzeł jest wyznaczony jako korzeń drzewa, z którego wyłaniają się wszystkie inne węzły. Oprócz korzenia wszystkie inne węzły nazywane są węzłami podrzędnymi. Ogólnie rzecz biorąc, istnieją następujące typy struktur danych drzewa:

• Ogólne drzewa
• Drzewa binarne
• Drzewa wyszukiwania binarnego
• Lasy
• Drzewo wyrażeń
• Drzewo turniejowe

18. Jak działa sortowanie bąbelkowe?

Sortowanie bąbelkowe jest jednym z najczęściej używanych algorytmów sortowania i jest używany z tablicami, porównując sąsiednie elementy i wymieniając ich pozycje na podstawie ich wartości. Nazywa się to sortowaniem bąbelkowym, ponieważ wizualizacja tego, jak to działa, przypomina bąbelki unoszące się na powierzchni wody i opadające w dół większe jednostki.

Przeczytaj: Struktury danych w C i jak używać?

19. Jaki jest najszybszy dostępny algorytm sortowania?

Dostępnych jest wiele różnych algorytmów sortowania, takich jak sortowanie przez scalanie, sortowanie szybkie, sortowanie bąbelkowe i inne. Spośród nich nie możemy wybrać jednego konkretnego algorytmu, który jest obiektywnie najszybszy, ponieważ ich wydajność różni się znacznie w zależności od danych wejściowych, reakcji po przetworzeniu danych przez algorytm i sposobu ich przechowywania.

20. Czym są drzewa binarne?

Drzewa binarne to specjalne rodzaje drzew, w których każdy węzeł może mieć NAJWYŻEJ dwoje dzieci. Aby to ułatwić, drzewa binarne są generalnie podzielone na trzy rozłączne zestawy — węzeł główny, prawe poddrzewo i lewe poddrzewo.

21. W jaki sposób drzewa AVL mogą być używane w różnych operacjach w porównaniu z BST?

Drzewa AVL są drzewami o zrównoważonej wysokości, więc nie pozwalają na przekrzywienie drzewa z jednej strony. Czas potrzebny na wykonanie wszystkich operacji na BST o wysokości h wynosi O(h). Jednak w najgorszym przypadku może to być O(n) – kiedy BST zostaje wypaczone. AVL pomaga w wyeliminowaniu tego ograniczenia, ograniczając wysokość drzewa. Czyniąc to, nakłada górną granicę wszystkich operacji na maksimum O(log n), gdzie n = liczba węzłów.

22. Jakie są właściwości B-drzewa?

B-drzewo rzędu m zawiera następujące właściwości:

• Wszystkie właściwości drzewa M-way.
• Każdy węzeł B_drzewa będzie miał maksymalnie m dzieci.
• Każdy węzeł z wyjątkiem korzenia i liścia będzie miał co najmniej m/2 dzieci.
• Węzeł główny musi mieć co najmniej 2 węzły podrzędne.
• Wszystkie węzły liści muszą leżeć na tym samym poziomie.

23. Co rozumiesz o strukturze danych wykresu?

Strukturę danych wykresu (G) można zdefiniować jako uporządkowany zbiór G(V,E), gdzie V reprezentuje zbiór wierzchołków, a E to krawędzie tworzące połączenia. Zasadniczo wykres można traktować jako cykliczne drzewo, w którym węzły mogą utrzymywać złożone relacje między nimi, a nie tylko relacje rodzic-dziecko.

24. Rozróżnij cykl, ścieżkę i obwód w odniesieniu do struktury danych wykresu.

Różnice między cyklem, ścieżką i obwodem są następujące:

• Łata to rząd sąsiadujących ze sobą wierzchołków połączonych krawędziami bez żadnych ograniczeń.
• Cykl to zamknięta ścieżka, w której początkowy wierzchołek jest taki sam jak wierzchołek końcowy. W cyklu żaden konkretny wierzchołek nie może być odwiedzony dwa razy.
• Obwód, podobnie jak cykl, jest ścieżką zamkniętą, której wierzchołek początkowy jest taki sam jak wierzchołek końcowy. Jednak każdy wierzchołek w obwodzie może być odwiedzany więcej niż raz.

25. Jak działa algorytm Kruskala?

Algorytm Kruskala traktuje graf jako las, a każdy z jego węzłów jako indywidualne drzewo. Mówi się, że drzewo łączy się z innym drzewem wtedy i tylko wtedy, gdy ma najniższy koszt spośród wszystkich opcji i nie narusza żadnej właściwości minimalnego drzewa rozpinającego (MST).

Powiązane: Drzewo binarne w strukturze danych

26. Jak algorytm Prim znajduje drzewo opinające?

Algorytm Prima działa, traktując węzły jako pojedyncze drzewa. Następnie kontynuuje dodawanie nowych węzłów do drzewa opinającego z danego grafu, które muszą zostać przekształcone w wymagane drzewo opinające.

27. Co to jest minimalne drzewo opinające (MST)?

MST na wykresach ważonych to drzewa, które mają minimalną wagę, ale obejmują wszystkie wierzchołki.

28. Co to jest funkcja rekurencyjna?

Z definicji funkcja rekurencyjna wywołuje samą siebie lub bezpośrednio wywołuje funkcję, która ją wywołuje. Każda funkcja rekurencyjna ma pewne podstawowe kryteria, po których funkcja przestaje się wywoływać.

29. Jaka jest technika wyszukiwania interpolacyjnego?

Technika wyszukiwania interpolacyjnego jest modyfikacją metody Binary Search. Algorytm wyszukiwania interpolacyjnego działa na pozycji sondowania żądanych wartości.

30. Co to jest haszowanie?

Haszowanie jest bardzo przydatną techniką używaną do konwertowania szeregu par klucz-wartość na indeksy tablicy. Tabele haszujące przydają się podczas tworzenia asocjacyjnego magazynu danych, w którym indeks danych można łatwo znaleźć, po prostu podając jego parę klucz-wartość!

Podsumowując

Struktury danych są naprawdę podstawą wszystkiego, co dzieje się w informatyce. Nawet bardziej złożone zastosowania informatyki, tj. nauka o danych, uczenie maszynowe, sztuczna inteligencja, IoT, są zbudowane na bazie struktur danych i algorytmów.

Tak więc, jeśli jesteś początkującym, który chce zrobić karierę w którejkolwiek z nowych dziedzin, zalecamy rozpoczęcie od opanowania struktur danych i algorytmów. Możesz też sprawdzić nasz kurs Executive PG Program in Data Science , który jest przeznaczony dla początkujących. Ucz się od podstaw i zostań ekspertem w dziedzinie Data Science. Zapisz się już dziś!