Innholdsfortegnelse[Gjemme seg][Forestilling]
- 1. Hvordan definerer du en Array?
- 2. Dynamiske matriser: Hva er de? Hva skiller dem fra Basic Arrays?
- 3. Hvordan varierer en matrise og en ordbok fra hverandre?
- 4. List noen av fordelene og ulempene med arrays.
- 5. Hva refererer "Sparse Array" til?
- 6. Når vil du velge en koblet liste fremfor en matrise?
- 7. Hva skiller en indeksert matrise fra en assosiativ matrise?
- 8. Hvilke fordeler har Heap fremfor sorterte arrays?
- 9. Kan vi definere størrelsen på matrisen til å være negativ?
- 10. Hvordan finner du det manglende hele tallet i en 1 til 100-elements matrise?
- 11. Hvordan finner du indeksen til et element i en matrise?
- 12. Hvordan kan du bli kvitt et spesifikt element fra en matrise?
- 13. Hvordan kan to arrayers likhet verifiseres?
- 14. Når vi diskuterer arrays, hva mener du med setningene "Dimensjon" og "Subscript"?
- Koding av intervjuspørsmål
- 15. Oppsøk et par i en matrise som har den angitte summen
- 16. Binær array sortering med lineær tid
- 17. Finn det største to-int-produktet i en matrise.
- 18. Hvordan flytte alle arrayets nuller til slutten
- 19. Hvordan sortere en matrise med to oppføringer som byttes i én operasjon.
- 20. Hvordan kombinere to sorterte arrays på plass.
- 21. Hvordan omorganisere en rekke varer i vekslende høye og lave posisjoner?
- 22. Hvordan erstatte hvert element i en matrise uten å bruke en divisjonsoperator med produktet av hvert element i matrisen?
- 23. Finn det oddeste elementet i en matrise i logaritmisk tid
- 24. Hvordan få det påfølgende større elementet for hvert element i en sirkulær matrise?
- 25. Finne en arrays inversjonstall?
- 26. Hva er problemet med å fange opp regnvann?
- konklusjonen
Kodeintervjuer inneholder en serie DSA-spørsmål. Du bør være dyktig med arrays hvis du gjør deg klar for ditt kommende teknologiintervju med FAANG eller en annen Tier-1 teknologibedrift.
I de fleste kodeintervjuer kommer den på andreplass til Strings. En matrise er en gruppering av relaterte dataelementer som holdes i umiddelbar nærhet av hverandre i minnet.
Siden de er koblet til alle programmeringsspråk, som C, C++, Java, Python, Perl og Ruby, er de overalt. Fortsett å lese for noen øve kodingsutfordringer og intervjuspørsmål og svar basert på matriser.
Python vil bli brukt i dette innlegget for å takle kodingsproblemene fordi det er enkelt å bruke, forstå og må være kjent for de fleste av oss.
La oss begynne.
1. Hvordan definerer du en Array?
- En gruppe relaterte datatyper er en matrise.
- Matriser er alltid faste.
- Den samme typen variabel er lagret flere steder av array-objekter.
- Primitive typer og objektreferanser er begge kompatible med det.
2. Dynamiske matriser: Hva er de? Hva skiller dem fra Basic Arrays?
Den automatiske skaleringen som dynamiske arrays (også referert til som growable arrays, resisable arrays, changeable arrays eller ArrayLists i Java) gir er en betydelig fordel.
Du må alltid vite hvor mange elementer matrisen din vil lagre på forhånd siden matriser har en fast størrelse. En dynamisk matrise, derimot, vokser etter hvert som du legger til flere medlemmer til den, slik at du ikke trenger å vite den nøyaktige størrelsen på forhånd.
3. Hvordan varierer en matrise og en ordbok fra hverandre?
Dette er en grunnleggende rekke intervjuspørsmål som stilles regelmessig. Følgende er de viktigste forskjellene mellom matriser og ordbøker:
- En matrise er en ordnet liste over lignende elementer. Ordbok, derimot, har nøkkelverdi-par.
- Matrisestørrelser kan endres dynamisk. Slike dynamiske ideer finnes ikke i ordbøker.
- Før du bruker en matrise, må størrelsen spesifiseres. Ordbokstørrelser trenger ikke å tilpasses.
- Bruk Redim-setningen hvis du ønsker å utvide matrisens størrelse. I ordbøker kan et element legges til uten erklæring.
4. List noen av fordelene og ulempene med arrays.
Fordeler:
- Matriser kan sortere en rekke elementer samtidig.
- Annen datastrukturer, som stabler, køer, koblede lister, trær, grafer, etc., kan implementeres i en matrise.
- En indeks kan brukes til å nå et element i en matrise.
Ulemper:
- En arrays størrelse må deklareres på forhånd. I øyeblikket av array-deklarasjonen er det imidlertid ikke sikkert vi er klar over størrelsen vi trenger.
- Strukturen til matrisen er statisk. Det innebærer at matrisestørrelsen alltid er fast og at minneallokering ikke kan økes eller reduseres.
5. Hva refererer "Sparse Array" til?
En sparse matrise er en datamatrise som har mange oppføringer med null verdier. I kontrast inneholder en tett matrise de fleste av elementene med verdier som ikke er null. Indeksene til en sparsom matrise, som konverterer tall til objekter, kan inkludere mellomrom. Sammenlignet med et HashMap er de mer minneeffektive.
6. Når vil du velge en koblet liste fremfor en matrise?
Når du bruker koblede lister i stedet for matriser, bør du vurdere:
- Du trenger ingen elementer for å ha tilfeldig tilgang.
- Der tidsmessig forutsigbarhet er essensielt, trenger du innsetting og fjerning fra listen konstant.
- For å opprette en prioritert kø, må du kanskje plassere elementer i midten av listen.
- Du aner ikke hvor lang listen vil være. Hvis matrisestørrelsen øker, må du re-deklarere og duplisere minne, akkurat som med enkle matriser.
7. Hva skiller en indeksert matrise fra en assosiativ matrise?
De primære forskjellene mellom assosiative og indekserte matriser er oppført i følgende tabell.
- Et nøkkel-verdi-par i tekst- eller numerisk format brukes til å sortere en assosiativ matrise. Den indekserte matrisens nøkler er alle numeriske, og hver nøkkel er koblet til en distinkt verdi.
- I en assosiativ matrise kan nøkkelen være en streng. Indeksert matrise med heltallsnøkler som starter på 0.
- En to-kolonne tabell etterligner oppførselen til en assosiativ matrise. I likhet med en enkeltkolonnetabell er indekserte matriser.
- Kart er en assosiativ matrisetype. En indeksmatrise er ikke et kart.
8. Hvilke fordeler har Heap fremfor sorterte arrays?
Tidseffektiviteten ved å bruke Heap over Sorted Arrays er den viktigste fordelen. Selv om haugoperasjoner er raskere, krever sortering av en matrise mye tid. En haug kan oppdage det minste elementet betydelig raskere enn en matrise kan sorteres.
En gitt samling av tall kan ordnes på en av to måter ved å bruke Sorterte arrays. På den annen side, for en gitt samling av tall, kan det være mer enn én potensiell haug.
9. Kan vi definere størrelsen på matrisen til å være negativ?
Nei, vi kan ikke definere et negativt heltall til å være størrelsen på en matrise. Det vil ikke være en kompileringsfeil hvis vi erklærer. Under kjøring vil vi imidlertid støte på et NegativeArraySizeException.
10. Hvordan finner du det manglende hele tallet i en 1 til 100-elements matrise?
Summen av serien kan beregnes ved å bruke følgende funksjon: n (n + 1) / 2
Bare hvis matrisen ikke har noen duplikater eller mangler mer enn ett heltall, vil denne funksjonen fungere. Om en matrise har dupliserte elementer, kan du sortere matrisen for å se om det er noen elementer som er likeverdige.
11. Hvordan finner du indeksen til et element i en matrise?
Et elements indeks kan oppdages via et lineært eller binært søk. Inntil den finner treffet til det nødvendige elementet, går en lineær søkefunksjon over hvert element i en matrise. Den returnerer indeksen når den finner det matchende elementet. Følgelig er det lineære søkets temporale kompleksitet O. (n). Både en sortert og en usortert matrise kan bruke lineært søk.
Ved å bruke et binært søk, som kontinuerlig deler matrisen i to til medianen av intervallet samsvarer med det nødvendige elementet og gir indeksen, kan du få elementets indeks hvis matrisen er sortert. Følgelig er det binære søkets tidsmessige kompleksitet O. (log n).
12. Hvordan kan du bli kvitt et spesifikt element fra en matrise?
Siden du ikke bare kan slette elementer fra den opprinnelige matrisen siden de er faste sett med en definert størrelse, søker intervjueren at du skal foreslå en annen tilnærming og håndtere problemet som spørsmålet reiser. Den beste handlingen er å lage en ny array for å slette et element. Du kan duplisere elementene fra den første matrisen i denne matrisen og bare inkludere elementet du ønsker å slette.
En annen strategi innebærer å finne målelementet i matrisen og deretter reversere rekkefølgen på alle elementene som er til høyre for målelementet.
13. Hvordan kan to arrayers likhet verifiseres?
Du må først verifisere lengdene til de to angitte arrayene. De samsvarende elementene til begge matrisene sammenlignes når lengdene deres er like. De to matrisene vil bli sett på som like. hvis hvert par av komponenter i hver korrespondanse er like. Denne tilnærmingen anbefales ikke å kontrollere likheten mellom to arrays hvis arrayene er store i størrelse, siden det vil ta mye tid. Du kan også bruke equals()-metoden inkludert i Arrays-klassen, men hvis intervjueren ber deg om å sammenligne to arrays uten å bruke innebygde metoder, vil denne måten være nyttig.
14. Når vi diskuterer arrays, hva mener du med setningene "Dimensjon" og "Subscript"?
"Dimensjonen" til en matrise er antallet indekser, eller abonnenter, som kreves for å identifisere hvert enkelt medlem. Abonnementer og dimensjoner kan være uklare. En dimensjon er en beskrivelse av rekkevidden av tillatte nøkler, mens et abonnement er et tall. Det kreves bare ett abonnement for hver matrisedimensjon.
For eksempel har arrayen arr[10][5] to dimensjoner. Størrelse 10 på den ene og 5 på den andre. For å adressere komponentene, trenger du to abonnementer. Begge er mellom 0 og 4; en mellom 0 og 9, inklusive.
Koding av intervjuspørsmål
15. Oppsøk et par i en matrise som har den angitte summen
For eksempel,
Inngang:
- tall = [8, 7, 2, 5, 3, 1]
- mål = 10
Utgang:
- Par funnet (8, 2)
- Or
- Par funnet (7, 3)
Inngang:
- tall = [5, 2, 6, 8, 1, 9]
- mål = 12
Utgang:
- Finner ikke paret
16. Binær array sortering med lineær tid
Sorter en binær matrise i lineær tid og i et fast område. Utgangen bør vise alle nuller først, deretter alle enere.
For eksempel,
- Inndata: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Utdata: { 0, 0, 0, 0, 1, 1, 1, 1 }
En enkel tilnærming ville være å beregne matrisens totale antall 0-er, si k, og deretter fylle de første k-indeksene i matrisen med 0-er og de resterende indeksene med 1. Som et alternativ kan vi beregne hvor mange 1-ere som er totalt i matrise k, fyll de siste k-indeksene i matrisen med 1, og la resten av indeksene være fylt med 0.
Den gitte tilnærmingen har en O(n) tidskompleksitet og bruker ingen ekstra lagring, der n er størrelsen på inngangen.
17. Finn det største to-int-produktet i en matrise.
Finn det største produktet av to tall i en heltallsmatrise.
Tenk på matrisen 10 3 5 6 2 som et eksempel. (-10, -3) eller (5, 6) paret er det høyeste produktet.
Å tenke på hver elementkombinasjon og finne ut av produktet deres er en tåpelig tilnærming. Hvis produktet til det gjeldende paret er større enn det maksimale produktet som er oppnådd så langt, oppdater det maksimale produktet. Skriv ut komponentene til sluttproduktet sist.
Løsningen ovenfor, hvor n er mengden av input, har en tidskompleksitet på O(n2) og tar ikke opp mer plass.
18. Hvordan flytte alle arrayets nuller til slutten
Flytt alle nullene i en heltallsmatrise til slutten. Svaret bør unngå å bruke konstant plass og bevare den relative rekkefølgen til arrayens komponenter.
Inngang: {1,2,3,0,8,0,4,7}
Utdata vil være {1,2,3,8,4,7,0,0}
Sett elementet på følgende tilgjengelige posisjon i matrisen hvis det gjeldende elementet ikke er null. Fyll alle gjenværende indekser med 0 når matrisens elementer er behandlet.
Den foregående løsningen har en O(n) tidskompleksitet, der n er størrelsen på inngangen.
19. Hvordan sortere en matrise med to oppføringer som byttes i én operasjon.
Sorter en matrise i den lineære tiden gitt to byttede elementer og en matrise med alle elementene ordnet i stigende rekkefølge. Lat som om matrisen ikke inneholder duplikater.
Inndata:= [1,9,3,4,7,2] eller [9,3,7,2,1,4] eller [2,4,1,7,3,9]
Utgang: = [1,2,3,4,7,9]
Fra og med det andre elementet i matrisen, er målet å sammenligne hvert element med forgjengeren. Plasseringen av tvisten lagres ved å ta to pekere, x og y.
Oppdater x til forrige elements indeks og y til gjeldende elements indeks hvis førstnevnte er større enn sistnevnte. Oppdater y til indeksen til det gjeldende elementet hvis det viser seg at det forrige elementet er større enn det gjeldende elementet.
Bytt til slutt elementene ved indeksene x og y når vi er ferdige med å behandle hvert tilstøtende elementpar.
På grunn av det faktum at den nevnte metoden bare utfører en enkelt skanning av inngangsgruppen med størrelse n, er dens tidskompleksitet O(n). Det er ikke nødvendig med ekstra rom for løsningen.
20. Hvordan kombinere to sorterte arrays på plass.
Slå sammen elementene i arrays X[] og Y[] – to sorterte arrays med størrelse m og n hver – ved å beholde den sorterte rekkefølgen, det vil si ved å fylle X[] med de første m minste elementene og fylle Y[] med gjenværende elementer.
Hvis et element i matrisen X[] allerede er i riktig posisjon (dvs. det som er det minste av de gjenværende elementene), se bort fra det; Ellers erstatt det med det minste elementet, som også tilfeldigvis er det første medlemmet av Y[]. For å beholde den sorterte rekkefølgen etter bytte, overfør elementet (nå ved Y[0]) til riktig plassering i Y[].
Den første matrisens størrelse er m og den andre matrisens størrelse er n, og tidskompleksiteten er O(mn).
21. Hvordan omorganisere en rekke varer i vekslende høye og lave posisjoner?
Omorganiser en heltallsmatrise slik at hvert påfølgende medlem er større enn de foregående og følgende elementene. Anta at matrisen ikke inkluderer noen dupliserte elementer.
Sortering av matrisen eller bruk av ekstra plass er ikke nødvendig for en effektiv tilnærming. Planen er til å begynne med det andre medlemmet av matrisen og gå opp med to for hver loop-iterasjon.
Bytt komponentene hvis det siste elementet overstiger det første. På samme måte bytter du begge elementene hvis følgende element er større enn det gjeldende elementet. Vi vil oppnå ønsket matrise som samsvarer med de spesifiserte restriksjonene ved avslutningen av løkken.
22. Hvordan erstatte hvert element i en matrise uten å bruke en divisjonsoperator med produktet av hvert element i matrisen?
Uten å bruke divisjonsoperatoren, erstatt hvert element i en heltallsmatrise med produktet av alle andre elementer.
I lineær tid og konstant rom kan vi bruke rekursjon for å løse dette problemet. Rekursivt å beregne produktene til hvert element i høyre undergruppe og sende det venstre undergruppeproduktet som funksjonsparametere er ideen.
Tidskompleksiteten er O(n).
23. Finn det oddeste elementet i en matrise i logaritmisk tid
Gitt en heltallsmatrise der alle unntatt ett medlem har et like antall forekomster, er problemet å bestemme hvor mange ganger dette ene elementet vises. Finn det odde forekommende elementet i logaritmisk tid og konstant rom hvis de samme elementene forekommer i par i matrisen og det aldri kan være mer enn to forekomster av et gitt element på rad.
XOR-operasjonen gjør det mulig for oss å løse dette problemet i lineær tid. Målet er å XOR hvert element i matrisen. Bare de oddetall forekommende elementene forblir etter at de partall forekommende elementene kansellerer hverandre.
Dette problemet kan til og med løses i O(log(n))-tid.
24. Hvordan få det påfølgende større elementet for hvert element i en sirkulær matrise?
Det neste større elementet for hvert element i en sirkulær heltallsmatrise skal være plassert. Det første større hele tallet etter et element x i matrisen er det påfølgende større elementet i det elementet.
Fra høyre til venstre kan vi operere på array-elementer. Målet er å løkke for hvert element x til enten stabelen er tom eller vi har et høyere element på toppen av den. Sett det neste større elementet av x til å vises på toppen av stabelen når det gjør det.
25. Finne en arrays inversjonstall?
Finn det totale antallet inversjoner av en matrise. Et par I j) er referert til å være en inversjon av en matrise A hvis I j) og (A[i] > A[j]). Vi må telle hvert par av disse i matrisen.
Å telle alle array-medlemmer som er færre enn den til høyre og legge resultatet til utdataene er en enkel tilnærming.
Denne løsningen har en O(n2) kompleksitet, der n er størrelsen på inngangen.
26. Hva er problemet med å fange opp regnvann?
Å finne mest mulig vann som kan fanges i et gitt sett med stenger med en bredde på én enhet hver er kjent som problemet med "fangst av nedbør".
Målet er å bestemme den høyeste stolpen som kan plasseres til venstre og høyre for hver stolpe. Minimum av de ledende stolpene til venstre og høyre, minus høyden på gjeldende bar, er mengden vann som er lagret på toppen av hver bar.
konklusjonen
Sammenlignet med andre datastrukturemner er arrays enklere. For å kunne klare array-intervjuspørsmål, må du ha en grunnleggende forståelse av arrays.
Du bør grundig gjennomgå grunnlaget for arrays, inkludert array-operasjoner (fra å deklarere/opprette en array til å få tilgang til/endre array-elementer), samt programmeringskonsepter som loops, rekursjon og grunnleggende operatører for å kunne svare på array-intervjuspørsmål. Gjenkjenne problemet fullstendig.
Du bør søke avklaring hvis du har spørsmål. Tenk på å dele opp problemet i mer håndterbare deler. Sørg for at du har algoritmen i tankene før du begynner å programmere; skriv det ned eller visualiser det i et flytskjema. begynn deretter å skrive kode.
Legg igjen en kommentar