Tabl Cynnwys[Cuddio][Dangos]
- 1. Sut ydych chi'n diffinio Arae?
- 2. Araeau Dynamig: Beth Ydyn nhw? Beth sy'n eu gosod ar wahân i Araeau Sylfaenol?
- 3. Sut mae arae a geiriadur yn amrywio oddi wrth ei gilydd?
- 4. Rhestrwch rai o fanteision ac anfanteision araeau.
- 5. At beth mae “Sparse Array” yn cyfeirio?
- 6. Pryd fyddech chi'n dewis rhestr gysylltiedig dros gyfres?
- 7. Beth sy'n gwahaniaethu arae wedi'i fynegeio oddi wrth arae gysylltiadol?
- 8. Pa fanteision sydd gan Heap dros araeau wedi'u didoli?
- 9. A allwn ni ddiffinio maint yr arae i fod yn negyddol?
- 10. Sut ydych chi'n lleoli'r cyfanrif coll mewn arae 1 i 100 elfen?
- 11. Sut ydych chi'n dod o hyd i fynegai elfen mewn arae?
- 12. Sut allwch chi gael gwared ar elfen benodol o arae?
- 13. Sut y gellir gwirio cydraddoldeb dwy arae?
- 14. Pan fyddwn yn trafod araeau, beth ydych chi'n ei olygu wrth yr ymadroddion “Dimension” a “Subscript”?
- Codio Cwestiynau Cyfweliad
- 15. Chwiliwch am bâr mewn cyfres sydd â'r swm penodedig
- 16. Trefnu arae deuaidd gydag amser llinol
- 17. Darganfyddwch y cynnyrch dwy-int mwyaf mewn arae.
- 18. Sut i symud holl sero'r arae i'r diwedd
- 19. Sut i ddidoli arae gyda dau gofnod sy'n cael eu troi mewn un llawdriniaeth.
- 20. Sut i gyfuno dwy arae wedi'u didoli yn eu lle.
- 21. Sut i aildrefnu amrywiaeth o eitemau mewn safleoedd uchel ac isel bob yn ail?
- 22. Sut i amnewid pob elfen o arae heb ddefnyddio gweithredydd rhannu gyda chynnyrch pob elfen yn yr arae?
- 23. Darganfyddwch yr elfen oddest mewn arae mewn amser logarithmig
- 24. Sut i gael yr elfen fwy dilynol ar gyfer pob elfen mewn arae gylchol?
- 25. Darganfod cyfrif gwrthdroad arae?
- 26. Beth Yw'r Broblem Trapio Dwr Glaw?
- Casgliad
Mae cyfweliadau codio yn cynnwys cyfres o gwestiynau DSA. Dylech fod yn fedrus gydag araeau os ydych chi'n paratoi ar gyfer eich cyfweliad technoleg sydd ar ddod gyda FAANG neu fusnes technoleg Haen-1 arall.
Yn y rhan fwyaf o gyfweliadau codio, mae'n dod yn ail i Strings. Mae arae yn grŵp o elfennau data cysylltiedig a gedwir yn agos at ei gilydd yn y cof.
Gan eu bod yn gysylltiedig â phob iaith raglennu, fel C, C ++, Java, Python, Perl, a Ruby, maen nhw ym mhobman. Parhewch i ddarllen am rai heriau codio ymarfer a chyfweld cwestiynau ac atebion yn seiliedig ar araeau.
Bydd Python yn cael ei ddefnyddio yn y swydd hon i fynd i'r afael â'r materion codio oherwydd ei fod yn syml i'w ddefnyddio, ei ddeall, a rhaid iddo fod yn gyfarwydd i'r rhan fwyaf ohonom.
Dewch i ni.
1. Sut ydych chi'n diffinio Arae?
- Mae grŵp o fathau o ddata cysylltiedig yn arae.
- Mae araeau bob amser yn sefydlog.
- Mae'r un math o newidyn yn cael ei storio mewn sawl man gan wrthrychau arae.
- Mae mathau cyntefig a chyfeiriadau gwrthrych ill dau yn gydnaws ag ef.
2. Araeau Dynamig: Beth Ydyn nhw? Beth sy'n eu gosod ar wahân i Araeau Sylfaenol?
Mae'r graddio awtomatig y mae araeau deinamig (y cyfeirir atynt hefyd fel araeau y gellir eu tyfu, araeau y gellir eu hailfeintio, araeau cyfnewidiol, neu ArrayLists yn Java) yn eu darparu yn fantais sylweddol.
Rhaid i chi bob amser wybod faint o elfennau y bydd eich arae yn eu storio ymlaen llaw gan fod gan araeau faint sefydlog. Mae amrywiaeth ddeinamig, ar y llaw arall, yn tyfu wrth i chi ychwanegu aelodau ychwanegol ato, felly nid oes angen i chi wybod ei union faint ymlaen llaw.
3. Sut mae arae a geiriadur yn amrywio oddi wrth ei gilydd?
Mae hwn yn gyfres o gwestiynau cyfweliad sy'n seiliedig ar hanfodion a ofynnir yn rheolaidd. Mae'r canlynol yn wahaniaethau allweddol rhwng araeau a geiriaduron:
- Mae arae yn rhestr drefnus o eitemau tebyg. Ar y llaw arall, mae gan eiriadur barau gwerth allweddol.
- Gall meintiau arae newid yn ddeinamig. Nid yw syniadau deinamig o'r fath yn bodoli mewn geiriaduron.
- Cyn defnyddio amrywiaeth, rhaid nodi ei faint. Nid oes angen addasu meintiau geiriadur.
- Defnyddiwch y datganiad Redim os ydych am ehangu maint yr arae. Mewn geiriaduron, gellir ychwanegu elfen heb ddatganiad.
4. Rhestrwch rai o fanteision ac anfanteision araeau.
Manteision:
- Gall araeau ddidoli nifer o elfennau ar yr un pryd.
- Arall strwythurau data, fel staciau, ciwiau, rhestrau cysylltiedig, coed, graffiau, ac ati, gellir eu gweithredu mewn amrywiaeth.
- Gellir defnyddio mynegai i gyrraedd elfen o arae.
Anfanteision:
- Rhaid datgan maint arae ymlaen llaw. Ar hyn o bryd y byddwn yn datgan arae, efallai na fyddwn, fodd bynnag, yn ymwybodol o'r maint sydd ei angen arnom.
- Mae strwythur yr arae yn statig. Mae'n awgrymu bod maint yr arae bob amser yn sefydlog ac na ellir cynyddu neu leihau dyraniad cof.
5. At beth mae “Sparse Array” yn cyfeirio?
Mae arae denau yn arae ddata sydd â llawer o gofnodion â gwerthoedd sero. Mewn cyferbyniad, mae arae trwchus yn cynnwys y mwyafrif o'i eitemau â gwerthoedd nad ydynt yn sero. Gall mynegeion arae denau, sy'n trosi rhifau yn wrthrychau, gynnwys bylchau. O'u cymharu â HashMap, maent yn fwy cof-effeithlon.
6. Pryd fyddech chi'n dewis rhestr gysylltiedig dros gyfres?
Wrth ddefnyddio rhestrau cysylltiedig yn lle araeau, ystyriwch:
- Nid oes angen unrhyw elfennau arnoch i gael mynediad ar hap.
- Lle mae rhagweladwyedd amser yn hanfodol, mae angen mewnosod amser cyson a thynnu oddi ar y rhestr.
- Er mwyn creu ciw blaenoriaeth, efallai y bydd angen i chi osod eitemau yng nghanol y rhestr.
- Nid oes gennych unrhyw syniad pa mor hir fydd y rhestr. Os bydd maint yr arae yn codi, rhaid i chi ail-ddatgan a dyblygu cof, yn union fel gydag araeau syml.
7. Beth sy'n gwahaniaethu arae wedi'i fynegeio oddi wrth arae gysylltiadol?
Rhestrir y prif wahaniaethau rhwng araeau cysylltiadol a mynegeiedig yn y tabl canlynol.
- Defnyddir pâr gwerth allweddol mewn fformat testun neu rifol i ddidoli arae cysylltiadol. Mae allweddi'r arae wedi'i mynegeio i gyd yn rhifol, ac mae pob allwedd wedi'i chysylltu â gwerth penodol.
- Mewn arae cysylltiadol, efallai mai llinyn yw'r allwedd. Arae wedi'i mynegeio gydag allweddi cyfanrif yn dechrau ar 0.
- Mae tabl dwy golofn yn dynwared ymddygiad arae gysylltiadol. Yn debyg i dabl un golofn mae araeau wedi'u mynegeio.
- Mae mapiau yn fath arae cysylltiadol. Nid map yw arae mynegai.
8. Pa fanteision sydd gan Heap dros araeau wedi'u didoli?
Effeithlonrwydd amser defnyddio Heap over Sorted Arrays yw'r budd allweddol. Er bod gweithrediadau tomen yn gyflymach, mae angen llawer o amser i ddidoli arae. Gall tomen ddarganfod yr elfen leiaf yn llawer cyflymach nag y gellir ei ddidoli arae.
Gellir trefnu casgliad penodol o rifau mewn un o ddwy ffordd gan ddefnyddio Trefnu Araeau. Ar y llaw arall, ar gyfer casgliad penodol o rifau, gall fod mwy nag un domen bosibl.
9. A allwn ni ddiffinio maint yr arae i fod yn negyddol?
Na, ni allwn ddiffinio cyfanrif negyddol fel maint arae. Ni fydd gwall amser crynhoi os byddwn yn datgan. Ar amser rhedeg, fodd bynnag, byddwn yn dod ar draws NegativeArraySizeException.
10. Sut ydych chi'n lleoli'r cyfanrif coll mewn arae 1 i 100 elfen?
Gellir cyfrifo cyfanswm y gyfres trwy gymhwyso'r swyddogaeth ganlynol: n (n + 1) / 2
Dim ond os nad oes gan yr arae unrhyw ddyblygiadau neu os oes mwy nag un cyfanrif ar goll y bydd y swyddogaeth hon yn gweithredu. P'un a oes gan arae elfennau dyblyg, gallwch ddidoli'r arae i weld a oes unrhyw elfennau sy'n cyfateb.
11. Sut ydych chi'n dod o hyd i fynegai elfen mewn arae?
Gellir darganfod mynegai elfen trwy chwiliad llinol neu ddeuaidd. Hyd nes y bydd yn lleoli cyfatebiaeth yr elfen ofynnol, mae swyddogaeth chwilio llinol yn dolennu dros bob elfen mewn arae. Mae'n dychwelyd y mynegai unwaith y bydd wedi lleoli'r elfen gyfatebol. O ganlyniad, cymhlethdod amser y chwiliad llinol yw O. (n). Gall arae wedi'i ddidoli a heb ei drefnu ddefnyddio chwiliad llinol.
Gan ddefnyddio chwiliad deuaidd, sy'n rhannu'r arae yn ei hanner yn barhaus nes bod canolrif yr egwyl yn cyfateb i'r elfen ofynnol ac yn darparu'r mynegai, gallwch gael mynegai'r elfen os yw'r arae wedi'i didoli. O ganlyniad, cymhlethdod amser y chwiliad deuaidd yw O. (log n).
12. Sut allwch chi gael gwared ar elfen benodol o arae?
Gan na allwch ddileu elfennau o'r arae wreiddiol gan eu bod yn setiau sefydlog gyda maint diffiniedig, mae'r cyfwelydd yn ceisio ichi awgrymu dull gwahanol a delio â'r broblem a godir gan y cwestiwn. Y ffordd orau o weithredu yw gwneud arae newydd er mwyn dileu elfen. Gallwch ddyblygu'r elfennau o'r arae gyntaf yn yr arae hon a chynnwys yr elfen yr ydych am ei dileu yn unig.
Mae strategaeth arall yn ymwneud â darganfod yr elfen darged yn yr arae ac yna gwrthdroi trefn yr holl eitemau sydd i'r dde o'r elfen darged.
13. Sut y gellir gwirio cydraddoldeb dwy arae?
Yn gyntaf rhaid i chi wirio hyd y ddwy arae a ddarperir. Mae eitemau cyfatebol y ddwy arae yn cael eu cymharu pan fydd eu hyd yn hafal. Bydd y ddau arae yn cael eu hystyried yn gyfartal. os yw pob pâr o gydrannau ym mhob gohebiaeth yn gyfartal. Ni chynghorir y dull hwn i wirio cydraddoldeb dwy arae os yw'r araeau'n fawr o ran maint gan y bydd yn cymryd llawer o amser. Gallwch hefyd ddefnyddio'r dull hafal() a gynhwysir yn y dosbarth Arrays, fodd bynnag, os bydd y cyfwelydd yn gofyn i chi gymharu dwy arae heb ddefnyddio dulliau adeiledig, bydd y ffordd hon yn ddefnyddiol.
14. Pan fyddwn yn trafod araeau, beth ydych chi'n ei olygu wrth yr ymadroddion “Dimension” a “Subscript”?
“Dimensiwn” arae yw nifer y mynegeion, neu danysgrifiadau, sydd eu hangen i adnabod pob aelod unigol. Gallai tanysgrifiadau a dimensiynau fod yn aneglur. Mae dimensiwn yn ddisgrifiad o'r ystod o allweddi a ganiateir, tra bod tanysgrif yn rhif. Dim ond un tanysgrifiad sydd ei angen ar gyfer pob dimensiwn arae.
Er enghraifft, mae gan yr arae arae[10][5] ddau ddimensiwn. Meintiau 10 ar un a 5 ar y llall. Er mwyn mynd i'r afael â'i gydrannau, mae angen dau danysgrifiad arnoch. Mae'r ddau rhwng 0 a 4; un rhwng 0 a 9, yn gynwysedig.
Codio Cwestiynau Cyfweliad
15. Chwiliwch am bâr mewn cyfres sydd â'r swm penodedig
Er enghraifft,
Mewnbwn:
- nums = [8, 7, 2, 5, 3, 1]
- targed = 10
Allbwn:
- Wedi canfod pâr (8, 2)
- Or
- Wedi canfod pâr (7, 3)
Mewnbwn:
- nums = [5, 2, 6, 8, 1, 9]
- targed = 12
Allbwn:
- Pâr heb ei ganfod
16. Trefnu arae deuaidd gydag amser llinol
Trefnu arae ddeuaidd mewn amser llinol ac mewn ardal sefydlog. Dylai'r allbwn ddangos pob sero yn gyntaf, yna pob un.
Er enghraifft,
- Mewnbwn: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Allbwn: { 0, 0, 0, 0, 1, 1, 1, 1 }
Ymagwedd syml fyddai cyfrifo cyfanswm yr arae o 0s, dyweder k, ac yna llenwi'r mynegeion k cyntaf yn yr arae gyda 0s a'r mynegeion sy'n weddill gydag 1. Fel dewis arall, gallem gyfrifo sawl 1 sy'n gyfanswm yn y arae k, llenwch y mynegeion k olaf yn yr arae gydag 1, a gadewch weddill y mynegeion wedi'u llenwi â 0.
Mae gan y dull a roddir gymhlethdod amser O(n) ac nid yw'n defnyddio storfa ychwanegol, lle mai n yw maint y mewnbwn.
17. Darganfyddwch y cynnyrch dwy-int mwyaf mewn arae.
Darganfyddwch y cynnyrch mwyaf o ddau rif mewn arae cyfanrif.
Meddyliwch am yr arae 10 3 5 6 2 fel enghraifft. Y pâr (-10, -3) neu (5, 6) yw'r cynnyrch uchaf.
Mae meddwl am bob cyfuniad elfen a chyfrif i maes eu cynnyrch yn ddull ffôl. Os yw cynnyrch y pâr presennol yn fwy na'r uchafswm cynnyrch a gafwyd hyd yn hyn, diweddarwch yr uchafswm cynnyrch. Argraffwch gydrannau'r cynnyrch terfynol yn olaf.
Mae gan y datrysiad uchod, lle mae n swm y mewnbwn, gymhlethdod amser o O(n2) ac nid yw'n cymryd mwy o le.
18. Sut i symud holl sero'r arae i'r diwedd
Symudwch yr holl seroau mewn arae cyfanrif i'r diwedd. Dylai'r ateb osgoi defnyddio gofod cyson a chadw trefn gymharol cydrannau'r arae.
Mewnbwn: {1,2,3,0,8,0,4,7}
Yr allbwn fydd {1,2,3,8,4,7,0,0}
Rhowch yr elfen yn y safle canlynol sydd ar gael yn yr arae os nad yw'r elfen gyfredol yn sero. Llenwch yr holl fynegeion sy'n weddill gyda 0 unwaith y bydd holl eitemau'r arae wedi'u prosesu.
Mae gan y datrysiad blaenorol gymhlethdod amser O(n), ac n yw maint y mewnbwn.
19. Sut i ddidoli arae gyda dau gofnod sy'n cael eu troi mewn un llawdriniaeth.
Trefnwch arae yn yr amser llinol a roddir dwy eitem wedi'u cyfnewid ac arae gyda'i holl elfennau wedi'u trefnu mewn trefn esgynnol. Esgus nad yw'r arae yn cynnwys unrhyw ddyblygiadau.
Mewnbwn:= [1,9,3,4,7,2] neu [9,3,7,2,1,4] neu [2,4,1,7,3,9]
Allbwn: = [1,2,3,4,7,9]
Gan ddechrau gyda'r ail elfen yn yr arae, yr amcan yw cymharu pob elfen â'i rhagflaenydd. Mae lleoliad yr anghydfod yn cael ei storio trwy gymryd dau awgrym, x, ac y.
Diweddarwch x i fynegai'r elfen flaenorol ac y i fynegai'r elfen gyfredol os yw'r cyntaf yn fwy na'r olaf. Diweddarwch y i fynegai'r elfen gyfredol os yw'n ymddangos bod yr elfen flaenorol yn fwy na'r elfen gyfredol.
Yn olaf, newidiwch yr elfennau ym mynegeion x ac y unwaith y byddwn wedi gorffen prosesu pob pâr o elfennau cyfagos.
Oherwydd y ffaith mai dim ond un sgan y mae'r dull uchod yn ei wneud o'r arae mewnbwn maint n, ei gymhlethdod amser yw O(n). Nid oes angen ystafell ychwanegol ar gyfer yr ateb.
20. Sut i gyfuno dwy arae wedi'u didoli yn eu lle.
Cyfuno'r eitemau araeau X[] ac Y[]—dwy arae wedi'u didoli o faint m ac n yr un—drwy gadw'r drefn ddidoli, hynny yw, trwy lenwi X[] gyda'r elfennau lleiaf m cyntaf a llenwi Y[] gyda'r elfennau sy'n weddill.
Os yw elfen yn yr arae X[] eisoes yn y safle cywir (hy yr un sydd leiaf ymhlith yr elfennau sy'n weddill), anwybyddwch hi; fel arall, rhowch yr elfen leiaf yn ei le, sydd hefyd yn digwydd bod yn aelod cyntaf Y[]. I gadw'r drefn wedi'i didoli ar ôl cyfnewid, trosglwyddwch yr elfen (yn awr yn Y[0]) i'w lleoliad priodol yn Y[].
Maint yr arae gyntaf yw m a maint yr ail arae yw n, a'r cymhlethdod amser yw O(mn).
21. Sut i aildrefnu amrywiaeth o eitemau mewn safleoedd uchel ac isel bob yn ail?
Aildrefnwch arae cyfanrif fel bod pob aelod dilynol yn fwy na'r elfennau blaenorol a dilynol. Cymryd yn ganiataol nad yw'r arae yn cynnwys unrhyw elfennau dyblyg.
Nid oes angen didoli'r arae neu ddefnyddio gofod ychwanegol ar gyfer ymagwedd effeithiol. Y cynllun, i ddechrau, yw ail aelod yr arae ac aiff i fyny gan ddau ar gyfer pob iteriad dolen.
Cyfnewidiwch y cydrannau os yw'r elfen olaf yn fwy na'r un gyntaf. Yn yr un modd, newidiwch y ddwy eitem os yw'r elfen ganlynol yn fwy na'r elfen gyfredol. Byddwn yn cael yr amrywiaeth a ddymunir sy'n cydymffurfio â'r cyfyngiadau penodedig ar ddiwedd y ddolen.
22. Sut i amnewid pob elfen o arae heb ddefnyddio gweithredydd rhannu gyda chynnyrch pob elfen yn yr arae?
Heb ddefnyddio'r gweithredwr rhannu, disodli pob elfen mewn cyfres gyfanrif gyda chynnyrch yr holl elfennau eraill.
Mewn amser llinol a gofod cyson, gallwn ddefnyddio ailadrodd i fynd i'r afael â'r mater hwn. Y syniad yw cyfrifo cynhyrchion pob elfen yn yr is-arae dde yn rheolaidd a phasio'r cynnyrch is-arae chwith fel paramedrau swyddogaeth.
Y cymhlethdod amser yw O(n).
23. Darganfyddwch yr elfen oddest mewn arae mewn amser logarithmig
O ystyried arae cyfanrif lle mae gan bob aelod ond un niferoedd eilrif o ddigwyddiadau, y broblem yw penderfynu sawl gwaith mae'r un elfen hon yn ymddangos. Darganfyddwch yr elfen sy'n digwydd od mewn amser logarithmig a gofod cyson os yw'r un elfennau yn digwydd mewn parau yn yr arae ac ni all byth fod mwy na dau achos o elfen benodol mewn rhes.
Mae gweithrediad XOR yn ein galluogi i ddatrys y mater hwn mewn amser llinol. Y nod yw XOR pob elfen yn yr arae. Dim ond ambell elfen sy'n digwydd ar ôl ar ôl i'r elfennau sy'n digwydd eilrif ganslo ei gilydd.
Gellir datrys y broblem hon hyd yn oed mewn amser O(log(n)).
24. Sut i gael yr elfen fwy dilynol ar gyfer pob elfen mewn arae gylchol?
Dylid lleoli'r elfen fwy nesaf ar gyfer pob elfen mewn arae cyfanrif crwn. Y cyfanrif mwy cyntaf ar ôl elfen x yn yr arae yw elfen fwy dilynol yr elfen honno.
O'r dde i'r chwith, efallai y byddwn yn gweithredu ar eitemau arae. Y nod yw dolen ar gyfer pob elfen x nes bod y pentwr yn wag neu fod gennym ni elfen uwch ar ei ben. Gosodwch yr elfen fwy nesaf o x i ymddangos ar ben y pentwr pan fydd yn gwneud hynny.
25. Darganfod cyfrif gwrthdroad arae?
Darganfyddwch gyfanswm nifer gwrthdroadau arae. Cyfeirir at bâr I j) fel gwrthdroad o arae A os I j) ac (A[i] > A[j]). Rhaid inni gyfrif pob pâr o'r rhain yn yr arae.
Mae cyfrif yr holl aelodau arae sy'n llai nag ef ar y dde ac ychwanegu'r canlyniad at yr allbwn yn ddull syml.
Mae gan y datrysiad hwn gymhlethdod O(n2), ac n yw maint y mewnbwn.
26. Beth Yw'r Broblem Trapio Dwr Glaw?
Mae dod o hyd i’r mwyaf o ddŵr y gellir ei ddal mewn set benodol o fariau gyda lled un uned yr un yn cael ei alw’n fater “glawiad trapio”.
Y nod yw pennu'r bar uchaf y gellir ei osod ar ochr chwith a dde pob bar. Lleiafswm y bariau arweiniol i'r chwith a'r dde, llai uchder y bar cyfredol, yw faint o ddŵr sy'n cael ei storio ar ben pob bar.
Casgliad
O'i gymharu â phynciau strwythur data eraill, mae araeau yn symlach. Er mwyn actio cwestiynau cyfweliad, mae angen i chi gael dealltwriaeth sylfaenol o araeau.
Dylech adolygu sylfeini araeau yn helaeth, gan gynnwys gweithrediadau araeau (o ddatgan/creu arae i gyrchu/addasu eitemau arae), yn ogystal â chysyniadau rhaglennu fel dolenni, ailadrodd, a gweithredwyr sylfaenol er mwyn ateb cwestiynau cyfweliad arae yn llwyddiannus. Cydnabod y mater yn llwyr.
Dylech ofyn am eglurhad os oes gennych unrhyw ymholiadau. Meddyliwch am rannu'r mater yn rhannau mwy hylaw. Sicrhewch fod gennych yr algorithm mewn golwg cyn i chi ddechrau rhaglennu; ei ysgrifennu i lawr neu ei ddelweddu mewn siart llif. yna dechreuwch ysgrifennu cod.
Gadael ymateb