Inhoudsopgave[Zich verstoppen][Laten zien]
- 1. Hoe definieer je een array?
- 2. Dynamische arrays: wat zijn ze? Wat onderscheidt ze van Basic Arrays?
- 3. Hoe verschillen een array en een woordenboek van elkaar?
- 4. Noem enkele voor- en nadelen van arrays.
- 5. Waar verwijst “Sparse Array” naar?
- 6. Wanneer zou u een gekoppelde lijst verkiezen boven een array?
- 7. Wat onderscheidt een geïndexeerde array van een associatieve array?
- 8. Welke voordelen heeft Heap ten opzichte van gesorteerde arrays?
- 9. Kunnen we de grootte van de array als negatief definiëren?
- 10. Hoe vind je het ontbrekende gehele getal in een array van 1 tot 100 elementen?
- 11. Hoe vind je de index van een element in een array?
- 12. Hoe kun je een specifiek element uit een array verwijderen?
- 13. Hoe kan de gelijkheid van twee arrays worden geverifieerd?
- 14. Als we het hebben over arrays, wat bedoelt u dan met de uitdrukkingen "Dimensie" en "Subscript"?
- Sollicitatievragen coderen
- 15. Zoek een paar in een array met de gespecificeerde som
- 16. Binaire array-sortering met lineaire tijd
- 17. Zoek het grootste two-int-product in een array.
- 18. Hoe alle nullen van de array naar het einde te verschuiven?
- 19. Hoe een array te sorteren met twee items die in één bewerking worden verwisseld.
- 20. Hoe twee gesorteerde arrays op hun plaats te combineren.
- 21. Hoe een reeks items opnieuw ordenen in afwisselend hoge en lage posities?
- 22. Hoe vervang je elk element van een array zonder een delingsoperator te gebruiken met het product van elk element in de array?
- 23. Vind het vreemdste element in een array in logaritmische tijd
- 24. Hoe krijg je het volgende grotere element voor elk element in een cirkelvormige array?
- 25. Vind het aantal inversies van een array?
- 26. Wat is het probleem met het opvangen van regenwater?
- Conclusie
Coderingsinterviews bevatten een reeks DSA-vragen. Je moet vaardig zijn met arrays als je je voorbereidt op je aanstaande technische interview met FAANG of een ander Tier-1 tech-bedrijf.
In de meeste coderingsinterviews komt het op de tweede plaats na Strings. Een array is een groep gerelateerde gegevenselementen die in het geheugen dicht bij elkaar worden bewaard.
Omdat ze verbonden zijn met alle programmeertalen, zoals C, C++, Java, Python, Perl en Ruby, zijn ze overal. Lees verder voor enkele oefencode-uitdagingen en interviewvragen en antwoorden op basis van arrays.
Python zal in dit bericht worden gebruikt om de coderingsproblemen aan te pakken, omdat het eenvoudig te gebruiken en te begrijpen is en voor de meesten van ons bekend moet zijn.
Laten we beginnen.
1. Hoe definieer je een array?
- Een groep gerelateerde gegevenstypen is een array.
- Arrays zijn altijd vast.
- Dezelfde soort variabele wordt op verschillende plaatsen opgeslagen door array-objecten.
- Primitieve typen en objectreferenties zijn er beide compatibel mee.
2. Dynamische arrays: wat zijn ze? Wat onderscheidt ze van Basic Arrays?
De automatische schaling die dynamische arrays (ook wel aangroeibare arrays, resizable arrays, veranderbare arrays of ArrayLists in Java genoemd) bieden, is een belangrijk voordeel.
U moet altijd van tevoren weten hoeveel elementen uw array zal opslaan, aangezien arrays een vaste grootte hebben. Een dynamische array groeit daarentegen naarmate u er extra leden aan toevoegt, dus u hoeft de exacte grootte niet van tevoren te weten.
3. Hoe verschillen een array en een woordenboek van elkaar?
Dit is een op fundamenten gebaseerde reeks interviewvragen die regelmatig worden gesteld. Hieronder volgen de belangrijkste verschillen tussen arrays en woordenboeken:
- Een array is een geordende lijst van vergelijkbare items. Dictionary heeft daarentegen sleutel-waardeparen.
- Matrixgroottes kunnen dynamisch veranderen. Dergelijke dynamische ideeën komen niet voor in woordenboeken.
- Voordat u een array gebruikt, moet de grootte worden opgegeven. Woordenboekformaten hoeven niet te worden aangepast.
- Gebruik de Redim-instructie als u de grootte van de array wilt uitbreiden. In woordenboeken kan een element worden toegevoegd zonder declaratie.
4. Noem enkele voor- en nadelen van arrays.
voordelen:
- Arrays kunnen een aantal elementen tegelijk sorteren.
- Overige data structuren, zoals stapels, wachtrijen, gekoppelde lijsten, bomen, grafieken, enz., Kunnen in een array worden geïmplementeerd.
- Een index kan worden gebruikt om een element van een array te bereiken.
nadelen:
- De grootte van een array moet vooraf worden aangegeven. Op het moment van de array-declaratie zijn we ons echter misschien niet bewust van de grootte die we nodig hebben.
- De structuur van de array is statisch. Dit houdt in dat de grootte van de array altijd vast is en dat de geheugentoewijzing niet kan worden verhoogd of verlaagd.
5. Waar verwijst “Sparse Array” naar?
Een sparse array is een gegevensarray met veel items met nulwaarden. Daarentegen bevat een dichte array de meeste items met niet-nulwaarden. De indices van een schaarse array, die getallen naar objecten converteert, kunnen hiaten bevatten. In vergelijking met een HashMap zijn ze geheugenefficiënter.
6. Wanneer zou u een gekoppelde lijst verkiezen boven een array?
Overweeg bij het gebruik van gekoppelde lijsten in plaats van arrays:
- U hebt geen elementen nodig om willekeurige toegang te hebben.
- Waar temporele voorspelbaarheid essentieel is, moet u constante toevoegingen en verwijderingen uit de lijst hebben.
- Als u een prioriteitswachtrij wilt maken, moet u mogelijk items in het midden van de lijst plaatsen.
- Je hebt geen idee hoe lang de lijst zal zijn. Als de arraygrootte toeneemt, moet u het geheugen opnieuw declareren en dupliceren, net als bij eenvoudige arrays.
7. Wat onderscheidt een geïndexeerde array van een associatieve array?
De belangrijkste verschillen tussen associatieve en geïndexeerde arrays worden weergegeven in de volgende tabel.
- Een sleutel/waarde-paar in tekst- of numeriek formaat wordt gebruikt om een associatieve array te sorteren. De sleutels van de geïndexeerde array zijn allemaal numeriek en elke sleutel is verbonden met een afzonderlijke waarde.
- In een associatieve array kan de sleutel een string zijn. Geïndexeerde array met integer-sleutels beginnend bij 0.
- Een tabel met twee kolommen bootst het gedrag van een associatieve array na. Net als bij een tabel met één kolom zijn geïndexeerde arrays.
- Kaarten zijn een associatief arraytype. Een indexarray is geen kaart.
8. Welke voordelen heeft Heap ten opzichte van gesorteerde arrays?
De tijdsefficiëntie van het gebruik van Heap over Sorted Arrays is het belangrijkste voordeel. Hoewel heapbewerkingen sneller zijn, kost het sorteren van een array veel tijd. Een heap kan het kleinste element aanzienlijk sneller ontdekken dan een array kan worden gesorteerd.
Een bepaalde verzameling getallen kan op twee manieren worden gerangschikt met behulp van Sorted Arrays. Aan de andere kant kan er voor een bepaalde verzameling getallen meer dan één potentiële hoop zijn.
9. Kunnen we de grootte van de array als negatief definiëren?
Nee, we kunnen een negatief geheel getal niet definiëren als de grootte van een array. Er zal geen compile-time fout zijn als we declareren. Tijdens runtime zullen we echter een NegativeArraySizeException tegenkomen.
10. Hoe vind je het ontbrekende gehele getal in een array van 1 tot 100 elementen?
Het totaal van de reeks kan worden berekend door de volgende functie toe te passen: n (n + 1) / 2
Alleen als de array geen duplicaten heeft of meer dan één geheel getal mist, zal deze functie werken. Of een array dubbele elementen heeft, u kunt de array sorteren om te zien of er elementen zijn die equivalent zijn.
11. Hoe vind je de index van een element in een array?
De index van een element kan worden ontdekt via een lineaire of binaire zoekopdracht. Totdat het de overeenkomst van het vereiste element lokaliseert, loopt een lineaire zoekfunctie over elk element in een array. Het retourneert de index zodra het het overeenkomende element heeft gevonden. Bijgevolg is de temporele complexiteit van de lineaire zoekactie O. (n). Zowel een gesorteerde als een ongesorteerde array kan lineair zoeken.
Met behulp van een binaire zoekactie, die de array voortdurend in tweeën deelt totdat de mediaan van het interval overeenkomt met het vereiste element en de index levert, kunt u de index van het element krijgen als de array is gesorteerd. Bijgevolg is de temporele complexiteit van de binaire zoekactie O. (log n).
12. Hoe kun je een specifiek element uit een array verwijderen?
Aangezien je niet zomaar elementen uit de originele array kunt verwijderen, aangezien het vaste sets met een gedefinieerde grootte zijn, wil de interviewer dat je een andere benadering voorstelt en het probleem dat de vraag oproept aanpakt. De beste manier van handelen is om een nieuwe array te maken om een element te verwijderen. U mag de elementen van de eerste array in deze array dupliceren en alleen het element opnemen dat u wilt verwijderen.
Een andere strategie omvat het vinden van het doelelement in de array en het omkeren van de volgorde van alle items die zich rechts van het doelelement bevinden.
13. Hoe kan de gelijkheid van twee arrays worden geverifieerd?
U moet eerst de lengtes van de twee geleverde arrays controleren. De overeenkomende items van beide arrays worden vergeleken wanneer hun lengte gelijk is. De twee arrays worden als gelijk beschouwd. als elk paar componenten in elke correspondentie gelijk is. Deze benadering wordt niet aangeraden om de gelijkheid van twee arrays te controleren als de arrays groot zijn, aangezien dit veel tijd kost. U kunt ook de methode equals() gebruiken die is opgenomen in de klasse Arrays, maar als de interviewer u vraagt om twee arrays te vergelijken zonder ingebouwde methoden te gebruiken, is deze manier nuttig.
14. Als we het hebben over arrays, wat bedoelt u dan met de uitdrukkingen "Dimensie" en "Subscript"?
De "Dimensie" van een array is het aantal indices of subscripts dat nodig is om elk afzonderlijk lid te identificeren. Abonnementen en afmetingen zijn mogelijk onduidelijk. Een dimensie is een beschrijving van het bereik van toegestane sleutels, terwijl een subscript een getal is. Er is slechts één subscript vereist voor elke matrixdimensie.
De array arr[10][5] heeft bijvoorbeeld twee dimensies. Maat 10 aan de ene en 5 aan de andere. Om de componenten aan te pakken, hebt u twee subscripts nodig. Beide liggen tussen 0 en 4; één tussen 0 en 9, inclusief.
Sollicitatievragen coderen
15. Zoek een paar in een array met de gespecificeerde som
Bijvoorbeeld
Input:
- aantal = [8, 7, 2, 5, 3, 1]
- doel = 10
Output:
- Paar gevonden (8, 2)
- Or
- Paar gevonden (7, 3)
Input:
- aantal = [5, 2, 6, 8, 1, 9]
- doel = 12
Output:
- Paar niet gevonden
16. Binaire array-sortering met lineaire tijd
Sorteer een binaire array in lineaire tijd en in een vast gebied. De uitvoer zou eerst alle nullen moeten weergeven, dan alle enen.
Bijvoorbeeld
- Invoer: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Uitgang: { 0, 0, 0, 0, 1, 1, 1, 1 }
Een eenvoudige benadering zou zijn om het totale aantal nullen van de array te berekenen, zeg k, en dan de eerste k-indexen in de array te vullen met nullen en de resterende indices met 0. Als alternatief kunnen we berekenen hoeveel enen in totaal zijn in de array k, vul de laatste k-indexen in de array met 0, en laat de rest van de indices gevuld met 1.
De gegeven benadering heeft een O(n)-tijdcomplexiteit en gebruikt geen extra opslag, waarbij n de grootte van de invoer is.
17. Zoek het grootste two-int-product in een array.
Vind het grootste product van twee getallen in een integerarray.
Denk aan de array 10 3 5 6 2 als voorbeeld. Het (-10, -3) of (5, 6) paar is het hoogste product.
Nadenken over elke combinatie van elementen en erachter komen wat hun product is, is een dwaze benadering. Als het product van het huidige paar groter is dan het maximale product dat tot nu toe is verkregen, update dan het maximale product. Druk de componenten van het eindproduct als laatste af.
De bovenstaande oplossing, waarbij n de hoeveelheid invoer is, heeft een tijdcomplexiteit van O(n2) en neemt niet meer ruimte in beslag.
18. Hoe alle nullen van de array naar het einde te verschuiven?
Verplaats alle nullen in een integerarray naar het einde. Het antwoord zou het gebruik van constante ruimte moeten vermijden en de relatieve volgorde van de componenten van de array moeten behouden.
Invoer: {1,2,3,0,8,0,4,7}
Uitvoer zal {1,2,3,8,4,7,0,0} zijn
Plaats het element op de volgende beschikbare positie in de array als het huidige element niet nul is. Vul alle resterende indices met 0 zodra de items van de array allemaal zijn verwerkt.
De voorgaande oplossing heeft een O(n) tijdcomplexiteit, waarbij n de grootte van de invoer is.
19. Hoe een array te sorteren met twee items die in één bewerking worden verwisseld.
Sorteer een array in de lineaire tijd gegeven twee verwisselde items en een array met alle elementen in oplopende volgorde gerangschikt. Doe alsof de array geen duplicaten bevat.
Invoer:= [1,9,3,4,7,2] of [9,3,7,2,1,4] of [2,4,1,7,3,9]
Uitgang: = [1,2,3,4,7,9]
Beginnend met het tweede element in de array, is het doel om elk element te vergelijken met zijn voorganger. De positie van het geschil wordt opgeslagen door twee wijzers, x en y, te nemen.
Werk x bij naar de index van het vorige element en y naar de index van het huidige element als de eerste groter is dan de laatste. Werk y bij naar de index van het huidige element als blijkt dat het vorige element groter is dan het huidige element.
Schakel ten slotte de elementen op de indexen x en y om zodra we klaar zijn met het verwerken van elk aangrenzend paar elementen.
Vanwege het feit dat de bovengenoemde methode slechts een enkele scan van de invoerarray met grootte n uitvoert, is de tijdcomplexiteit O(n). Er is geen extra ruimte nodig voor de oplossing.
20. Hoe twee gesorteerde arrays op hun plaats te combineren.
Voeg de items van arrays X[] en Y[] samen - twee gesorteerde arrays van elk de grootte m en n - door de gesorteerde volgorde te behouden, dat wil zeggen door X[] te vullen met de eerste m kleinste elementen en Y[] te vullen met de resterende elementen.
Als een element in de array X[] al op de juiste positie staat (dwz degene die het kleinste is van de resterende elementen), negeer het dan; vervang het anders door het kleinste element, dat ook het eerste lid van Y[] is. Om de gesorteerde volgorde na het verwisselen te behouden, verplaatst u het element (nu op Y[0]) naar de juiste locatie in Y[].
De grootte van de eerste array is m en de grootte van de tweede array is n, en de tijdcomplexiteit is O(mn).
21. Hoe een reeks items opnieuw ordenen in afwisselend hoge en lage posities?
Herschik een integerarray zodat elk volgend lid groter is dan de voorgaande en volgende elementen. Neem aan dat de array geen dubbele elementen bevat.
Het sorteren van de array of het benutten van extra ruimte is niet nodig voor een effectieve aanpak. Het plan is om te beginnen het tweede lid van de array en gaat met twee omhoog voor elke lusiteratie.
Verwissel de componenten als het laatste element het eerste overschrijdt. Schakel op dezelfde manier beide items om als het volgende element groter is dan het huidige element. We zullen de gewenste array verkrijgen die voldoet aan de gespecificeerde beperkingen aan het einde van de lus.
22. Hoe vervang je elk element van een array zonder een delingsoperator te gebruiken met het product van elk element in de array?
Vervang elk element in een integerarray door het product van alle andere elementen zonder de delingsoperator te gebruiken.
In lineaire tijd en constante ruimte kunnen we recursie gebruiken om dit probleem aan te pakken. Recursief de producten van elk element in de rechter subarray berekenen en het linker subarray-product doorgeven als functieparameters is het idee.
De tijdcomplexiteit is O(n).
23. Vind het vreemdste element in een array in logaritmische tijd
Gegeven een integer-array waarin op één na alle leden een even aantal keren voorkomen, is het probleem om te bepalen hoe vaak dit ene element voorkomt. Zoek het oneven voorkomende element in logaritmische tijd en constante ruimte als dezelfde elementen in paren in de array voorkomen en er nooit meer dan twee instanties van een bepaald element op een rij kunnen zijn.
De XOR-bewerking stelt ons in staat om dit probleem in lineaire tijd op te lossen. Het doel is om elk element in de array te XOR. Alleen de oneven voorkomende elementen blijven over nadat de even voorkomende elementen elkaar opheffen.
Dit probleem kan zelfs in O(log(n))-tijd worden opgelost.
24. Hoe krijg je het volgende grotere element voor elk element in een cirkelvormige array?
Het volgende grotere element voor elk element in een cirkelvormige integer-array moet worden gelokaliseerd. Het eerste grotere gehele getal na een element x in de array is het daaropvolgende grotere element van dat element.
Van rechts naar links kunnen we werken met array-items. Het doel is om voor elk element x een lus te maken totdat de stapel leeg is of we er een hoger element bovenop hebben. Stel het volgende grotere element van x in om bovenop de stapel te verschijnen wanneer dit het geval is.
25. Vind het aantal inversies van een array?
Zoek het totale aantal inversies van een array. Een paar I j) wordt een inversie van een array A genoemd als I j) en (A[i] > A[j]). We moeten elk paar hiervan in de array tellen.
Het tellen van alle arrayleden die minder zijn dan rechts ervan en het resultaat toevoegen aan de uitvoer is een eenvoudige benadering.
Deze oplossing heeft een O(n2) complexiteit, waarbij n de grootte van de invoer is.
26. Wat is het probleem met het opvangen van regenwater?
Het vinden van het meeste water dat kan worden opgesloten in een bepaalde reeks staven met een breedte van elk één eenheid staat bekend als het probleem van het "vangen van regenval".
Het doel is om de hoogste balk te bepalen die links en rechts van elke balk mag worden geplaatst. Het minimum van de voorste balkjes links en rechts, minus de hoogte van de huidige balk, is de hoeveelheid water die bovenop elke balk wordt opgeslagen.
Conclusie
In vergelijking met andere gegevensstructuuronderwerpen zijn arrays eenvoudiger. Om array-interviewvragen te beantwoorden, moet u een fundamenteel begrip van arrays hebben.
U moet de fundamenten van arrays uitgebreid doornemen, inclusief array-bewerkingen (van het declareren/maken van een array tot het openen/wijzigen van array-items), evenals programmeerconcepten zoals lussen, recursie en basisoperators om vragen over array-interviews met succes te beantwoorden. Herken het probleem volledig.
Bij vragen dient u opheldering te vragen. Denk erover na om het probleem op te delen in meer beheersbare delen. Zorg ervoor dat u het algoritme in gedachten heeft voordat u begint met programmeren; schrijf het op of visualiseer het in een stroomdiagram. begin dan met het schrijven van code.
Laat een reactie achter