Spis treści[Ukryć][Pokazać]
- 1. Jak definiujesz tablicę?
- 2. Tablice dynamiczne: czym one są? Co odróżnia je od podstawowych tablic?
- 3. Czym różnią się tablica i słownik?
- 4. Wymień niektóre zalety i wady tablic.
- 5. Do czego odnosi się „Sparse Array”?
- 6. Kiedy byś wybrał połączoną listę zamiast tablicy?
- 7. Co odróżnia tablicę indeksowaną od tablicy asocjacyjnej?
- 8. Jakie zalety ma Heap nad posortowanymi tablicami?
- 9. Czy możemy zdefiniować wielkość tablicy jako ujemną?
- 10. Jak znaleźć brakującą liczbę całkowitą w tablicy od 1 do 100 elementów?
- 11. Jak znaleźć indeks elementu w tablicy?
- 12. Jak pozbyć się określonego elementu z tablicy?
- 13. Jak można zweryfikować równość dwóch tablic?
- 14. Kiedy omawiamy tablice, co rozumiesz przez wyrażenia „Wymiar” i „Indeks dolny”?
- Pytania do rozmowy kwalifikacyjnej na temat kodowania
- 15. Znajdź parę w tablicy, która ma określoną sumę
- 16. Sortowanie tablicy binarnej z czasem liniowym
- 17. Znajdź największy dwucyfrowy produkt w tablicy.
- 18. Jak przesunąć wszystkie zera tablicy na koniec?
- 19. Jak posortować tablicę z dwoma wpisami, które są przełączane w jednej operacji.
- 20. Jak połączyć dwie posortowane tablice w miejscu.
- 21. Jak zmienić kolejność elementów w naprzemiennych wysokich i niskich pozycjach?
- 22. Jak podstawić każdy element tablicy bez użycia operatora dzielenia iloczynem każdego elementu tablicy?
- 23. Znajdź najdziwniejszy element w tablicy w czasie logarytmicznym
- 24. Jak uzyskać kolejny większy element dla każdego elementu w tablicy kołowej?
- 25. Znajdź liczbę inwersji tablicy?
- 26. Co to jest problem zatrzymywania wody deszczowej?
- Wnioski
Wywiady dotyczące kodowania zawierają serię pytań DSA. Powinieneś umieć posługiwać się tablicami, jeśli przygotowujesz się do nadchodzącego wywiadu technicznego z FAANG lub inną firmą technologiczną Tier-1.
W większości wywiadów dotyczących kodowania zajmuje drugie miejsce po Strings. Tablica to grupa powiązanych ze sobą elementów danych przechowywanych blisko siebie w pamięci.
Ponieważ są połączone ze wszystkimi językami programowania, takimi jak C, C++, Java, Python, Perl i Ruby, są wszędzie. Kontynuuj czytanie, aby zapoznać się z kilkoma ćwiczącymi wyzwaniami związanymi z kodowaniem oraz pytaniami i odpowiedziami podczas wywiadów w oparciu o tablice.
Python zostanie użyty w tym poście, aby rozwiązać problemy z kodowaniem, ponieważ jest prosty w użyciu, zrozumiały i musi być znany większości z nas.
Zaczynajmy.
1. Jak definiujesz tablicę?
- Grupa powiązanych typów danych to tablica.
- Tablice są zawsze stałe.
- Ten sam rodzaj zmiennej jest przechowywany w kilku miejscach przez obiekty tablicowe.
- Zarówno typy pierwotne, jak i odwołania do obiektów są z nim zgodne.
2. Tablice dynamiczne: czym one są? Co odróżnia je od podstawowych tablic?
Istotną zaletą jest automatyczne skalowanie, które zapewniają tablice dynamiczne (nazywane również tablicami rozwijalnymi, tablicami o zmiennym rozmiarze, tablicami wymiennymi lub ArrayLists w Javie).
Zawsze musisz wiedzieć, ile elementów Twoja tablica będzie przechowywać z góry, ponieważ tablice mają stały rozmiar. Z drugiej strony tablica dynamiczna rośnie wraz z dodawaniem do niej kolejnych członków, więc nie trzeba wcześniej znać jej dokładnego rozmiaru.
3. Czym różnią się tablica i słownik?
Jest to zestaw pytań do rozmowy kwalifikacyjnej oparty na podstawach, które są regularnie zadawane. Poniżej przedstawiono kluczowe różnice między tablicami a słownikami:
- Tablica to uporządkowana lista podobnych elementów. Z drugiej strony słownik ma pary klucz-wartość.
- Rozmiary tablic mogą zmieniać się dynamicznie. Takie dynamiczne idee nie istnieją w słownikach.
- Przed użyciem tablicy należy określić jej rozmiar. Rozmiary słowników nie muszą być dostosowywane.
- Użyj instrukcji Redim, jeśli chcesz zwiększyć rozmiar tablicy. W słownikach element można dodać bez deklaracji.
4. Wymień niektóre zalety i wady tablic.
Zalety:
- Tablice mogą sortować wiele elementów jednocześnie.
- Inne struktury danych, jak stosy, kolejki, połączone listy, drzewa, wykresy itp., mogą być zaimplementowane w tablicy.
- Indeks może służyć do dotarcia do elementu tablicy.
Niedogodności:
- Rozmiar tablicy należy wcześniej zadeklarować. W momencie deklaracji tablicy możemy jednak nie zdawać sobie sprawy z wymaganego rozmiaru.
- Struktura tablicy jest statyczna. Oznacza to, że rozmiar tablicy jest zawsze stały i alokacja pamięci nie może zostać zwiększona ani zmniejszona.
5. Do czego odnosi się „Sparse Array”?
Rozrzedzona tablica to tablica danych zawierająca wiele wpisów o wartościach zerowych. W przeciwieństwie do tego, gęsta tablica zawiera większość swoich elementów o wartościach niezerowych. Indeksy tablicy rzadkiej, która konwertuje liczby na obiekty, mogą zawierać luki. W porównaniu do HashMap są bardziej wydajne pod względem pamięci.
6. Kiedy byś wybrał połączoną listę zamiast tablicy?
Używając połączonych list zamiast tablic, rozważ:
- Nie potrzebujesz żadnych elementów, aby mieć dostęp losowy.
- Tam, gdzie przewidywalność czasowa ma kluczowe znaczenie, potrzebujesz wstawiania i usuwania z listy w czasie stałym.
- Aby utworzyć kolejkę priorytetową, może być konieczne umieszczenie pozycji na środku listy.
- Nie masz pojęcia, jak długa będzie lista. Jeśli rozmiar tablicy rośnie, musisz ponownie zadeklarować i zduplikować pamięć, tak jak w przypadku prostych tablic.
7. Co odróżnia tablicę indeksowaną od tablicy asocjacyjnej?
W poniższej tabeli wymieniono podstawowe różnice między tablicami asocjacyjnymi i indeksowanymi.
- Do sortowania tablicy asocjacyjnej używana jest para klucz-wartość w formacie tekstowym lub liczbowym. Wszystkie klucze w indeksowanej tablicy są numeryczne, a każdy klucz jest powiązany z odrębną wartością.
- W tablicy asocjacyjnej kluczem może być ciąg. Tablica indeksowana z kluczami całkowitymi zaczynającymi się od 0.
- Dwukolumnowa tabela naśladuje zachowanie tablicy asocjacyjnej. Podobne do tabeli jednokolumnowej są tablice indeksowane.
- Mapy są typem tablicy asocjacyjnej. Tablica indeksów nie jest mapą.
8. Jakie zalety ma Heap nad posortowanymi tablicami?
Kluczową korzyścią jest efektywność czasowa wykorzystania sterty nad posortowanymi tablicami. Chociaż operacje na stercie są szybsze, sortowanie tablicy wymaga dużo czasu. Sterta może wykryć najmniejszy element znacznie szybciej niż można posortować tablicę.
Dany zbiór liczb można uporządkować na jeden z dwóch sposobów za pomocą posortowanych tablic. Z drugiej strony, dla danego zbioru liczb może istnieć więcej niż jedna potencjalna sterta.
9. Czy możemy zdefiniować wielkość tablicy jako ujemną?
Nie, nie możemy zdefiniować ujemnej liczby całkowitej jako rozmiaru tablicy. Jeśli zadeklarujemy, nie będzie błędu w czasie kompilacji. W czasie wykonywania napotkamy jednak wyjątek NegativeArraySizeException.
10. Jak znaleźć brakującą liczbę całkowitą w tablicy od 1 do 100 elementów?
Sumę szeregu można obliczyć, stosując następującą funkcję: n (n + 1) / 2
Ta funkcja będzie działać tylko wtedy, gdy tablica nie ma żadnych duplikatów lub brakuje w niej więcej niż jednej liczby całkowitej. Niezależnie od tego, czy tablica zawiera zduplikowane elementy, możesz posortować tablicę, aby sprawdzić, czy istnieją elementy, które są równoważne.
11. Jak znaleźć indeks elementu w tablicy?
Indeks elementu można wykryć za pomocą wyszukiwania liniowego lub binarnego. Dopóki nie zlokalizuje dopasowania wymaganego elementu, funkcja wyszukiwania liniowego zapętla się po każdym elemencie w tablicy. Zwraca indeks po zlokalizowaniu pasującego elementu. W konsekwencji czasowa złożoność poszukiwań liniowych wynosi O. (n). Zarówno posortowana, jak i nieposortowana tablica mogą korzystać z wyszukiwania liniowego.
Korzystając z wyszukiwania binarnego, które w sposób ciągły dzieli tablicę na pół, aż mediana interwału odpowiada wymaganemu elementowi i dostarcza indeks, można uzyskać indeks elementu, jeśli tablica jest posortowana. W konsekwencji czasowa złożoność wyszukiwania binarnego wynosi O. (log n).
12. Jak pozbyć się określonego elementu z tablicy?
Ponieważ nie możesz po prostu usunąć elementów z oryginalnej tablicy, ponieważ są to ustalone zestawy o określonej wielkości, ankieter stara się zasugerować inne podejście i rozwiązać problem, który pojawia się w pytaniu. Najlepszym sposobem postępowania jest utworzenie nowej tablicy w celu usunięcia elementu. Możesz zduplikować elementy z pierwszej tablicy w tej tablicy i uwzględnić tylko ten element, który chcesz usunąć.
Inna strategia polega na znalezieniu elementu docelowego w tablicy, a następnie odwróceniu kolejności wszystkich elementów znajdujących się po prawej stronie elementu docelowego.
13. Jak można zweryfikować równość dwóch tablic?
Najpierw musisz zweryfikować długości dwóch dostarczonych tablic. Pasujące elementy obu tablic są porównywane, gdy ich długości są równe. Dwie tablice będą traktowane jako równe. jeśli każda para składników w każdej korespondencji jest równa. To podejście nie jest zalecane do sprawdzania równości dwóch tablic, jeśli tablice mają duży rozmiar, ponieważ zajmie to dużo czasu. Możesz również użyć metody equals() zawartej w klasie Arrays, jednak jeśli osoba przeprowadzająca wywiad poprosi Cię o porównanie dwóch tablic bez użycia metod wbudowanych, ten sposób będzie przydatny.
14. Kiedy omawiamy tablice, co rozumiesz przez wyrażenia „Wymiar” i „Indeks dolny”?
„Wymiar” tablicy to liczba indeksów lub indeksów dolnych potrzebnych do zidentyfikowania każdego indywidualnego elementu. Indeksy i wymiary mogą być niejasne. Wymiar to opis zakresu dozwolonych kluczy, a indeks dolny to liczba. Dla każdego wymiaru tablicy wymagany jest tylko jeden indeks dolny.
Na przykład tablica arr[10][5] ma dwa wymiary. Rozmiary 10 z jednej i 5 z drugiej. Aby zaadresować jego komponenty, potrzebujesz dwóch indeksów dolnych. Oba są od 0 do 4; jeden od 0 do 9 włącznie.
Pytania do rozmowy kwalifikacyjnej na temat kodowania
15. Znajdź parę w tablicy, która ma określoną sumę
Na przykład,
Wejście:
- liczby = [8, 7, 2, 5, 3, 1]
- cel = 10
Wyjście:
- Znaleziono parę (8, 2)
- Or
- Znaleziono parę (7, 3)
Wejście:
- liczby = [5, 2, 6, 8, 1, 9]
- cel = 12
Wyjście:
- Nie znaleziono pary
16. Sortowanie tablicy binarnej z czasem liniowym
Sortuj tablicę binarną w czasie liniowym i w ustalonym obszarze. Na wyjściu powinny pojawić się najpierw wszystkie zera, a potem same jedynek.
Na przykład,
- Dane wejściowe: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Dane wyjściowe: { 0, 0, 0, 0, 1, 1, 1, 1 }
Prostym podejściem byłoby obliczenie całkowitej liczby zer w tablicy, powiedzmy k, a następnie wypełnienie pierwszych k indeksów w tablicy zerami, a pozostałych indeksów 0. Alternatywnie możemy obliczyć, ile jedynek jest łącznie w tablicy tablica k, wypełnij ostatnie k indeksów tablicy wartością 0, a resztę indeksów pozostaw 1.
Dane podejście ma złożoność czasową O(n) i nie wykorzystuje dodatkowej pamięci, gdzie n jest rozmiarem danych wejściowych.
17. Znajdź największy dwucyfrowy produkt w tablicy.
Znajdź największy iloczyn dwóch liczb w tablicy liczb całkowitych.
Pomyśl o tablicy 10 3 5 6 2 jako przykładu. Para (-10, -3) lub (5, 6) jest najwyższym iloczynem.
Myślenie o każdej kombinacji elementów i wymyślanie ich produktu to głupie podejście. Jeśli iloczyn bieżącej pary jest większy niż maksymalny iloczyn uzyskany do tej pory, zaktualizuj maksymalny iloczyn. Wydrukuj komponenty produktu końcowego na końcu.
Powyższe rozwiązanie, gdzie n jest wielkością wejścia, ma złożoność czasową O(n2) i nie zajmuje więcej miejsca.
18. Jak przesunąć wszystkie zera tablicy na koniec?
Przenieś wszystkie zera w tablicy liczb całkowitych na koniec. Odpowiedź powinna unikać używania stałej przestrzeni i zachować względną kolejność składników tablicy.
Dane wejściowe: {1,2,3,0,8,0,4,7}
Wynik wyniesie {1,2,3,8,4,7,0,0}
Umieść element w następującej dostępnej pozycji w tablicy, jeśli bieżący element nie jest zerem. Wypełnij wszystkie pozostałe indeksy 0, gdy wszystkie elementy tablicy zostaną przetworzone.
Poprzednie rozwiązanie ma złożoność czasową O(n), gdzie n jest rozmiarem danych wejściowych.
19. Jak posortować tablicę z dwoma wpisami, które są przełączane w jednej operacji.
Sortuj tablicę w czasie liniowym, biorąc pod uwagę dwa zamienione elementy i tablicę ze wszystkimi jej elementami ułożonymi w kolejności rosnącej. Udawaj, że tablica nie zawiera duplikatów.
Dane wejściowe:= [1,9,3,4,7,2] lub [9,3,7,2,1,4] lub [2,4,1,7,3,9]
Wyjście: = [1,2,3,4,7,9]
Począwszy od drugiego elementu w tablicy, celem jest porównanie każdego elementu z jego poprzednikiem. Stanowisko sporu jest przechowywane przez dwa wskaźniki, x i y.
Zaktualizuj x do indeksu poprzedniego elementu i y do indeksu bieżącego elementu, jeśli pierwszy jest większy niż drugi. Zaktualizuj y do indeksu bieżącego elementu, jeśli okaże się, że poprzedni element jest większy niż bieżący element.
Na koniec zamień elementy o indeksach x i y po zakończeniu przetwarzania każdej sąsiedniej pary elementów.
Ze względu na fakt, że powyższa metoda wykonuje tylko jedno skanowanie tablicy wejściowej o rozmiarze n, jej złożoność czasowa wynosi O(n). Rozwiązanie nie wymaga dodatkowego miejsca.
20. Jak połączyć dwie posortowane tablice w miejscu.
Połącz elementy tablic X[] i Y[]—dwie posortowane tablice o rozmiarze m i n każda—zachowując posortowaną kolejność, to znaczy wypełniając X[] pierwszymi m najmniejszymi elementami i wypełniając Y[] pozostałe elementy.
Jeśli element w tablicy X[] jest już na właściwej pozycji (tj. najmniejszej spośród pozostałych elementów), zignoruj go; w przeciwnym razie zastąp go najmniejszym elementem, który również jest pierwszym elementem Y[]. Aby zachować posortowaną kolejność po zamianie, przenieś element (teraz w Y[0]) do właściwej lokalizacji w Y[].
Rozmiar pierwszej tablicy to m, rozmiar drugiej tablicy to n, a złożoność czasowa to O(mn).
21. Jak zmienić kolejność elementów w naprzemiennych wysokich i niskich pozycjach?
Zmień rozmieszczenie tablicy liczb całkowitych, aby każdy kolejny element był większy niż poprzednie i następujące elementy. Załóżmy, że tablica nie zawiera żadnych zduplikowanych elementów.
Sortowanie tablicy lub wykorzystanie dodatkowej przestrzeni nie jest konieczne do efektywnego podejścia. Plan zakłada, na początek, drugi element tablicy i zwiększenie o dwa dla każdej iteracji pętli.
Zamień komponenty, jeśli ostatni element przekracza pierwszy. W podobnym duchu zamień oba elementy, jeśli następny element jest większy niż bieżący. Pożądaną tablicę zgodną z określonymi ograniczeniami uzyskamy na końcu pętli.
22. Jak podstawić każdy element tablicy bez użycia operatora dzielenia iloczynem każdego elementu tablicy?
Bez użycia operatora dzielenia zastąp każdy element w tablicy liczb całkowitych iloczynem wszystkich innych elementów.
W liniowym czasie i stałej przestrzeni możemy wykorzystać rekurencję do rozwiązania tego problemu. Pojęciem jest rekurencyjne obliczanie iloczynów każdego elementu w prawej podtablicy i przekazywanie iloczynu lewej podtablicy jako parametrów funkcji.
Złożoność czasowa wynosi O(n).
23. Znajdź najdziwniejszy element w tablicy w czasie logarytmicznym
Mając tablicę liczb całkowitych, w której wszystkie elementy oprócz jednego mają parzystą liczbę wystąpień, problemem jest określenie, ile razy pojawia się ten jeden element. Znajdź nieparzysto występujący element w czasie logarytmicznym i stałej przestrzeni, jeśli te same elementy występują parami w tablicy i nigdy nie może być więcej niż dwa wystąpienia danego elementu z rzędu.
Operacja XOR pozwala nam rozwiązać ten problem w czasie liniowym. Celem jest XOR dla każdego elementu w tablicy. Pozostają tylko nieparzyste elementy występujące po tym, jak elementy parzyste znoszą się nawzajem.
Ten problem można rozwiązać nawet w czasie O(log(n)).
24. Jak uzyskać kolejny większy element dla każdego elementu w tablicy kołowej?
Powinien znajdować się następny większy element dla każdego elementu w okrągłej tablicy liczb całkowitych. Pierwsza większa liczba całkowita po elemencie x w tablicy jest kolejnym większym elementem tego elementu.
Od prawej do lewej możemy operować na elementach tablicy. Celem jest wykonanie pętli dla każdego elementu x, aż albo stos będzie pusty, albo będziemy mieć na nim wyższy element. Ustaw kolejny większy element x tak, aby pojawił się na górze stosu, kiedy to nastąpi.
25. Znajdź liczbę inwersji tablicy?
Znajdź całkowitą liczbę inwersji tablicy. Para I j) jest nazywana odwróceniem tablicy A, jeśli I j) i (A[i] > A[j]). Musimy policzyć każdą parę w tablicy.
Liczenie wszystkich członków tablicy, których jest mniej niż po prawej stronie i dodanie wyniku do danych wyjściowych, jest prostym podejściem.
To rozwiązanie ma złożoność O(n2), gdzie n jest rozmiarem danych wejściowych.
26. Co to jest problem zatrzymywania wody deszczowej?
Znalezienie największej ilości wody, która może zostać uwięziona w danym zestawie słupków o szerokości jednej jednostki, jest znane jako problem „zatrzymywania opadów deszczu”.
Celem jest określenie najwyższego słupka, który można umieścić po lewej i prawej stronie każdego słupka. Minimum wiodących słupków po lewej i prawej stronie, pomniejszone o wysokość bieżącego słupka, to ilość wody, która jest przechowywana na każdym słupku.
Wnioski
W porównaniu do innych tematów dotyczących struktury danych tablice są prostsze. Aby zadawać pytania podczas rozmowy kwalifikacyjnej, musisz mieć podstawową wiedzę na temat tablic.
Powinieneś dokładnie przejrzeć podstawy tablic, w tym operacje na tablicach (od deklarowania/tworzenia tablicy do uzyskiwania dostępu/modyfikowania elementów tablicy), a także koncepcje programowania, takie jak pętle, rekursja i podstawowe operatory, aby pomyślnie odpowiedzieć na pytania wywiadu tablicowego. Całkowicie rozpoznaj problem.
Jeśli masz jakiekolwiek pytania, powinieneś szukać wyjaśnień. Pomyśl o podzieleniu problemu na łatwiejsze do opanowania części. Upewnij się, że masz na uwadze algorytm przed rozpoczęciem programowania; zapisz to lub zwizualizuj na schemacie blokowym. następnie zacznij pisać kod.
Dodaj komentarz