Efnisyfirlit[Fela][Sýna]
- 1. Hvernig skilgreinir þú Array?
- 2. Dynamic Arrays: Hvað eru þær? Hvað aðgreinir þá frá Basic Arrays?
- 3. Hvernig eru fylki og orðabók frábrugðin hvert öðru?
- 4. Nefndu nokkra kosti og galla fylkisins.
- 5. Hvað vísar „sparse Array“ til?
- 6. Hvenær myndir þú velja tengdan lista yfir fylki?
- 7. Hvað aðgreinir verðtryggt fylki frá tengdu fylki?
- 8. Hvaða kosti hefur Heap umfram flokkað fylki?
- 9. Getum við skilgreint stærð fylkisins þannig að hún sé neikvæð?
- 10. Hvernig finnur þú heiltöluna sem vantar í fylki 1 til 100 þátta?
- 11. Hvernig finnur þú vísitölu staks í fylki?
- 12. Hvernig er hægt að losa sig við ákveðinn þátt úr fylki?
- 13. Hvernig er hægt að sannreyna jafnræði tveggja fylkinga?
- 14. Þegar við ræðum fylki, hvað áttu við með orðasamböndunum „vídd“ og „áskrift“?
- Kóðunarviðtalsspurningar
- 15. Leitaðu að pari í fylki sem hefur tilgreinda summa
- 16. Tvöfaldur fylki flokkun með línulegum tíma
- 17. Finndu stærstu tveggja innstu vöruna í fylki.
- 18. Hvernig á að færa öll núll fylkisins til enda
- 19. Hvernig á að raða fylki með tveimur færslum sem skipt er um í einni aðgerð.
- 20. Hvernig á að sameina tvö flokkuð fylki á sínum stað.
- 21. Hvernig á að endurraða fjölda hluta á víxl hátt og lágt?
- 22. Hvernig á að skipta út hverju staki fylkis án þess að nota deilingaroperator með margfeldi hvers staks í fylkinu?
- 23. Finndu skrýtnasta þáttinn í fylki í lógaritmískum tíma
- 24. Hvernig á að fá næsta stærra frumefni fyrir hvert frumefni í hringlaga fylki?
- 25. Finndu snúningsfjölda fylkis?
- 26. Hvert er vandamálið við að fanga regnvatn?
- Niðurstaða
Kóðunarviðtöl innihalda röð DSA spurninga. Þú ættir að vera fær um fylki ef þú ert að undirbúa þig fyrir væntanlegt tækniviðtal þitt við FAANG eða annað Tier-1 tæknifyrirtæki.
Í flestum kóðunarviðtölum er það í öðru sæti fyrir Strings. Fylki er hópur tengdra gagnaþátta sem geymdir eru í nálægð hver við annan í minni.
Þar sem þau eru tengd öllum forritunarmálum, eins og C, C++, Java, Python, Perl og Ruby, eru þau alls staðar. Haltu áfram að lesa fyrir nokkrar æfingar við erfðaskráráskoranir og viðtalsspurningar og svör byggð á fylki.
Python verður notað í þessari færslu til að takast á við kóðunarvandamálin vegna þess að það er einfalt í notkun, skilja og verður að vera kunnugt fyrir flest okkar.
Byrjum.
1. Hvernig skilgreinir þú Array?
- Hópur tengdra gagnategunda er fylki.
- Fylki eru alltaf fast.
- Sams konar breyta er geymd á nokkrum stöðum með fylkishlutum.
- Frumstæðar gerðir og tilvísanir hluta eru bæði samhæfðar við það.
2. Dynamic Arrays: Hvað eru þær? Hvað aðgreinir þá frá Basic Arrays?
Sjálfvirka stærðarstærðin sem kvik fylki (einnig nefnt ræktanleg fylki, stærðarbreytanleg fylki, breytanleg fylki eða ArrayLists í Java) veita er verulegur kostur.
Þú verður alltaf að vita hversu marga þætti fylkið þitt mun geyma fyrirfram þar sem fylki hafa fasta stærð. Kraftmikið fylki vex aftur á móti eftir því sem þú bætir fleiri meðlimum við það, svo þú þarft ekki að vita nákvæmlega stærð þess fyrirfram.
3. Hvernig eru fylki og orðabók frábrugðin hvert öðru?
Þetta er grunnatriði sem byggir á fjölda viðtalsspurninga sem reglulega er spurt. Eftirfarandi eru helstu aðgreiningarnar á fylki og orðabókum:
- Fylki er raðaður listi yfir svipaða hluti. Orðabók hefur aftur á móti lykilgildapör.
- Fylkjastærðir geta breyst á kraftmikinn hátt. Slíkar kraftmiklar hugmyndir eru ekki til í orðabókum.
- Áður en fylki er notað verður að tilgreina stærð þess. Orðabókastærðir þarf ekki að aðlaga.
- Notaðu Redim yfirlýsinguna ef þú vilt stækka stærð fylkisins. Í orðabókum er hægt að bæta við staki án yfirlýsingar.
4. Nefndu nokkra kosti og galla fylkisins.
Kostir:
- Fylki geta flokkað fjölda þátta samtímis.
- Annað gagnaskipan, eins og stafla, biðraðir, tengdir listar, tré, línurit, osfrv., er hægt að útfæra í fylki.
- Hægt er að nota vísitölu til að ná til þáttar fylkis.
Ókostir:
- Tilgreina þarf stærð fylkis fyrirfram. Á því augnabliki sem fylkisyfirlýsing er gerð gætum við þó ekki verið meðvituð um stærðina sem við þurfum.
- Uppbygging fylkisins er kyrrstæð. Það felur í sér að fylkisstærð er alltaf föst og að minnisúthlutun er ekki hægt að auka eða minnka.
5. Hvað vísar „sparse Array“ til?
Dreifður fylki er gagnafylki sem hefur mikið af færslum með núllgildum. Aftur á móti inniheldur þétt fylki meirihluta atriða sinna með gildum sem eru ekki núll. Vísitölur dreifðar fylkis, sem breytir tölum í hluti, geta innihaldið eyður. Í samanburði við HashMap eru þau minni-dugleg.
6. Hvenær myndir þú velja tengdan lista yfir fylki?
Þegar þú notar tengda lista í stað fylkja skaltu íhuga:
- Þú þarft enga þætti til að hafa handahófsaðgang.
- Þar sem tímabundinn fyrirsjáanleiki er nauðsynlegur þarftu að setja inn og fjarlægja stöðugt af listanum.
- Til þess að búa til forgangsröð gætir þú þurft að setja hluti í miðju listans.
- Þú hefur ekki hugmynd um hversu langur listinn verður. Ef fylkisstærðin eykst verður þú að lýsa aftur yfir og afrita minni, alveg eins og með einföld fylki.
7. Hvað aðgreinir verðtryggt fylki frá tengdu fylki?
Aðal aðgreiningin á tengdum og verðtryggðum fylkjum er talin upp í eftirfarandi töflu.
- Lykilgildapar á texta- eða töluformi er notað til að flokka tengifylki. Lyklar verðtryggðu fylkisins eru allir tölulegir og hver lykill er tengdur sérstöku gildi.
- Í tengdu fylki gæti lykillinn verið strengur. Verðtryggt fylki með heiltölulyklum sem byrja á 0.
- Tveggja dálka tafla líkir eftir hegðun tengdrar fylkis. Svipað og í töflu með einum dálki eru verðtryggð fylki.
- Kort eru tengd fylkistegund. Vísitala fylki er ekki kort.
8. Hvaða kosti hefur Heap umfram flokkað fylki?
Tímaskilvirkni þess að nota Heap yfir flokkuð fylki er lykilávinningurinn. Þó að hrúguaðgerðir séu hraðari, þá tekur flokkun fylkis mikinn tíma. Hrúga getur uppgötvað minnsta þáttinn mun hraðar en hægt er að flokka fylki.
Hægt er að raða tilteknu safni af tölum á annan af tveimur vegum með því að nota Sorted Arrays. Á hinn bóginn, fyrir tiltekið safn af tölum, geta verið fleiri en ein möguleg hrúga.
9. Getum við skilgreint stærð fylkisins þannig að hún sé neikvæð?
Nei, við getum ekki skilgreint neikvæða heiltölu á stærð við fylki. Það verður ekki samsetningartímavilla ef við lýsum yfir. Á keyrslutíma munum við hins vegar lenda í NegativeArraySizeException.
10. Hvernig finnur þú heiltöluna sem vantar í fylki 1 til 100 þátta?
Hægt er að reikna út heildarfjölda röðarinnar með því að beita eftirfarandi falli: n (n + 1) / 2
Aðeins ef fylkið hefur engar afrit eða það vantar fleiri en eina heiltölu mun þessi aðgerð virka. Hvort fylki hefur afrita þætti, getur þú flokkað fylkið til að sjá hvort það séu einhverjir þættir sem eru jafngildir.
11. Hvernig finnur þú vísitölu staks í fylki?
Hægt er að uppgötva vísitölu frumefnis með línulegri eða tvíundarleit. Þangað til það finnur samsvörun nauðsynlegs þáttar fer línuleg leitaraðgerð yfir hvern og einasta þátt í fylki. Það skilar vísitölunni þegar það hefur fundið samsvarandi þáttinn. Þar af leiðandi er tímaflækjustig línulegrar leitar O. (n). Bæði flokkað og óflokkað fylki getur notað línulega leit.
Með því að nota tvíundarleit, sem skiptir fylkinu stöðugt í tvennt þar til miðgildi bilsins passar við nauðsynlegan þátt og gefur upp vísitöluna, geturðu fengið vísitölu frumefnisins ef fylkið er raðað. Þar af leiðandi er tímaflækjustig tvíundarleitarinnar O. (log n).
12. Hvernig er hægt að losa sig við ákveðinn þátt úr fylki?
Þar sem þú getur ekki einfaldlega eytt þáttum úr upprunalegu fylkinu þar sem þeir eru föst sett með skilgreindri stærð, leitar viðmælandinn eftir því að þú stingur upp á annarri nálgun og takist á við vandamálið sem spurningin vekur. Besta aðgerðin er að búa til nýtt fylki til að eyða einingu. Þú mátt afrita þættina úr fyrsta fylkinu í þessu fylki og hafa aðeins þann þátt sem þú vilt eyða.
Önnur aðferð felur í sér að finna markþáttinn í fylkinu og snúa síðan við röð allra hluta sem eru hægra megin við markþáttinn.
13. Hvernig er hægt að sannreyna jafnræði tveggja fylkinga?
Þú verður fyrst að staðfesta lengd þessara tveggja fylkinga. Samsvarandi hlutir beggja fylkinga eru bornir saman þegar lengd þeirra er jöfn. Litið verður á þessar tvær fylkingar sem jafnar. ef hvert par af íhlutum í hverri samsvörun er jafnt. Þessari nálgun er ekki ráðlagt að athuga jafnræði tveggja fylkinga ef fylkin eru stór í sniðum þar sem það mun taka mikinn tíma. Þú getur líka notað equals() aðferðina sem er innifalin í Arrays bekknum, en ef viðmælandinn biður þig um að bera saman tvær fylki án þess að nota innbyggðar aðferðir mun þessi leið vera gagnleg.
14. Þegar við ræðum fylki, hvað áttu við með orðasamböndunum „vídd“ og „áskrift“?
„Stærð“ fylkis er fjöldi vísitalna, eða áskriftar, sem þarf til að auðkenna hvern einstakan meðlim. Áskriftir og stærðir gætu verið óljósar. Vídd er lýsing á svið leyfilegra lykla, en áskrift er tala. Það þarf aðeins eina áskrift fyrir hverja fylkisvídd.
Til dæmis hefur fylkið arr[10][5] tvær víddir. Stærðir 10 á öðrum og 5 á hinum. Til að takast á við hluti þess þarftu tvær áskriftir. Báðir eru á milli 0 og 4; einn á milli 0 og 9, að meðtöldum.
Kóðunarviðtalsspurningar
15. Leitaðu að pari í fylki sem hefur tilgreinda summa
Til dæmis,
inntak:
- tölur = [8, 7, 2, 5, 3, 1]
- miða = 10
Output:
- Par fannst (8, 2)
- Or
- Par fannst (7, 3)
inntak:
- tölur = [5, 2, 6, 8, 1, 9]
- miða = 12
Output:
- Par fannst ekki
16. Tvöfaldur fylki flokkun með línulegum tíma
Raða tvíundarfylki í línulegum tíma og á föstu svæði. Úttakið ætti að sýna öll núll fyrst, síðan öll.
Til dæmis,
- Inntak: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Úttak: { 0, 0, 0, 0, 1, 1, 1, 1 }
Einföld nálgun væri að reikna út heildarfjölda 0s í fylkinu, segjum k, og fylla síðan fyrstu k vísitölurnar í fylkinu með 0s og þær vísitölur sem eftir eru með 1. Í staðinn gætum við reiknað út hversu margar 1 eru samtals í fylki k, fylltu síðustu k vísitölurnar í fylkinu með 1 og skildu restina af vísitölunum útfyllta með 0.
Gefin nálgun hefur O(n) tímaflækju og notar enga viðbótargeymslu, þar sem n er stærð inntaksins.
17. Finndu stærstu tveggja innstu vöruna í fylki.
Finndu stærstu afurð tveggja talna í heiltölufylki.
Hugsaðu um fylkið 10 3 5 6 2 sem dæmi. (-10, -3) eða (5, 6) parið er hæsta varan.
Að hugsa um hverja frumefnasamsetningu og finna út vöruna þeirra er heimskuleg nálgun. Ef vara núverandi pars er stærri en hámarksafurðin sem fæst hingað til, uppfærðu hámarksvöruna. Prentaðu íhluti lokaafurðarinnar síðast.
Ofangreind lausn, þar sem n er magn inntaksins, hefur tímaflækjustigið O(n2) og tekur ekki meira pláss.
18. Hvernig á að færa öll núll fylkisins til enda
Færðu öll núllin í heiltölufylki til enda. Svarið ætti að forðast að nota stöðugt bil og varðveita hlutfallslega röð íhluta fylkisins.
Inntak: {1,2,3,0,8,0,4,7}
Úttak verður {1,2,3,8,4,7,0,0}
Settu stakið á eftirfarandi tiltæka stöðu í fylkinu ef núverandi þáttur er ekki núll. Fylltu allar vísitölur sem eftir eru með 0 þegar öll atriði fylkisins hafa verið unnin.
Undanfarandi lausn hefur O(n) tímaflækju, þar sem n er stærð inntaksins.
19. Hvernig á að raða fylki með tveimur færslum sem skipt er um í einni aðgerð.
Raða fylki á línulegum tíma með tveimur skiptum hlutum og fylki með öllum þáttum þess raðað í hækkandi röð. Láttu eins og fylkið innihaldi engar afrit.
Inntak:= [1,9,3,4,7,2] eða [9,3,7,2,1,4] eða [2,4,1,7,3,9]
Framleiðsla: = [1,2,3,4,7,9]
Byrjað er á öðrum þættinum í fylkinu, markmiðið er að bera hvern þátt saman við forvera hans. Staða deilunnar er geymd með því að taka tvo ábendingar, x og y.
Uppfærðu x í vísitölu fyrri þáttar og y í vísitölu núverandi þáttar ef sá fyrri er stærri en sá síðari. Uppfærðu y í vísitölu núverandi þáttar ef í ljós kemur að fyrri þátturinn er stærri en núverandi þáttur.
Að lokum skaltu skipta um þætti í vísitölum x og y þegar við höfum lokið við að vinna hvert aðliggjandi par af þáttum.
Vegna þess að fyrrnefnd aðferð framkvæmir aðeins eina skönnun á inntaksfylki af stærð n, er tímaflækjustig hennar O(n). Ekkert aukarými er nauðsynlegt fyrir lausnina.
20. Hvernig á að sameina tvö flokkuð fylki á sínum stað.
Sameina hluti fylkianna X[] og Y[]—tvær flokkaðar fylki af stærð m og n hvor—með því að halda röðinni, það er að segja með því að fylla X[] með fyrstu m minnstu stökunum og fylla Y[] með þættir sem eftir eru.
Ef þáttur í fylkinu X[] er þegar á réttri stöðu (þ.e. sá sem er minnstur af þeim þáttum sem eftir eru), hunsaðu það; annars skaltu skipta því út fyrir minnstu þáttinn, sem er líka fyrsti þátturinn í Y[]. Til að halda röðinni eftir að skipt hefur verið um, flytjið þáttinn (nú á Y[0]) á réttan stað í Y[].
Stærð fyrri fylkisins er m og seinni fylkisins er n, og tímaflækjustigið er O(mn).
21. Hvernig á að endurraða fjölda hluta á víxl hátt og lágt?
Endurraðaðu heiltölufylki þannig að hver síðari meðlimur sé stærri en fyrri og eftirfarandi þættir. Gerum ráð fyrir að fylkið innihaldi enga afrita þætti.
Það er ekki nauðsynlegt að flokka fylkið eða nýta viðbótarrými fyrir árangursríka nálgun. Planið er til að byrja með annar meðlimur fylkisins og hækka um tvo fyrir hverja lykkjuendurtekningu.
Skiptu um íhluti ef síðasta þátturinn fer yfir þann fyrsta. Á svipaðan hátt skaltu skipta um bæði atriði ef eftirfarandi þáttur er stærri en núverandi þáttur. Við munum fá viðkomandi fylki sem er í samræmi við tilgreindar takmarkanir við lok lykkjunnar.
22. Hvernig á að skipta út hverju staki fylkis án þess að nota deilingaroperator með margfeldi hvers staks í fylkinu?
Án þess að nota skiptingaraðgerðina, skiptu hverri einingu í heiltölufylki út fyrir margfeldi allra annarra þátta.
Í línulegum tíma og stöðugu rúmi getum við notað endurkomu til að takast á við þetta vandamál. Það er hugmyndin að reikna afurðir hvers þáttar í hægri undirfylki aftur og aftur og senda vinstri undirfylkisafurðina sem fallfæribreytur.
Tímaflækjustigið er O(n).
23. Finndu skrýtnasta þáttinn í fylki í lógaritmískum tíma
Miðað við heiltalna fylki þar sem allir nema einn meðlimur hafa jafnan fjölda tilvika, er vandamálið að ákvarða hversu oft þessi eini þáttur birtist. Finndu staka stakið sem kemur fyrir í lógaritmískum tíma og föstu rúmi ef sömu þættir koma fyrir í pörum í fylkinu og það geta aldrei verið fleiri en tvö tilvik af tilteknu staki í röð.
XOR aðgerðin gerir okkur kleift að leysa þetta mál á línulegum tíma. Markmiðið er að XOR hvert atriði í fylkinu. Aðeins stakir stakir sem koma fyrir eru eftir eftir að þættir sem koma fyrir sléttu hætta hver öðrum.
Þetta vandamál er jafnvel hægt að leysa á O(log(n)) tíma.
24. Hvernig á að fá næsta stærra frumefni fyrir hvert frumefni í hringlaga fylki?
Næsta stærri þáttur fyrir hvern þátt í hringlaga heiltölufylki ætti að vera staðsettur. Fyrsta stærri heiltalan á eftir staki x í fylkinu er síðari stærri þáttur þess staks.
Frá hægri til vinstri gætum við starfað á fylkishlutum. Markmiðið er að lykkja fyrir hvert stak x þar til annaðhvort staflan er tóm eða við höfum hærra stak ofan á honum. Stilltu næsta stærra stak af x til að birtast ofan á staflanum þegar það gerist.
25. Finndu snúningsfjölda fylkis?
Finndu heildarfjölda snúninga fylkis. Par I j) er vísað til að vera snúning á fylki A ef I j) og (A[i] > A[j]). Við verðum að telja hvert par af þessu í fylkinu.
Að telja alla fylkismeðlimi sem eru færri en það til hægri og bæta niðurstöðunni við úttakið er einföld nálgun.
Þessi lausn hefur O(n2) flókið, þar sem n er stærð inntaksins.
26. Hvert er vandamálið við að fanga regnvatn?
Að finna mesta vatnið sem hægt er að fanga í tilteknu setti af börum með breidd einni einingu hver er þekkt sem vandamálið um að „fanga úrkomu“.
Markmiðið er að ákvarða hæstu stikuna sem má setja til vinstri og hægri við hverja stiku. Lágmark fremstu stanganna til vinstri og hægri, að frádregnum hæð núverandi stangar, er vatnsmagnið sem er geymt ofan á hverri stöng.
Niðurstaða
Í samanburði við önnur gagnauppbyggingarefni eru fylki einfaldari. Til þess að geta svarað spurningum um fylkisviðtal þarftu að hafa grundvallarskilning á fylki.
Þú ættir að fara ítarlega yfir undirstöðu fylkja, þar með talið fylkisaðgerðir (frá því að lýsa yfir/búa til fylki til að fá aðgang að/breyta fylkishlutum), sem og forritunarhugtök eins og lykkjur, endurtekningu og grunnaðgerðir til að geta svarað spurningum um fylkisviðtal. Kannast alveg við málið.
Þú ættir að leita skýringa ef þú hefur einhverjar spurningar. Hugsaðu um að skipta málinu í viðráðanlegri hluta. Gakktu úr skugga um að þú hafir reikniritið í huga áður en þú byrjar að forrita; skrifaðu það niður eða sýndu það í flæðiriti. byrjaðu síðan að skrifa kóða.
Skildu eftir skilaboð