INHOUDSOPGAWE[Versteek][Wys]
- 1. Hoe definieer jy 'n Skikking?
- 2. Dinamiese skikkings: wat is dit? Wat onderskei hulle van Basic Arrays?
- 3. Hoe verskil 'n skikking en 'n woordeboek van mekaar?
- 4. Lys sommige van die voordele en nadele van skikkings.
- 5. Waarna verwys “Sparse Array”?
- 6. Wanneer sal jy 'n gekoppelde lys bo 'n skikking kies?
- 7. Wat onderskei 'n geïndekseerde skikking van 'n assosiatiewe skikking?
- 8. Watter voordele het Heap bo gesorteerde skikkings?
- 9. Kan ons die grootte van die skikking as negatief definieer?
- 10. Hoe vind jy die ontbrekende heelgetal in 'n 1 tot 100-element skikking?
- 11. Hoe vind jy die indeks van 'n element in 'n skikking?
- 12. Hoe kan jy ontslae raak van 'n spesifieke element uit 'n skikking?
- 13. Hoe kan twee skikkings se gelykheid geverifieer word?
- 14. Wanneer ons skikkings bespreek, wat bedoel jy met die frases "Dimensie" en "Subscript"?
- Koderonderhoudvrae
- 15. Soek 'n paar in 'n skikking wat die gespesifiseerde som het
- 16. Binêre skikking sortering met lineêre tyd
- 17. Vind die grootste twee-int produk in 'n skikking.
- 18. Hoe om al die skikking se nulle na die einde te skuif
- 19. Hoe om 'n skikking te sorteer met twee inskrywings wat in een bewerking omgeskakel word.
- 20. Hoe om twee gesorteerde skikkings in plek te kombineer.
- 21. Hoe om 'n verskeidenheid items in afwisselende hoë en lae posisies te herrangskik?
- 22. Hoe om elke element van 'n skikking te vervang sonder om 'n afdelingsoperateur te gebruik met die produk van elke element in die skikking?
- 23. Vind die vreemdste element in 'n skikking in logaritmiese tyd
- 24. Hoe om die daaropvolgende groter element vir elke element in 'n sirkelvormige skikking te kry?
- 25. Vind 'n skikking se inversietelling?
- 26. Wat is die probleem om reënwater vas te vang?
- Gevolgtrekking
Koderonderhoude bevat 'n reeks DSA-vrae. Jy moet vaardig wees met skikkings as jy gereed maak vir jou komende tegnologie-onderhoud met FAANG of 'n ander vlak-1-tegnologie-onderneming.
In die meeste koderingsonderhoude kom dit in die tweede plek na Strings. 'n Skikking is 'n groepering van verwante data-elemente wat in die geheue naby mekaar gehou word.
Aangesien hulle aan alle programmeertale gekoppel is, soos C, C++, Java, Python, Perl en Ruby, is hulle oral. Lees verder vir 'n paar oefenkoderingsuitdagings en onderhoudvrae en antwoorde gebaseer op skikkings.
Python sal in hierdie pos gebruik word om die koderingskwessies aan te pak, want dit is maklik om te gebruik, te begryp en aan die meeste van ons bekend moet wees.
Laat ons begin.
1. Hoe definieer jy 'n Skikking?
- 'n Groep verwante datatipes is 'n skikking.
- Skikkings is altyd vas.
- Dieselfde soort veranderlike word op verskeie plekke deur skikkingsvoorwerpe gestoor.
- Primitiewe tipes en voorwerpverwysings is albei versoenbaar daarmee.
2. Dinamiese skikkings: wat is dit? Wat onderskei hulle van Basic Arrays?
Die outomatiese skaal wat dinamiese skikkings (ook na verwys as groeibare skikkings, verstelbare skikkings, veranderbare skikkings of ArrayLists in Java) bied, is 'n beduidende voordeel.
Jy moet altyd vooraf weet hoeveel elemente jou skikking sal stoor, aangesien skikkings 'n vaste grootte het. 'n Dinamiese skikking, aan die ander kant, groei soos jy bykomende lede daarby voeg, so jy hoef nie vooraf die presiese grootte daarvan te weet nie.
3. Hoe verskil 'n skikking en 'n woordeboek van mekaar?
Dit is 'n basiese reeks onderhoudsvrae wat gereeld gevra word. Die volgende is die belangrikste onderskeidings tussen skikkings en woordeboeke:
- 'n Skikking is 'n geordende lys van soortgelyke items. Woordeboek, aan die ander kant, het sleutel-waarde-pare.
- Skikkingsgroottes kan dinamies verander. Sulke dinamiese idees bestaan nie in woordeboeke nie.
- Voordat 'n skikking gebruik word, moet die grootte daarvan gespesifiseer word. Woordeboekgroottes hoef nie aangepas te word nie.
- Gebruik die Redim-stelling as jy die skikking se grootte wil uitbrei. In woordeboeke kan 'n element bygevoeg word sonder 'n verklaring.
4. Lys sommige van die voordele en nadele van skikkings.
Voordele:
- Skikkings kan 'n aantal elemente gelyktydig sorteer.
- ander datastrukture, soos stapels, rye, gekoppelde lyste, bome, grafieke, ens., kan in 'n skikking geïmplementeer word.
- 'n Indeks kan gebruik word om 'n element van 'n skikking te bereik.
Nadele:
- 'n Skikking se grootte moet vooraf verklaar word. Op die oomblik van skikkingverklaring is ons dalk nie bewus van die grootte wat ons benodig nie.
- Die struktuur van die skikking is staties. Dit impliseer dat skikkingsgrootte altyd vas is en dat geheuetoewysing nie verhoog of verminder kan word nie.
5. Waarna verwys “Sparse Array”?
'n Skaars skikking is 'n dataskikking wat baie inskrywings met nulwaardes het. Daarteenoor bevat 'n digte skikking die meerderheid van sy items met nie-nul waardes. Die indekse van 'n yl skikking, wat getalle na voorwerpe omskakel, kan gapings insluit. In vergelyking met 'n HashMap, is hulle meer geheue-doeltreffend.
6. Wanneer sal jy 'n gekoppelde lys bo 'n skikking kies?
Wanneer jy gekoppelde lyste in plaas van skikkings gebruik, oorweeg:
- Jy het geen elemente nodig om ewekansige toegang te hê nie.
- Waar tydelike voorspelbaarheid noodsaaklik is, benodig jy konstante-tyd-invoegings en verwyderings van die lys.
- Om 'n prioriteitswaglys te skep, moet jy dalk items in die middel van die lys plaas.
- Jy het geen idee hoe lank die lys sal wees nie. As die skikkingsgrootte toeneem, moet jy geheue weer verklaar en dupliseer, net soos met eenvoudige skikkings.
7. Wat onderskei 'n geïndekseerde skikking van 'n assosiatiewe skikking?
Die primêre onderskeid tussen assosiatiewe en geïndekseer skikkings word in die volgende tabel gelys.
- 'n Sleutel-waarde-paar in teks- of numeriese formaat word gebruik om 'n assosiatiewe skikking te sorteer. Die geïndekseerde skikking se sleutels is almal numeries, en elke sleutel is gekoppel aan 'n duidelike waarde.
- In 'n assosiatiewe skikking kan die sleutel 'n string wees. Geïndekseerde skikking met heelgetalsleutels wat by 0 begin.
- 'n Tweekolomtabel boots die gedrag van 'n assosiatiewe skikking na. Soortgelyk aan 'n enkelkolomtabel is geïndekseerde skikkings.
- Kaarte is 'n assosiatiewe skikking tipe. 'n Indeksskikking is nie 'n kaart nie.
8. Watter voordele het Heap bo gesorteerde skikkings?
Die tyddoeltreffendheid van die gebruik van Heap over Sorted Arrays is die belangrikste voordeel. Alhoewel hoopbewerkings vinniger is, verg die sortering van 'n skikking baie tyd. 'n Hoop kan die kleinste element aansienlik vinniger ontdek as wat 'n skikking gesorteer kan word.
'n Gegewe versameling getalle kan op een van twee maniere gerangskik word deur gebruik te maak van Sorted Arrays. Aan die ander kant, vir 'n gegewe versameling getalle, kan daar meer as een potensiële hoop wees.
9. Kan ons die grootte van die skikking as negatief definieer?
Nee, ons kan nie 'n negatiewe heelgetal definieer om die grootte van 'n skikking te wees nie. Daar sal nie 'n samestelling-tyd fout wees as ons verklaar nie. Tydens looptyd sal ons egter 'n NegativeArraySizeException teëkom.
10. Hoe vind jy die ontbrekende heelgetal in 'n 1 tot 100-element skikking?
Die totaal van die reeks kan bereken word deur die volgende funksie toe te pas: n (n + 1) / 2
Slegs as die skikking geen duplikate het nie of meer as een heelgetal ontbreek, sal hierdie funksie werk. Of 'n skikking duplikaatelemente het, jy kan die skikking sorteer om te sien of daar enige elemente is wat ekwivalent is.
11. Hoe vind jy die indeks van 'n element in 'n skikking?
'n Element se indeks kan deur 'n lineêre of binêre soektog ontdek word. Totdat dit die passing van die vereiste element opspoor, loop 'n lineêre soekfunksie oor elke element in 'n skikking. Dit gee die indeks terug sodra dit die ooreenstemmende element opgespoor het. Gevolglik is die lineêre soektog se temporele kompleksiteit O. (n). Beide 'n gesorteerde en 'n ongesorteerde skikking kan lineêre soektog gebruik.
Deur 'n binêre soektog te gebruik, wat die skikking voortdurend in die helfte verdeel totdat die mediaan van die interval ooreenstem met die vereiste element en die indeks verskaf, kan jy die element se indeks kry as die skikking gesorteer is. Gevolglik is die binêre soektog se tydelike kompleksiteit O. (log n).
12. Hoe kan jy ontslae raak van 'n spesifieke element uit 'n skikking?
Aangesien jy nie eenvoudig elemente uit die oorspronklike skikking kan verwyder nie, aangesien dit vaste stelle met 'n gedefinieerde grootte is, soek die onderhoudvoerder dat jy 'n ander benadering voorstel en die probleem wat die vraag veroorsaak, hanteer. Die beste manier van aksie is om 'n nuwe skikking te maak om 'n element uit te vee. Jy kan die elemente van die eerste skikking in hierdie skikking dupliseer en slegs die element insluit wat jy wil uitvee.
Nog 'n strategie behels om die teikenelement in die skikking te vind en dan die volgorde van al die items wat regs van die teikenelement is om te keer.
13. Hoe kan twee skikkings se gelykheid geverifieer word?
U moet eers die lengtes van die twee verskafde skikkings verifieer. Die bypassende items van beide skikkings word vergelyk wanneer hul lengtes gelyk is. Die twee skikkings sal as gelyk beskou word. as elke paar komponente in elke korrespondensie gelyk is. Hierdie benadering word nie aangeraai om die gelykheid van twee skikkings na te gaan as die skikkings groot is nie, aangesien dit baie tyd sal neem. Jy kan ook die equals()-metode gebruik wat in die Arrays-klas ingesluit is, maar as die onderhoudvoerder jou vra om twee skikkings te vergelyk sonder om ingeboude metodes te gebruik, sal hierdie manier nuttig wees.
14. Wanneer ons skikkings bespreek, wat bedoel jy met die frases "Dimensie" en "Subscript"?
Die "Dimensie" van 'n skikking is die aantal indekse, of subskripsies, wat nodig is om elke individuele lid te identifiseer. Onderskrifte en afmetings kan dalk onduidelik wees. 'n Dimensie is 'n beskrywing van die reeks toegelate sleutels, terwyl 'n subskripsie 'n getal is. Daar is net een subskripsie nodig vir elke skikkingsdimensie.
Byvoorbeeld, die skikking arr[10][5] het twee dimensies. Groottes 10 op een en 5 op die ander. Om die komponente daarvan aan te spreek, benodig u twee subskripsies. Albei is tussen 0 en 4; een tussen 0 en 9, ingesluit.
Koderonderhoudvrae
15. Soek 'n paar in 'n skikking wat die gespesifiseerde som het
Byvoorbeeld,
insette:
- getalle = [8, 7, 2, 5, 3, 1]
- teiken = 10
Uitgawe:
- Paar gevind (8, 2)
- Or
- Paar gevind (7, 3)
insette:
- getalle = [5, 2, 6, 8, 1, 9]
- teiken = 12
Uitgawe:
- Paar nie gevind nie
16. Binêre skikking sortering met lineêre tyd
Sorteer 'n binêre skikking in lineêre tyd en in 'n vaste area. Die uitvoer behoort eers alle nulle te vertoon, dan almal ene.
Byvoorbeeld,
- Invoer: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Uitset: { 0, 0, 0, 0, 1, 1, 1, 1 }
'n Eenvoudige benadering sal wees om die skikking se totale aantal 0'e, sê k, te bereken en dan die eerste k-indekse in die skikking te vul met 0'e en die oorblywende indekse met 1. As 'n alternatief kan ons bereken hoeveel 1'e totaal in die skikking is. skikking k, vul die laaste k indekse in die skikking met 1, en laat die res van die indekse gevul met 0.
Die gegewe benadering het 'n O(n) tydskompleksiteit en gebruik geen bykomende berging nie, waar n die grootte van die inset is.
17. Vind die grootste twee-int produk in 'n skikking.
Vind die grootste produk van twee getalle in 'n heelgetalskikking.
Dink aan die skikking 10 3 5 6 2 as 'n voorbeeld. Die (-10, -3) of (5, 6) paar is die hoogste produk.
Om oor elke elementkombinasie te dink en hul produk uit te vind is 'n dwase benadering. As die produk van die huidige paar groter is as die maksimum produk wat tot dusver verkry is, dateer die maksimum produk op. Druk die komponente van die finale produk laaste.
Die oplossing hierbo, waar n die hoeveelheid insette is, het 'n tydskompleksiteit van O(n2) en neem nie meer spasie op nie.
18. Hoe om al die skikking se nulle na die einde te skuif
Skuif al die nulle in 'n heelgetalskikking na die einde. Die antwoord moet vermy om konstante spasie te gebruik en die relatiewe volgorde van die skikking se komponente te behou.
Insette: {1,2,3,0,8,0,4,7}
Uitset sal {1,2,3,8,4,7,0,0} wees
Plaas die element op die volgende beskikbare posisie in die skikking as die huidige element nie nul is nie. Vul alle oorblywende indekse met 0 sodra die skikking se items almal verwerk is.
Die voorafgaande oplossing het 'n O(n) tydskompleksiteit, waar n die grootte van die inset is.
19. Hoe om 'n skikking te sorteer met twee inskrywings wat in een bewerking omgeskakel word.
Sorteer 'n skikking in die lineêre tyd gegewe twee omgeruilde items en 'n skikking met al sy elemente in stygende volgorde gerangskik. Maak asof die skikking geen duplikate bevat nie.
Invoer:= [1,9,3,4,7,2] of [9,3,7,2,1,4] of [2,4,1,7,3,9]
Uitset: = [1,2,3,4,7,9]
Begin met die tweede element in die skikking, die doel is om elke element met sy voorganger te vergelyk. Die posisie van die dispuut word gestoor deur twee wysers, x en y, te neem.
Dateer x op na die vorige element se indeks en y na die huidige element se indeks as eersgenoemde groter as laasgenoemde is. Dateer y op na die indeks van die huidige element as dit blyk dat die vorige element groter is as die huidige element.
Laastens, verander die elemente by indekse x en y sodra ons klaar is met die verwerking van elke aangrensende paar elemente.
As gevolg van die feit dat die voorgenoemde metode slegs 'n enkele skandering van die invoerskikking van grootte n uitvoer, is die tydskompleksiteit daarvan O(n). Geen bykomende ruimte is nodig vir die oplossing nie.
20. Hoe om twee gesorteerde skikkings in plek te kombineer.
Voeg die items van skikkings X[] en Y[] saam – twee gesorteerde skikkings van grootte m en n elk – deur die gesorteerde volgorde te behou, dit wil sê deur X[] met die eerste m kleinste elemente te vul en Y[] te vul met die oorblywende elemente.
As 'n element in die skikking X[] reeds op die regte posisie is (dws die een wat die kleinste onder die oorblywende elemente is), ignoreer dit; anders, vervang dit met die kleinste element, wat toevallig ook die eerste lid van Y[] is. Om die gesorteerde volgorde na omruiling te behou, dra die element (nou by Y[0]) oor na sy regte plek in Y[].
Die eerste skikking se grootte is m en die tweede skikking se grootte is n, en die tydskompleksiteit is O(mn).
21. Hoe om 'n verskeidenheid items in afwisselende hoë en lae posisies te herrangskik?
Herrangskik 'n heelgetalskikking sodat elke daaropvolgende lid groter is as die voorafgaande en volgende elemente. Aanvaar dat die skikking geen duplikaatelemente insluit nie.
Om die skikking te sorteer of bykomende spasie te benut is nie nodig vir 'n effektiewe benadering nie. Die plan is, om mee te begin, die tweede lid van die skikking en styg met twee vir elke lus-iterasie.
Ruil die komponente om as die laaste element die eerste een oorskry. In 'n soortgelyke trant, wissel beide items as die volgende element groter is as die huidige element. Ons sal die verlangde skikking kry wat aan die gespesifiseerde beperkings voldoen aan die einde van die lus.
22. Hoe om elke element van 'n skikking te vervang sonder om 'n afdelingsoperateur te gebruik met die produk van elke element in die skikking?
Sonder om die afdelingsoperateur te gebruik, vervang elke element in 'n heelgetalskikking met die produk van alle ander elemente.
In lineêre tyd en konstante ruimte kan ons rekursie gebruik om hierdie probleem aan te spreek. Om die produkte van elke element in die regter subskikking rekursief te bereken en die linker subreeksproduk as funksieparameters deur te gee, is die idee.
Die tydskompleksiteit is O(n).
23. Vind die vreemdste element in 'n skikking in logaritmiese tyd
Gegewe 'n heelgetalskikking waarin almal behalwe een lid ewe getalle voorkoms het, is die probleem om te bepaal hoeveel keer hierdie een element voorkom. Vind die element wat vreemd voorkom in logaritmiese tyd en konstante ruimte as dieselfde elemente in pare in die skikking voorkom en daar nooit meer as twee gevalle van 'n gegewe element in 'n ry kan wees nie.
Die XOR-bewerking stel ons in staat om hierdie probleem in lineêre tyd op te los. Die doel is om elke element in die skikking te XOR. Slegs die elemente wat vreemd voorkom, bly oor nadat die elemente wat ewe voorkom mekaar uitkanselleer.
Hierdie probleem kan selfs in O(log(n)) tyd opgelos word.
24. Hoe om die daaropvolgende groter element vir elke element in 'n sirkelvormige skikking te kry?
Die volgende groter element vir elke element in 'n sirkelvormige heelgetalskikking moet geleë wees. Die eerste groter heelgetal na 'n element x in die skikking is die daaropvolgende groter element van daardie element.
Van regs na links kan ons op 'n verskeidenheid items werk. Die doel is om vir elke element x te lus totdat óf die stapel leeg is óf ons het 'n hoër element bo-op dit. Stel die volgende groter element van x om bo-op die stapel te verskyn wanneer dit gebeur.
25. Vind 'n skikking se inversietelling?
Vind die totale aantal inversies van 'n skikking. Daar word na 'n paar I j) verwys na 'n inversie van 'n skikking A as I j) en (A[i] > A[j]). Ons moet elke paar hiervan in die skikking tel.
Om alle skikkingslede wat minder as dit regs is, te tel en die resultaat by die uitset te voeg, is 'n eenvoudige benadering.
Hierdie oplossing het 'n O(n2) kompleksiteit, waar n die grootte van die inset is.
26. Wat is die probleem om reënwater vas te vang?
Om die meeste water te vind wat in 'n gegewe stel stawe met 'n breedte van een eenheid elk vasgevang kan word, staan bekend as die "vangreënval"-kwessie.
Die doel is om die hoogste staaf te bepaal wat links en regs van elke staaf geplaas kan word. Die minimum van die voorste stawe links en regs, minus die hoogte van die huidige staaf, is die hoeveelheid water wat bo-op elke staaf gestoor word.
Gevolgtrekking
In vergelyking met ander datastruktuuronderwerpe, is skikkings eenvoudiger. Om 'n reeks onderhoudvrae te kan beantwoord, moet jy 'n fundamentele begrip van skikkings hê.
Jy moet die fondamente van skikkings breedvoerig hersien, insluitend skikkingsbewerkings (van die verklaring/skep van 'n skikking tot toegang tot/wysiging van skikkingsitems), sowel as programmeringskonsepte soos lusse, rekursie en basiese operateurs om die reeksonderhoudvrae suksesvol te beantwoord. Herken die probleem heeltemal.
Jy moet verduideliking soek as jy enige navrae het. Dink daaraan om die probleem in meer hanteerbare dele te verdeel. Maak seker dat jy die algoritme in gedagte het voordat jy begin programmering; skryf dit neer of visualiseer dit in 'n vloeidiagram. begin dan kode skryf.
Lewer Kommentaar