Obsah[Skryť][Šou]
- 1. Ako definujete pole?
- 2. Dynamické polia: Čo sú to? Čo ich odlišuje od Basic Arrays?
- 3. Ako sa pole a slovník navzájom líšia?
- 4. Uveďte niektoré výhody a nevýhody polí.
- 5. Čo znamená „Sparse Array“?
- 6. Kedy by ste zvolili prepojený zoznam pred poľom?
- 7. Čo odlišuje indexované pole od asociatívneho poľa?
- 8. Aké výhody má Heap oproti triedeným poliam?
- 9. Môžeme definovať veľkosť poľa ako zápornú?
- 10. Ako nájdete chýbajúce celé číslo v poli s 1 až 100 prvkami?
- 11. Ako zistíte index prvku v poli?
- 12. Ako sa môžete zbaviť konkrétneho prvku z poľa?
- 13. Ako možno overiť rovnosť dvoch polí?
- 14. Keď hovoríme o poliach, čo máte na mysli pod vetami „Dimenzia“ a „dolný index“?
- Otázky na pohovor o kódovaní
- 15. Vyhľadajte pár v poli, ktorý má zadaný súčet
- 16. Binárne triedenie poľa s lineárnym časom
- 17. Nájdite najväčší dvojintový súčin v poli.
- 18. Ako posunúť všetky nuly poľa na koniec
- 19. Ako zoradiť pole s dvoma položkami, ktoré sa prepínajú v jednej operácii.
- 20. Ako skombinovať dve zoradené polia na mieste.
- 21. Ako zmeniť poradie radu položiek v striedaní vysokých a nízkych pozícií?
- 22. Ako nahradiť každý prvok poľa bez použitia operátora delenia súčinom každého prvku v poli?
- 23. Nájdite najpodivnejší prvok v poli v logaritmickom čase
- 24. Ako získať ďalší väčší prvok pre každý prvok v kruhovom poli?
- 25. Nájdite počet inverzií poľa?
- 26. Aký je problém zachytávania dažďovej vody?
- záver
Kódovacie rozhovory obsahujú sériu otázok DSA. Mali by ste byť zruční s poliami, ak sa pripravujete na svoj nadchádzajúci technický rozhovor s FAANG alebo iným technologickým podnikom úrovne 1.
Vo väčšine rozhovorov o kódovaní je na druhom mieste za Strings. Pole je zoskupenie súvisiacich dátových prvkov, ktoré sú v pamäti uložené vo vzájomnej tesnej blízkosti.
Keďže sú prepojené so všetkými programovacími jazykmi, ako sú C, C++, Java, Python, Perl a Ruby, sú všade. Pokračujte v čítaní, kde nájdete niektoré praktické problémy s kódovaním a otázky a odpovede na rozhovory založené na poliach.
Python sa v tomto príspevku použije na riešenie problémov s kódovaním, pretože je jednoduchý na používanie, je pochopiteľný a musí ho poznať väčšina z nás.
Poďme začať.
1. Ako definujete pole?
- Skupina súvisiacich dátových typov je pole.
- Polia sú vždy pevné.
- Rovnaký druh premennej je uložený na niekoľkých miestach v objektoch poľa.
- Primitívne typy a referencie na objekty sú s ním kompatibilné.
2. Dynamické polia: Čo sú to? Čo ich odlišuje od Basic Arrays?
Automatické škálovanie, ktoré poskytujú dynamické polia (v jazyku Java označované aj ako pestovateľné polia, polia s meniteľnou veľkosťou, meniteľné polia alebo ArrayLists), je významnou výhodou.
Vždy musíte vopred vedieť, koľko prvkov vaše pole uloží, pretože polia majú pevnú veľkosť. Na druhej strane dynamické pole rastie, keď k nemu pridávate ďalších členov, takže nemusíte vopred poznať jeho presnú veľkosť.
3. Ako sa pole a slovník navzájom líšia?
Toto je základný rad otázok na pohovore, ktoré sa pravidelne kladú. Nasledujú kľúčové rozdiely medzi poliami a slovníkmi:
- Pole je usporiadaný zoznam podobných položiek. Na druhej strane slovník má páry kľúč – hodnota.
- Veľkosti polí sa môžu dynamicky meniť. Takéto dynamické myšlienky v slovníkoch neexistujú.
- Pred použitím poľa je potrebné určiť jeho veľkosť. Veľkosti slovníkov nie je potrebné prispôsobovať.
- Ak chcete zväčšiť veľkosť poľa, použite príkaz Redim. V slovníkoch možno prvok pridať bez deklarácie.
4. Uveďte niektoré výhody a nevýhody polí.
výhody:
- Polia môžu triediť viacero prvkov súčasne.
- ostatné dátových štruktúr, ako sú zásobníky, fronty, prepojené zoznamy, stromy, grafy atď., môžu byť implementované v poli.
- Index možno použiť na dosiahnutie prvku poľa.
Nevýhody:
- Veľkosť poľa musí byť deklarovaná vopred. V momente deklarácie poľa si však nemusíme byť vedomí veľkosti, ktorú požadujeme.
- Štruktúra poľa je statická. Znamená to, že veľkosť poľa je vždy pevná a že alokácia pamäte sa nedá zvýšiť ani znížiť.
5. Čo znamená „Sparse Array“?
Riedke pole je dátové pole, ktoré má veľa položiek s nulovými hodnotami. Naproti tomu husté pole obsahuje väčšinu svojich položiek s nenulovými hodnotami. Indexy riedkeho poľa, ktoré konvertuje čísla na objekty, môžu obsahovať medzery. V porovnaní s HashMap sú pamäťovo efektívnejšie.
6. Kedy by ste zvolili prepojený zoznam pred poľom?
Pri použití prepojených zoznamov namiesto polí zvážte:
- Na náhodný prístup nepotrebujete žiadne prvky.
- Tam, kde je nevyhnutná časová predvídateľnosť, potrebujete neustále vkladanie a odstraňovanie zo zoznamu.
- Ak chcete vytvoriť prioritný front, možno budete musieť umiestniť položky do stredu zoznamu.
- Netušíte, aký dlhý bude zoznam. Ak sa veľkosť poľa zvýši, musíte znova deklarovať a duplikovať pamäť, rovnako ako pri jednoduchých poliach.
7. Čo odlišuje indexované pole od asociatívneho poľa?
Hlavné rozdiely medzi asociatívnymi a indexovanými poliami sú uvedené v nasledujúcej tabuľke.
- Na triedenie asociatívneho poľa sa používa pár kľúč – hodnota v textovom alebo číselnom formáte. Všetky kľúče indexovaného poľa sú číselné a každý kľúč je spojený s odlišnou hodnotou.
- V asociatívnom poli môže byť kľúčom reťazec. Indexované pole s celočíselnými kľúčmi začínajúcimi od 0.
- Dvojstĺpcová tabuľka napodobňuje správanie asociatívneho poľa. Podobne ako jednostĺpcová tabuľka sú indexované polia.
- Mapy sú typ asociatívneho poľa. Indexové pole nie je mapa.
8. Aké výhody má Heap oproti triedeným poliam?
Časová efektívnosť využitia haldy cez triedené polia je kľúčovou výhodou. Zatiaľ čo operácie haldy sú rýchlejšie, triedenie poľa vyžaduje veľa času. Hromada dokáže objaviť najmenší prvok podstatne rýchlejšie, ako je možné triediť pole.
Daná zbierka čísel môže byť usporiadaná jedným z dvoch spôsobov pomocou triedených polí. Na druhej strane, pre danú zbierku čísel môže existovať viac ako jedna potenciálna hromada.
9. Môžeme definovať veľkosť poľa ako zápornú?
Nie, nemôžeme definovať záporné celé číslo ako veľkosť poľa. Ak deklarujeme, nedôjde k chybe počas kompilácie. Počas behu sa však stretneme s výnimkou NegativeArraySizeException.
10. Ako nájdete chýbajúce celé číslo v poli s 1 až 100 prvkami?
Celkovú sériu možno vypočítať použitím nasledujúcej funkcie: n (n + 1) / 2
Táto funkcia bude fungovať iba v prípade, že pole nemá žiadne duplikáty alebo v ňom chýba viac ako jedno celé číslo. Či pole obsahuje duplicitné prvky, môžete pole zoradiť, aby ste zistili, či existujú nejaké ekvivalentné prvky.
11. Ako zistíte index prvku v poli?
Index prvku je možné zistiť pomocou lineárneho alebo binárneho vyhľadávania. Kým nenájde zhodu s požadovaným prvkom, funkcia lineárneho vyhľadávania sa bude opakovať nad každým prvkom v poli. Keď nájde zodpovedajúci prvok, vráti index. V dôsledku toho je časová zložitosť lineárneho vyhľadávania O. (n). Zoradené aj nezoradené pole môže používať lineárne vyhľadávanie.
Pomocou binárneho vyhľadávania, ktoré neustále rozdeľuje pole na polovicu, kým sa medián intervalu nezhoduje s požadovaným prvkom a neposkytne index, môžete získať index prvku, ak je pole zoradené. V dôsledku toho je časová zložitosť binárneho vyhľadávania O. (log n).
12. Ako sa môžete zbaviť konkrétneho prvku z poľa?
Keďže prvky z pôvodného poľa nemôžete jednoducho vymazať, pretože ide o pevné sady s definovanou veľkosťou, anketár sa snaží, aby ste navrhli iný prístup a vysporiadali sa s problémom, ktorý otázka vyvoláva. Najlepším postupom je vytvoriť nové pole na odstránenie prvku. Môžete duplikovať prvky z prvého poľa v tomto poli a zahrnúť iba prvok, ktorý chcete odstrániť.
Ďalšia stratégia zahŕňa nájdenie cieľového prvku v poli a následné obrátenie poradia všetkých položiek, ktoré sú napravo od cieľového prvku.
13. Ako možno overiť rovnosť dvoch polí?
Najprv musíte overiť dĺžky dvoch poskytnutých polí. Zhodné položky oboch polí sa porovnávajú, keď sú ich dĺžky rovnaké. Tieto dve polia sa budú považovať za rovnaké. ak je každá dvojica zložiek v každej korešpondencii rovnaká. Tento prístup sa neodporúča kontrolovať rovnosť dvoch polí, ak sú polia veľké, pretože to zaberie veľa času. Môžete tiež použiť metódu equals() zahrnutú v triede Arrays, avšak ak vás anketár požiada o porovnanie dvoch polí bez použitia vstavaných metód, tento spôsob bude užitočný.
14. Keď hovoríme o poliach, čo máte na mysli pod vetami „Dimenzia“ a „dolný index“?
„Dimenzia“ poľa je počet indexov alebo dolných indexov, ktoré sú potrebné na identifikáciu každého jednotlivého člena. Dolné indexy a rozmery môžu byť nejasné. Dimenzia je popis rozsahu povolených kľúčov, zatiaľ čo dolný index je číslo. Pre každú dimenziu poľa je potrebný iba jeden dolný index.
Napríklad pole arr[10][5] má dva rozmery. Veľkosť 10 na jednej a 5 na druhej. Na riešenie jeho komponentov potrebujete dva dolné indexy. Obidva sú medzi 0 a 4; jedna medzi 0 a 9 vrátane.
Otázky na pohovor o kódovaní
15. Vyhľadajte pár v poli, ktorý má zadaný súčet
Napríklad,
vstup:
- nums = [8, 7, 2, 5, 3, 1]
- cieľ = 10
Výkon:
- Nájdený pár (8, 2)
- Or
- Nájdený pár (7, 3)
vstup:
- nums = [5, 2, 6, 8, 1, 9]
- cieľ = 12
Výkon:
- Pár sa nenašiel
16. Binárne triedenie poľa s lineárnym časom
Zoraďte binárne pole v lineárnom čase a v pevnej oblasti. Výstup by mal najskôr zobraziť všetky nuly, potom všetky jednotky.
Napríklad,
- Vstup: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Výstup: { 0, 0, 0, 0, 1, 1, 1, 1 }
Priamym prístupom by bolo vypočítať celkový počet nul v poli, povedzme k, a potom vyplniť prvých k indexov v poli nulami a zvyšné indexy 0. Alternatívne by sme mohli vypočítať, koľko 0 je celkovo v poli. pole k, vyplňte posledných k indexov v poli 1 a zvyšok indexov nechajte vyplnený 1.
Daný prístup má časovú zložitosť O(n) a nepoužíva žiadne dodatočné úložisko, kde n je veľkosť vstupu.
17. Nájdite najväčší dvojintový súčin v poli.
Nájdite najväčší súčin dvoch čísel v celočíselnom poli.
Predstavte si pole 10 3 5 6 2 ako príklad. Dvojica (-10, -3) alebo (5, 6) je najvyšší súčin.
Premýšľať o každej kombinácii prvkov a zistiť ich produkt je hlúpy prístup. Ak je súčin aktuálneho páru väčší ako maximálny súčin získaný doteraz, aktualizujte maximálny súčin. Ako posledné vytlačte komponenty konečného produktu.
Vyššie uvedené riešenie, kde n je množstvo vstupu, má časovú zložitosť O(n2) a nezaberá viac miesta.
18. Ako posunúť všetky nuly poľa na koniec
Presuňte všetky nuly v celočíselnom poli na koniec. Odpoveď by sa mala vyhnúť používaniu konštantného priestoru a zachovať relatívne poradie komponentov poľa.
Vstup: {1,2,3,0,8,0,4,7}
Výstup bude {1,2,3,8,4,7,0,0}
Ak aktuálny prvok nie je nula, umiestnite prvok na nasledujúcu dostupnú pozíciu v poli. Po spracovaní všetkých položiek poľa vyplňte všetky zostávajúce indexy 0.
Predchádzajúce riešenie má časovú zložitosť O(n), kde n je veľkosť vstupu.
19. Ako zoradiť pole s dvoma položkami, ktoré sa prepínajú v jednej operácii.
Zoraďte pole v lineárnom čase za predpokladu, že dve vymenené položky a pole so všetkými jeho prvkami usporiadané vzostupne. Predstierajte, že pole neobsahuje žiadne duplikáty.
Vstup:= [1,9,3,4,7,2] alebo [9,3,7,2,1,4] alebo [2,4,1,7,3,9]
Výstup: = [1,2,3,4,7,9]
Počnúc druhým prvkom v poli je cieľom porovnať každý prvok s jeho predchodcom. Pozícia sporu sa uloží pomocou dvoch ukazovateľov, x a y.
Aktualizujte x na index predchádzajúceho prvku a y na index aktuálneho prvku, ak je prvý väčší ako druhý. Aktualizujte y na index aktuálneho prvku, ak sa ukáže, že predchádzajúci prvok je väčší ako aktuálny prvok.
Nakoniec prepnite prvky na indexoch x a y, keď dokončíme spracovanie každého susedného páru prvkov.
Vzhľadom na skutočnosť, že vyššie uvedená metóda vykonáva iba jeden sken vstupného poľa veľkosti n, jej časová zložitosť je O(n). Pre riešenie nie je potrebný žiadny ďalší priestor.
20. Ako skombinovať dve zoradené polia na mieste.
Zlúčte položky polí X[] a Y[] – každé dve zoradené polia veľkosti m a n – zachovaním zoradeného poradia, t. j. vyplnením X[] prvými m najmenšími prvkami a vyplnením Y[] zostávajúce prvky.
Ak je prvok v poli X[] už na správnej pozícii (tj ten, ktorý je najmenší spomedzi ostatných prvkov), ignorujte ho; v opačnom prípade ho nahraďte najmenším prvkom, ktorý je tiež prvým členom Y[]. Ak chcete zachovať zoradené poradie po výmene, preneste prvok (teraz na Y[0]) na správne miesto v Y[].
Veľkosť prvého poľa je m a veľkosť druhého poľa je n a časová zložitosť je O(mn).
21. Ako zmeniť poradie radu položiek v striedaní vysokých a nízkych pozícií?
Usporiadajte celočíselné pole tak, aby každý nasledujúci člen bol väčší ako predchádzajúci a nasledujúci prvok. Predpokladajme, že pole neobsahuje žiadne duplicitné prvky.
Pre efektívny prístup nie je potrebné triedenie poľa alebo využitie dodatočného priestoru. Plán je, na začiatok, druhý člen poľa a ísť hore o dva pre každú iteráciu cyklu.
Vymeňte komponenty, ak posledný prvok presahuje prvý. V podobnom duchu prepnite obe položky, ak je nasledujúci prvok väčší ako aktuálny prvok. Na konci cyklu získame požadované pole, ktoré vyhovuje špecifikovaným obmedzeniam.
22. Ako nahradiť každý prvok poľa bez použitia operátora delenia súčinom každého prvku v poli?
Bez použitia operátora delenia nahraďte každý prvok v celočíselnom poli súčinom všetkých ostatných prvkov.
V lineárnom čase a konštantnom priestore môžeme na riešenie tohto problému použiť rekurziu. Ide o rekurzívny výpočet súčinov každého prvku v pravom podpole a odovzdanie súčinu ľavého podpolia ako funkčných parametrov.
Časová zložitosť je O(n).
23. Nájdite najpodivnejší prvok v poli v logaritmickom čase
Vzhľadom na celočíselné pole, v ktorom majú všetky členy okrem jedného párny počet výskytov, je problém určiť, koľkokrát sa tento jeden prvok objaví. Nájdite nepárny prvok v logaritmickom čase a konštantnom priestore, ak sa rovnaké prvky vyskytujú v pároch v poli a nikdy nemôžu byť viac ako dva výskyty daného prvku v rade.
Operácia XOR nám umožňuje vyriešiť tento problém v lineárnom čase. Cieľom je XOR každý prvok v poli. Po vzájomnom zrušení párne sa vyskytujúcich prvkov zostanú len nepárne prvky.
Tento problém možno dokonca vyriešiť v čase O(log(n)).
24. Ako získať ďalší väčší prvok pre každý prvok v kruhovom poli?
Mal by byť umiestnený ďalší väčší prvok pre každý prvok v kruhovom celočíselnom poli. Prvé väčšie celé číslo po prvku x v poli je nasledujúci väčší prvok tohto prvku.
Sprava doľava môžeme pracovať s položkami poľa. Cieľom je cyklovať pre každý prvok x, až kým nie je zásobník prázdny alebo nad ním nemáme vyšší prvok. Nastavte ďalší väčší prvok x, aby sa objavil na vrchu zásobníka, keď sa tak stane.
25. Nájdite počet inverzií poľa?
Nájdite celkový počet inverzií poľa. Pár Ij) sa označuje ako inverzia poľa A, ak Ij) a (A[i] > A[j]). Musíme spočítať každý pár z nich v poli.
Počítanie všetkých členov poľa, ktorých je napravo od neho menej, a pridanie výsledku k výstupu je jednoduchý prístup.
Toto riešenie má zložitosť O(n2), kde n je veľkosť vstupu.
26. Aký je problém zachytávania dažďovej vody?
Nájdenie najväčšieho množstva vody, ktorá môže byť zachytená v danej sade tyčí so šírkou jednej jednotky, je známe ako problém „zachytenia zrážok“.
Cieľom je určiť najvyššiu lištu, ktorá môže byť umiestnená vľavo a vpravo od každej lišty. Minimálne množstvo vodiacich pruhov vľavo a vpravo, mínus výška aktuálneho pruhu, je množstvo vody, ktoré je uložené na vrchu každého pruhu.
záver
V porovnaní s inými témami o štruktúre údajov sú polia jednoduchšie. Aby ste mohli odpovedať na otázky na pohovore s poľami, musíte mať základné znalosti o poliach.
Mali by ste si dôkladne preštudovať základy polí vrátane operácií s poľami (od deklarovania/vytvorenia poľa po prístup/úpravu položiek poľa), ako aj programovacie koncepty, ako sú slučky, rekurzia a základné operátory, aby ste úspešne odpovedali na otázky týkajúce sa rozhovoru s poľami. Úplne rozpoznajte problém.
Ak máte nejaké otázky, mali by ste požiadať o vysvetlenie. Zamyslite sa nad rozdelením problému na viac zvládnuteľné časti. Pred začatím programovania sa uistite, že máte na pamäti algoritmus; zapíšte si to alebo si to vizualizujte vo vývojovom diagrame. potom začnite písať kód.
Nechaj odpoveď