Saturs[Paslēpt][Rādīt]
- 1. Kā jūs definējat masīvu?
- 2. Dinamiskie masīvi: kas tie ir? Kas tos atšķir no pamata masīviem?
- 3. Kā masīvs un vārdnīca atšķiras viens no otra?
- 4. Uzskaitiet dažas masīvu priekšrocības un trūkumus.
- 5. Uz ko attiecas “Sparse Array”?
- 6. Kad jūs izvēlētos saistīto sarakstu, nevis masīvu?
- 7. Kas atšķir indeksētu masīvu no asociatīvā masīva?
- 8. Kādas ir Heap priekšrocības salīdzinājumā ar sakārtotiem masīviem?
- 9. Vai varam definēt masīva lielumu kā negatīvu?
- 10. Kā atrast trūkstošo veselo skaitli masīvā no 1 līdz 100 elementiem?
- 11. Kā masīvā var atrast elementa indeksu?
- 12. Kā var atbrīvoties no konkrēta elementa no masīva?
- 13. Kā var pārbaudīt divu masīvu vienādību?
- 14. Kad mēs apspriežam masīvus, ko jūs domājat ar frāzēm "Dimensija" un "Apakšraksts"?
- Kodēšanas intervijas jautājumi
- 15. Meklējiet pāri masīvā, kuram ir norādītā summa
- 16. Bināro masīvu šķirošana ar lineāro laiku
- 17. Atrodiet masīvā lielāko divu indu reizinājumu.
- 18. Kā nobīdīt visas masīva nulles uz beigām
- 19. Kā sakārtot masīvu ar diviem ierakstiem, kas tiek pārslēgti vienā operācijā.
- 20. Kā apvienot divus sakārtotus masīvus vietā.
- 21. Kā pārkārtot preču masīvu pārmaiņus augstās un zemās pozīcijās?
- 22. Kā aizvietot katru masīva elementu, neizmantojot dalīšanas operatoru ar katra elementa reizinājumu masīvā?
- 23. Atrast masīvā nepāraāko elementu logaritmiskajā laikā
- 24. Kā iegūt nākamo lielāku elementu katram elementam apļveida masīvā?
- 25. Atrast masīva inversiju skaitu?
- 26. Kas ir lietus ūdens uztveršanas problēma?
- Secinājumi
Kodēšanas intervijas satur virkni DSA jautājumu. Ja gatavojaties gaidāmajai tehniskajai intervijai ar FAANG vai citu Tier-1 tehnoloģiju uzņēmumu, jums ir jābūt prasmīgam ar masīviem.
Lielākajā daļā kodēšanas interviju tā ieņem otro vietu pēc Strings. Masīvs ir saistītu datu elementu grupa, kas atmiņā tiek glabāta tuvu viens otram.
Tā kā tie ir savienoti ar visām programmēšanas valodām, piemēram, C, C++, Java, Python, Perl un Ruby, tās ir visur. Turpiniet lasīt dažus prakses kodēšanas izaicinājumus un interviju jautājumus un atbildes, kuru pamatā ir masīvi.
Python tiks izmantots šajā ziņojumā, lai risinātu kodēšanas problēmas, jo tas ir vienkārši lietojams, saprotams, un tas ir pazīstams lielākajai daļai no mums.
Sāksim.
1. Kā jūs definējat masīvu?
- Saistītu datu tipu grupa ir masīvs.
- Masīvi vienmēr ir fiksēti.
- Tāda paša veida mainīgo masīva objekti glabā vairākās vietās.
- Ar to ir saderīgi gan primitīvie tipi, gan objektu atsauces.
2. Dinamiskie masīvi: kas tie ir? Kas tos atšķir no pamata masīviem?
Automātiskā mērogošana, ko nodrošina dinamiskie masīvi (Java valodā saukti arī par paplašināmiem masīviem, maināmiem masīviem, maināmiem masīviem vai ArrayLists) ir būtiska priekšrocība.
Jums vienmēr iepriekš jāzina, cik elementu jūsu masīvs saglabās, jo masīviem ir noteikts izmērs. No otras puses, dinamiskais masīvs palielinās, pievienojot tam papildu dalībniekus, tāpēc jums nav iepriekš jāzina precīzs tā lielums.
3. Kā masīvs un vārdnīca atšķiras viens no otra?
Šis ir uz pamatiem balstīts intervijas jautājumu kopums, kas tiek regulāri uzdots. Tālāk ir norādītas galvenās atšķirības starp masīviem un vārdnīcām.
- Masīvs ir sakārtots līdzīgu vienumu saraksts. No otras puses, vārdnīcā ir atslēgu un vērtību pāri.
- Masīvu izmēri var dinamiski mainīties. Šādas dinamiskas idejas vārdnīcās nepastāv.
- Pirms masīva izmantošanas ir jānorāda tā lielums. Vārdnīcas izmēri nav jāpielāgo.
- Izmantojiet Redim paziņojumu, ja vēlaties paplašināt masīva lielumu. Vārdnīcās elementu var pievienot bez deklarācijas.
4. Uzskaitiet dažas masīvu priekšrocības un trūkumus.
Priekšrocības:
- Masīvi var kārtot vairākus elementus vienlaikus.
- cits datu struktūras, piemēram, kā skursteņus, rindas, saistītos sarakstus, kokus, grafikus utt., var ieviest masīvā.
- Indeksu var izmantot, lai sasniegtu masīva elementu.
Trūkumi:
- Masīva lielums ir jādeklarē iepriekš. Tomēr masīva deklarēšanas brīdī mēs, iespējams, neapzināsim nepieciešamo izmēru.
- Masīva struktūra ir statiska. Tas nozīmē, ka masīva lielums vienmēr ir fiksēts un ka atmiņas sadalījumu nevar palielināt vai samazināt.
5. Uz ko attiecas “Sparse Array”?
Rets masīvs ir datu masīvs, kurā ir daudz ierakstu ar nulles vērtībām. Turpretim blīvs masīvs satur lielāko daļu vienumu ar vērtībām, kas nav nulles. Reta masīva indeksos, kas pārvērš skaitļus objektos, var būt atstarpes. Salīdzinot ar HashMap, tie ir efektīvāki atmiņu.
6. Kad jūs izvēlētos saistīto sarakstu, nevis masīvu?
Ja masīvu vietā izmantojat saistītos sarakstus, ņemiet vērā:
- Lai iegūtu nejaušu piekļuvi, jums nav nepieciešami nekādi elementi.
- Ja ir būtiska laika paredzamība, jums ir jāveic pastāvīga ievietošana un noņemšana no saraksta.
- Lai izveidotu prioritāru rindu, iespējams, būs jāievieto vienumi saraksta centrā.
- Jums nav ne jausmas, cik garš būs saraksts. Ja masīva lielums palielinās, jums ir atkārtoti jādeklarē un jādublē atmiņa, tāpat kā ar vienkāršiem masīviem.
7. Kas atšķir indeksētu masīvu no asociatīvā masīva?
Galvenās atšķirības starp asociatīvajiem un indeksētajiem masīviem ir norādītas nākamajā tabulā.
- Asociatīvā masīva kārtošanai tiek izmantots atslēgas-vērtības pāris teksta vai ciparu formātā. Visas indeksētā masīva atslēgas ir ciparu, un katra atslēga ir saistīta ar noteiktu vērtību.
- Asociatīvajā masīvā atslēga var būt virkne. Indeksēts masīvs ar veseliem skaitļiem, kas sākas ar 0.
- Divu kolonnu tabula atdarina asociatīvā masīva darbību. Līdzīgi vienas kolonnas tabulai ir indeksēti masīvi.
- Kartes ir asociatīvs masīvu veids. Indeksa masīvs nav karte.
8. Kādas ir Heap priekšrocības salīdzinājumā ar sakārtotiem masīviem?
Galvenais ieguvums ir laika efektivitāte, izmantojot Heap, salīdzinot ar sakārtotajiem masīviem. Lai gan kaudzes darbības ir ātrākas, masīva kārtošana prasa daudz laika. Kaudze var atklāt mazāko elementu ievērojami ātrāk nekā masīvu var sakārtot.
Noteiktu skaitļu kolekciju var sakārtot vienā no diviem veidiem, izmantojot sakārtotos masīvus. No otras puses, konkrētai skaitļu kolekcijai var būt vairāk nekā viena potenciālā kaudze.
9. Vai varam definēt masīva lielumu kā negatīvu?
Nē, mēs nevaram definēt negatīvu veselu skaitli kā masīva lielumu. Ja mēs paziņosim, kompilēšanas laika kļūda nebūs. Tomēr izpildlaikā mēs saskarsimies ar NegativeArraySizeException.
10. Kā atrast trūkstošo veselo skaitli masīvā no 1 līdz 100 elementiem?
Sērijas kopsummu var aprēķināt, izmantojot šādu funkciju: n (n + 1) / 2
Šī funkcija darbosies tikai tad, ja masīvam nav dublikātu vai trūkst vairāk nekā viena vesela skaitļa. Neatkarīgi no tā, vai masīvam ir elementu dublikāti, varat kārtot masīvu, lai redzētu, vai ir kādi elementi, kas ir līdzvērtīgi.
11. Kā masīvā var atrast elementa indeksu?
Elementa indeksu var atklāt, izmantojot lineāro vai bināro meklēšanu. Līdz brīdim, kad tiek atrasta atbilstība vajadzīgajam elementam, lineārā meklēšanas funkcija cilpas pār katru masīva elementu. Tas atgriež indeksu, tiklīdz tiek atrasts atbilstošs elements. Līdz ar to lineārās meklēšanas laika sarežģītība ir O. (n). Gan sakārtots, gan nešķirots masīvs var izmantot lineāro meklēšanu.
Izmantojot bināro meklēšanu, kas nepārtraukti sadala masīvu uz pusēm, līdz intervāla mediāna atbilst vajadzīgajam elementam un nodrošina indeksu, varat iegūt elementa indeksu, ja masīvs ir sakārtots. Līdz ar to binārās meklēšanas laika sarežģītība ir O. (log n).
12. Kā var atbrīvoties no konkrēta elementa no masīva?
Tā kā jūs nevarat vienkārši izdzēst elementus no sākotnējā masīva, jo tie ir fiksētas kopas ar noteiktu izmēru, intervētājs vēlas, lai jūs ieteiktu citu pieeju un risinātu problēmas, ko rada jautājums. Labākais darbības veids ir izveidot jaunu masīvu, lai dzēstu elementu. Šajā masīvā varat dublēt elementus no pirmā masīva un iekļaut tikai to elementu, kuru vēlaties dzēst.
Cita stratēģija ietver mērķa elementa atrašanu masīvā un pēc tam visu to vienumu secības apmaiņu, kas atrodas pa labi no mērķa elementa.
13. Kā var pārbaudīt divu masīvu vienādību?
Vispirms ir jāpārbauda divu nodrošināto masīvu garums. Abu masīvu atbilstošie vienumi tiek salīdzināti, ja to garumi ir vienādi. Abi masīvi tiks uzskatīti par vienādiem. ja katrs komponentu pāris katrā atbilstībā ir vienāds. Šī pieeja nav ieteicama, lai pārbaudītu divu masīvu vienādību, ja masīvi ir lieli, jo tas prasīs daudz laika. Varat arī izmantot masīvu klasē iekļauto metodi equals(), taču, ja intervētājs lūdz salīdzināt divus masīvus, neizmantojot iebūvētās metodes, šis veids būs noderīgs.
14. Kad mēs apspriežam masīvus, ko jūs domājat ar frāzēm "Dimensija" un "Apakšraksts"?
Masīva “dimensija” ir indeksu vai apakšindeksu skaits, kas nepieciešams, lai identificētu katru atsevišķu dalībnieku. Apakšraksti un izmēri var būt neskaidri. Dimensija ir atļauto atslēgu diapazona apraksts, savukārt apakšindekss ir skaitlis. Katrai masīva dimensijai ir nepieciešams tikai viens apakšindekss.
Piemēram, masīvam arr[10][5] ir divas dimensijas. Vienam 10, otram 5 izmērs. Lai risinātu tās sastāvdaļas, ir nepieciešami divi apakšindeksi. Abi ir no 0 līdz 4; viens no 0 līdz 9, ieskaitot.
Kodēšanas intervijas jautājumi
15. Meklējiet pāri masīvā, kuram ir norādītā summa
Piemēram,
Ieeja:
- skaitļi = [8, 7, 2, 5, 3, 1]
- mērķis = 10
Output:
- Pāris atrasts (8, 2)
- Or
- Pāris atrasts (7, 3)
Ieeja:
- skaitļi = [5, 2, 6, 8, 1, 9]
- mērķis = 12
Output:
- Pāris nav atrasts
16. Bināro masīvu šķirošana ar lineāro laiku
Kārtot bināro masīvu lineārā laikā un fiksētā apgabalā. Izvadā vispirms ir jāparāda visas nulles, pēc tam visas vieninieki.
Piemēram,
- Ievade: {1, 0, 1, 0, 1, 0, 0, 1}
- Izvade: {0, 0, 0, 0, 1, 1, 1, 1}
Vienkārša pieeja būtu aprēķināt masīva kopējo 0 skaitu, piemēram, k, un pēc tam pirmos k indeksus masīvā aizpildīt ar 0 un pārējos indeksus ar 1. Kā alternatīvu mēs varam aprēķināt, cik 1 ir kopā masīvs k, aizpildiet pēdējos k rādītājus masīvā ar 1 un atstājiet pārējos indeksus aizpildītus ar 0.
Dotajai pieejai ir O(n) laika sarežģītība, un tā neizmanto papildu krātuvi, kur n ir ievades lielums.
17. Atrodiet masīvā lielāko divu indu reizinājumu.
Atrodiet divu skaitļu lielāko reizinājumu veselā masīvā.
Padomājiet par masīvu 10 3 5 6 2 kā piemēru. Pāris (-10, -3) vai (5, 6) ir augstākais produkts.
Pārdomāt katru elementu kombināciju un izdomāt to produktu ir muļķīga pieeja. Ja pašreizējā pāra reizinājums ir lielāks par līdz šim iegūto maksimālo preci, atjauniniet maksimālo preci. Pēdējā izdrukājiet gala produkta sastāvdaļas.
Iepriekš minētā risinājuma, kur n ir ievades apjoms, laika sarežģītība ir O(n2), un tas neaizņem vairāk vietas.
18. Kā nobīdīt visas masīva nulles uz beigām
Pārvietojiet visas nulles veselu skaitļu masīvā līdz beigām. Atbildei vajadzētu izvairīties no pastāvīgas telpas izmantošanas un saglabāt masīva komponentu relatīvo secību.
Ieeja: {1,2,3,0,8,0,4,7}
Izvade būs {1,2,3,8,4,7,0,0}
Ja pašreizējais elements nav nulle, novietojiet elementu tālāk norādītajā pieejamajā masīva pozīcijā. Kad visi masīva vienumi ir apstrādāti, aizpildiet visus atlikušos indeksus ar 0.
Iepriekšējam risinājumam ir O(n) laika sarežģītība, kur n ir ievades lielums.
19. Kā sakārtot masīvu ar diviem ierakstiem, kas tiek pārslēgti vienā operācijā.
Kārtojiet masīvu lineārajā laikā, ņemot vērā divus apmainītos vienumus un masīvu ar visiem tā elementiem, kas sakārtoti augošā secībā. Izliecieties, ka masīvā nav dublikātu.
Ievade:= [1,9,3,4,7,2] vai [9,3,7,2,1,4] vai [2,4,1,7,3,9]
Izvade: = [1,2,3,4,7,9]
Sākot ar otro elementu masīvā, mērķis ir salīdzināt katru elementu ar tā priekšgājēju. Strīda pozīcija tiek saglabāta, izmantojot divus rādītājus x un y.
Atjauniniet x uz iepriekšējā elementa indeksu un y uz pašreizējā elementa indeksu, ja pirmais ir lielāks par otro. Atjauniniet y uz pašreizējā elementa indeksu, ja izrādās, ka iepriekšējais elements ir lielāks par pašreizējo elementu.
Visbeidzot, pārslēdziet elementus indeksos x un y, kad esam pabeiguši katra blakus esošā elementu pāra apstrādi.
Sakarā ar to, ka iepriekšminētā metode veic tikai vienu n izmēra ievades masīva skenēšanu, tās laika sarežģītība ir O(n). Risinājumam nav nepieciešama papildu telpa.
20. Kā apvienot divus sakārtotus masīvus vietā.
Apvienojiet masīvu X[] un Y[] vienumus — divus sakārtotus masīvus, kuru izmērs ir m un n —, saglabājot sakārtoto secību, tas ir, aizpildot X[] ar pirmajiem m mazākajiem elementiem un aizpildot Y[] ar atlikušie elementi.
Ja elements masīvā X[] jau atrodas pareizajā pozīcijā (ti, tajā, kas ir mazākā starp atlikušajiem elementiem), neņemiet to vērā; pretējā gadījumā aizstājiet to ar mazāko elementu, kas arī ir Y[] pirmais dalībnieks. Lai saglabātu sakārtoto secību pēc apmaiņas, pārvietojiet elementu (tagad pie Y[0]) uz tā pareizo vietu Y[].
Pirmā masīva izmērs ir m, otrā masīva izmērs ir n, un laika sarežģītība ir O(mn).
21. Kā pārkārtot preču masīvu pārmaiņus augstās un zemās pozīcijās?
Pārkārtojiet veselu skaitļu masīvu tā, lai katrs nākamais elements būtu lielāks par iepriekšējo un nākamo elementu. Pieņemsim, ka masīvā nav dublētu elementu.
Masīva šķirošana vai papildu vietas izmantošana efektīvai pieejai nav nepieciešama. Sākumā plāns ir masīva otrais dalībnieks un palielinās par diviem katrai cilpas iterācijai.
Apmainiet komponentus, ja pēdējais elements pārsniedz pirmo. Līdzīgā veidā pārslēdziet abus vienumus, ja nākamais elements ir lielāks par pašreizējo elementu. Mēs iegūsim vēlamo masīvu, kas atbilst norādītajiem ierobežojumiem cilpas noslēgumā.
22. Kā aizvietot katru masīva elementu, neizmantojot dalīšanas operatoru ar katra elementa reizinājumu masīvā?
Neizmantojot dalīšanas operatoru, aizstājiet katru veselu skaitļu masīva elementu ar visu pārējo elementu reizinājumu.
Lineārā laikā un nemainīgā telpā mēs varam izmantot rekursiju, lai risinātu šo problēmu. Ir jēdziens rekursīvi aprēķināt katra labā apakšmasīva elementa reizinājumus un nodot kreisā apakšgrupas reizinājumu kā funkcijas parametrus.
Laika sarežģītība ir O(n).
23. Atrast masīvā nepāraāko elementu logaritmiskajā laikā
Ņemot vērā veselu skaitļu masīvu, kurā visiem dalībniekiem, izņemot vienu, ir pāra gadījumu skaits, problēma ir noteikt, cik reižu šis viens elements parādās. Atrodiet nepāra sastopamo elementu logaritmiskajā laikā un nemainīgajā telpā, ja vieni un tie paši elementi masīvā sastopami pa pāriem un vienā rindā nevar būt vairāk par diviem dotā elementa gadījumiem.
XOR darbība ļauj mums atrisināt šo problēmu lineārā laikā. Mērķis ir veikt XOR katru masīva elementu. Tikai nepāra sastopamie elementi paliek pēc tam, kad pāra sastopamie elementi izdzēš viens otru.
Šo problēmu var atrisināt pat O(log(n)) laikā.
24. Kā iegūt nākamo lielāku elementu katram elementam apļveida masīvā?
Jāatrodas nākamajam lielākajam elementam katram elementam apļveida veselo skaitļu masīvā. Pirmais lielākais veselais skaitlis pēc elementa x masīvā ir nākamais lielākais šī elementa elements.
No labās puses uz kreiso mēs varam strādāt ar masīva vienumiem. Mērķis ir veikt cilpu katram elementam x, līdz kaudze ir tukša, vai arī virs tās ir augstāks elements. Iestatiet, lai nākamais lielākais x elements tiktu parādīts kaudzes augšpusē, kad tas parādās.
25. Atrast masīva inversiju skaitu?
Atrodiet kopējo masīva inversiju skaitu. Pāri I j) sauc par masīva A inversiju, ja I j) un (A[i] > A[j]). Mums ir jāsaskaita katrs to pāris masīvā.
Visu masīva locekļu, kuru skaits ir mazāks par to labajā pusē, saskaitīšana un rezultāta pievienošana izvadei ir vienkārša pieeja.
Šim risinājumam ir O(n2) sarežģītība, kur n ir ievades lielums.
26. Kas ir lietus ūdens uztveršanas problēma?
Vislielākā ūdens daudzuma atrašana, ko var iesprostīt noteiktā stieņu komplektā ar vienas vienības platumu, tiek dēvēta par “nokrišņu ieslodzīšanas” problēmu.
Mērķis ir noteikt augstāko joslu, ko var novietot pa kreisi un pa labi no katras joslas. Vadošo stieņu minimums pa kreisi un pa labi, atskaitot pašreizējās joslas augstumu, ir ūdens daudzums, kas tiek uzglabāts katra stieņa augšpusē.
Secinājumi
Salīdzinot ar citām datu struktūras tēmām, masīvi ir vienkāršāki. Lai atbildētu uz masīvu intervijas jautājumiem, jums ir jābūt fundamentālai izpratnei par masīviem.
Lai sekmīgi atbildētu uz masīva intervijas jautājumiem, jums rūpīgi jāpārskata masīvu pamati, tostarp masīvu darbības (no masīva deklarēšanas/izveidošanas līdz piekļuvei/pārveidošanai masīva vienumiem), kā arī programmēšanas koncepcijas, piemēram, cilpas, rekursija un pamata operatori. Atzīstiet problēmu pilnībā.
Ja jums ir kādi jautājumi, jums jāmeklē skaidrojums. Padomājiet par jautājuma sadalīšanu vieglāk pārvaldāmās daļās. Pirms programmēšanas sākšanas pārliecinieties, ka esat padomājis par algoritmu; pierakstiet to vai vizualizējiet to blokshēmā. pēc tam sāciet rakstīt kodu.
Atstāj atbildi