Përmbajtje[Fshih][Shfaqje]
- 1. Si e përcaktoni një varg?
- 2. Vargjet dinamike: Cilat janë ato? Çfarë i veçon ata nga Vargjet Bazë?
- 3. Si ndryshojnë një grup dhe një fjalor nga njëri-tjetri?
- 4. Rendisni disa nga përfitimet dhe të metat e vargjeve.
- 5. Çfarë i referohet “Sparse Array”?
- 6. Kur do të zgjidhnit një listë të lidhur mbi një grup?
- 7. Çfarë e dallon një grup të indeksuar nga një grup shoqërues?
- 8. Çfarë avantazhesh ka Heap ndaj vargjeve të renditura?
- 9. A mund të përcaktojmë që madhësia e grupit të jetë negative?
- 10. Si e gjeni numrin e plotë që mungon në një grup prej 1 deri në 100 elemente?
- 11. Si e gjeni indeksin e një elementi në një grup?
- 12. Si mund të heqësh qafe një element specifik nga një grup?
- 13. Si mund të verifikohet barazia e dy vargjeve?
- 14. Kur diskutojmë vargje, çfarë kuptoni me frazat "Dimension" dhe "Subscript"?
- Pyetjet e Kodimit të Intervistës
- 15. Kërkoni një çift në një grup që ka shumën e specifikuar
- 16. Renditja e vargjeve binare me kohë lineare
- 17. Gjeni produktin më të madh me dy int në një grup.
- 18. Si të zhvendosen të gjitha zerot e grupit në fund
- 19. Si të renditni një grup me dy hyrje që ndërrohen në një veprim.
- 20. Si të kombinohen dy grupe të renditura në vend.
- 21. Si të rirenditni një grup artikujsh në pozicione të alternuara të larta dhe të ulëta?
- 22. Si të zëvendësohet çdo element i një vargu pa përdorur një operator ndarjeje me produktin e secilit element në grup?
- 23. Gjeni elementin më të çuditshëm në një varg në kohën logaritmike
- 24. Si të merret elementi më i madh pasues për secilin element në një grup rrethor?
- 25. Gjeni numrin e përmbysjes së një vargu?
- 26. Cili është problemi i bllokimit të ujit të shiut?
- Përfundim
Intervistat e kodimit përmbajnë një sërë pyetjesh DSA. Ju duhet të jeni të aftë me vargje nëse po përgatiteni për intervistën tuaj të ardhshme të teknologjisë me FAANG ose një biznes tjetër teknologjik të nivelit 1.
Në shumicën e intervistave të kodimit, ajo vjen në vendin e dytë pas Strings. Një grup është një grupim i elementeve të të dhënave të lidhura që mbahen në afërsi të njëri-tjetrit në memorie.
Duke qenë se ato janë të lidhura me të gjitha gjuhët e programimit, si C, C++, Java, Python, Perl dhe Ruby, ato janë kudo. Vazhdoni të lexoni për disa sfida praktike të kodimit dhe pyetjet dhe përgjigjet e intervistës bazuar në vargje.
Python do të përdoret në këtë postim për të trajtuar çështjet e kodimit sepse është i thjeshtë për t'u përdorur, për t'u kuptuar dhe duhet të jetë i njohur për shumicën prej nesh.
Le të fillojmë.
1. Si e përcaktoni një varg?
- Një grup i llojeve të të dhënave të lidhura është një grup.
- Vargjet janë gjithmonë të fiksuara.
- I njëjti lloj ndryshore ruhet në disa vende nga objektet e grupit.
- Llojet primitive dhe referencat e objekteve janë të dyja në përputhje me të.
2. Vargjet dinamike: Cilat janë ato? Çfarë i veçon ata nga Vargjet Bazë?
Shkallëzimi automatik që ofrojnë vargjet dinamike (të referuara gjithashtu si vargje të rritshme, vargje të ridimensionueshme, vargje të ndryshueshme ose ArrayLists në Java) është një avantazh i rëndësishëm.
Ju gjithmonë duhet të dini se sa elementë do të ruajë grupi juaj paraprakisht pasi vargjet kanë një madhësi fikse. Një grup dinamik, nga ana tjetër, rritet ndërsa shtoni anëtarë shtesë në të, kështu që nuk keni nevojë të dini madhësinë e tij të saktë paraprakisht.
3. Si ndryshojnë një grup dhe një fjalor nga njëri-tjetri?
Ky është një grup pyetjesh intervistash të bazuara në baza që bëhen rregullisht. Më poshtë janë dallimet kryesore midis vargjeve dhe fjalorëve:
- Një grup është një listë e renditur e artikujve të ngjashëm. Fjalori, nga ana tjetër, ka çifte çelës-vlerë.
- Madhësitë e grupeve mund të ndryshojnë në mënyrë dinamike. Ide të tilla dinamike nuk ekzistojnë në fjalorë.
- Përpara përdorimit të një grupi, madhësia e tij duhet të specifikohet. Madhësitë e fjalorit nuk kanë nevojë të personalizohen.
- Përdorni deklaratën Redim nëse dëshironi të zgjeroni madhësinë e grupit. Në fjalorë, një element mund të shtohet pa një deklaratë.
4. Rendisni disa nga përfitimet dhe të metat e vargjeve.
Përparësitë:
- Vargjet mund të renditin një numër elementesh njëkohësisht.
- tjetër strukturat e të dhënave, si rafte, radhë, lista të lidhura, pemë, grafikë, etj., mund të zbatohen në një grup.
- Një indeks mund të përdoret për të arritur një element të një grupi.
Disavantazhet:
- Madhësia e një grupi duhet të deklarohet paraprakisht. Sidoqoftë, në momentin e deklarimit të grupit, ne mund të mos jemi të vetëdijshëm për madhësinë që kërkojmë.
- Struktura e grupit është statike. Kjo nënkupton që madhësia e grupit është gjithmonë fikse dhe se shpërndarja e memories nuk mund të rritet ose zvogëlohet.
5. Çfarë i referohet “Sparse Array”?
Një grup i rrallë është një grup i të dhënave që ka shumë hyrje me vlera zero. Në të kundërt, një grup i dendur përmban shumicën e artikujve të tij me vlera jo zero. Indekset e një grupi të rrallë, i cili konverton numrat në objekte, mund të përfshijnë boshllëqe. Krahasuar me një HashMap, ato janë më efikase në memorie.
6. Kur do të zgjidhnit një listë të lidhur mbi një grup?
Kur përdorni listat e lidhura në vend të vargjeve, merrni parasysh:
- Ju nuk keni nevojë për ndonjë element për të pasur akses të rastësishëm.
- Aty ku parashikueshmëria kohore është thelbësore, keni nevojë për futje dhe heqje në kohë të vazhdueshme nga lista.
- Për të krijuar një radhë prioritare, mund t'ju duhet të vendosni artikujt në qendër të listës.
- Nuk e keni idenë se sa e gjatë do të jetë lista. Nëse madhësia e grupit rritet, duhet të rideklaroni dhe kopjoni memorien, ashtu si me vargje të thjeshta.
7. Çfarë e dallon një grup të indeksuar nga një grup shoqërues?
Dallimet kryesore midis vargjeve shoqëruese dhe të indeksuara janë renditur në tabelën e mëposhtme.
- Një çift çelës-vlerë në format teksti ose numerik përdoret për të renditur një grup shoqërues. Çelësat e grupit të indeksuar janë të gjithë numerikë dhe çdo çelës është i lidhur me një vlerë të veçantë.
- Në një grup shoqërues, çelësi mund të jetë një varg. Vargu i indeksuar me çelësa me numra të plotë që fillojnë nga 0.
- Një tabelë me dy kolona imiton sjelljen e një grupi shoqërues. Ngjashëm me një tabelë me një kolonë janë vargjet e indeksuar.
- Hartat janë një lloj grupi asociativ. Një grup indeksimi nuk është një hartë.
8. Çfarë avantazhesh ka Heap ndaj vargjeve të renditura?
Efikasiteti në kohë i përdorimit të grupit mbi vargje të renditura është përfitimi kryesor. Ndërsa operacionet e grumbullit janë më të shpejta, renditja e një grupi kërkon shumë kohë. Një grumbull mund të zbulojë elementin më të vogël shumë më shpejt sesa mund të renditet një grup.
Një koleksion i caktuar numrash mund të organizohet në njërën nga dy mënyrat duke përdorur vargje të renditura. Nga ana tjetër, për një koleksion të caktuar numrash, mund të ketë më shumë se një grumbull potencial.
9. A mund të përcaktojmë që madhësia e grupit të jetë negative?
Jo, ne nuk mund të përcaktojmë një numër të plotë negativ në madhësinë e një grupi. Nuk do të ketë një gabim në kohën e përpilimit nëse deklarojmë. Në kohën e ekzekutimit, megjithatë, do të hasim një NegativeArraySizeException.
10. Si e gjeni numrin e plotë që mungon në një grup prej 1 deri në 100 elemente?
Totali i serive mund të llogaritet duke aplikuar funksionin e mëposhtëm: n (n + 1) / 2
Ky funksion do të funksionojë vetëm nëse grupi nuk ka ndonjë dublikatë ose nëse mungon më shumë se një numër i plotë. Nëse një grup ka elementë dublikatë, ju mund ta renditni grupin për të parë nëse ka ndonjë element që është ekuivalent.
11. Si e gjeni indeksin e një elementi në një grup?
Indeksi i një elementi mund të zbulohet nëpërmjet një kërkimi linear ose binar. Derisa të gjejë përputhjen e elementit të kërkuar, një funksion linear kërkimi qarkullon mbi çdo element në një grup. E kthen indeksin sapo të gjejë elementin që përputhet. Rrjedhimisht, kompleksiteti kohor i kërkimit linear është O. (n). Si një grup i renditur ashtu edhe një grup i pazgjedhur mund të përdorin kërkimin linear.
Duke përdorur një kërkim binar, i cili e ndan vazhdimisht grupin në gjysmë derisa medianaja e intervalit të përputhet me elementin e kërkuar dhe të sigurojë indeksin, mund të merrni indeksin e elementit nëse grupi është i renditur. Rrjedhimisht, kompleksiteti i përkohshëm i kërkimit binar është O. (log n).
12. Si mund të heqësh qafe një element specifik nga një grup?
Meqenëse nuk mund të fshini thjesht elementë nga grupi origjinal pasi ato janë grupe fikse me një madhësi të përcaktuar, intervistuesi po kërkon që ju të sugjeroni një qasje të ndryshme dhe të merreni me problemin që ngre pyetja. Mënyra më e mirë e veprimit është të krijoni një grup të ri për të fshirë një element. Ju mund të kopjoni elementet nga grupi i parë në këtë grup dhe të përfshini vetëm elementin që dëshironi të fshini.
Një strategji tjetër përfshin gjetjen e elementit të synuar në grup dhe më pas ndryshimin e renditjes së të gjithë artikujve që janë në të djathtë të elementit të synuar.
13. Si mund të verifikohet barazia e dy vargjeve?
Së pari duhet të verifikoni gjatësinë e dy vargjeve të ofruara. Artikujt që përputhen të të dy vargjeve krahasohen kur gjatësitë e tyre janë të barabarta. Të dy vargjet do të konsiderohen të barabarta. nëse çdo çift i komponentëve në çdo korrespondencë është i barabartë. Kjo qasje nuk këshillohet për të kontrolluar barazinë e dy vargjeve nëse vargjet janë të mëdha në madhësi pasi do të marrë shumë kohë. Ju gjithashtu mund të përdorni metodën e barabartë () të përfshirë në klasën Arrays, megjithatë, nëse intervistuesi ju kërkon të krahasoni dy vargje pa përdorur metoda të integruara, kjo mënyrë do të jetë e dobishme.
14. Kur diskutojmë vargje, çfarë kuptoni me frazat "Dimension" dhe "Subscript"?
"Dimensioni" i një grupi është numri i indekseve, ose nënshkrimeve, të kërkuara për të identifikuar çdo anëtar individual. Abonimet dhe dimensionet mund të jenë të paqarta. Një dimension është një përshkrim i gamës së çelësave të lejuar, ndërsa një nënshkrim është një numër. Kërkohet vetëm një nënshkrim për çdo dimension të grupit.
Për shembull, grupi arr[10][5] ka dy dimensione. Madhësitë 10 në njërën dhe 5 në tjetrën. Për të adresuar komponentët e tij, ju nevojiten dy nënshkrime. Të dyja janë midis 0 dhe 4; një mes 0 dhe 9, përfshirë.
Pyetjet e Kodimit të Intervistës
15. Kërkoni një çift në një grup që ka shumën e specifikuar
Për shembull,
input:
- numra = [8, 7, 2, 5, 3, 1]
- caku = 10
output:
- Çifti u gjet (8, 2)
- Or
- Çifti u gjet (7, 3)
input:
- numra = [5, 2, 6, 8, 1, 9]
- caku = 12
output:
- Çifti nuk u gjet
16. Renditja e vargjeve binare me kohë lineare
Renditni një grup binar në kohë lineare dhe në një zonë fikse. Prodhimi duhet të shfaqë së pari të gjitha zerat, pastaj të gjitha ato.
Për shembull,
- Hyrja: {1, 0, 1, 0, 1, 0, 0, 1 }
- Prodhimi: {0, 0, 0, 0, 1, 1, 1, 1 }
Një qasje e drejtpërdrejtë do të ishte llogaritja e numrit total të grupit prej 0, le të themi k, dhe më pas plotësoni k indekset e para në grup me 0 dhe indekset e mbetura me 1. Si alternativë, ne mund të llogarisim sa 1 janë gjithsej në grupi k, plotësoni k indekset e fundit në grup me 1 dhe lërini pjesën tjetër të indekseve të mbushura me 0.
Qasja e dhënë ka një kompleksitet kohor O(n) dhe nuk përdor ruajtje shtesë, ku n është madhësia e hyrjes.
17. Gjeni produktin më të madh me dy int në një grup.
Gjeni prodhimin më të madh të dy numrave në një grup të plotë.
Mendoni për grupin 10 3 5 6 2 si shembull. Çifti (-10, -3) ose (5, 6) është produkti më i lartë.
Të mendosh për çdo kombinim elementesh dhe të kuptosh produktin e tyre është një qasje marrëzi. Nëse produkti i çiftit aktual është më i madh se produkti maksimal i marrë deri më tani, përditësoni produktin maksimal. Printoni përbërësit e produktit përfundimtar.
Zgjidhja e mësipërme, ku n është sasia e hyrjes, ka një kompleksitet kohor prej O(n2) dhe nuk zë më hapësirë.
18. Si të zhvendosen të gjitha zerot e grupit në fund
Zhvendosni të gjitha zerot në një grup me numra të plotë deri në fund. Përgjigja duhet të shmangë përdorimin e hapësirës konstante dhe të ruajë rendin relativ të përbërësve të grupit.
Hyrja: {1,2,3,0,8,0,4,7}
Prodhimi do të jetë {1,2,3,8,4,7,0,0}
Vendoseni elementin në pozicionin e mëposhtëm të disponueshëm në grup nëse elementi aktual nuk është zero. Plotësoni të gjithë indekset e mbetura me 0 pasi të gjithë artikujt e grupit të jenë përpunuar.
Zgjidhja e mëparshme ka një kompleksitet kohor O(n), ku n është madhësia e hyrjes.
19. Si të renditni një grup me dy hyrje që ndërrohen në një veprim.
Renditni një varg në kohën lineare duke pasur parasysh dy elementë të ndërruar dhe një grup me të gjithë elementët e tij të renditur në rend rritës. Pretendoni se grupi nuk përmban dublikatë.
Hyrja:= [1,9,3,4,7,2] ose [9,3,7,2,1,4] ose [2,4,1,7,3,9]
Prodhimi: = [1,2,3,4,7,9]
Duke filluar me elementin e dytë në grup, objektivi është të krahasohet secili element me paraardhësin e tij. Pozicioni i mosmarrëveshjes ruhet duke marrë dy tregues, x dhe y.
Përditëso x në indeksin e elementit të mëparshëm dhe y në indeksin e elementit aktual nëse i pari është më i madh se i dyti. Përditësoni y në indeksin e elementit aktual nëse rezulton se elementi i mëparshëm është më i madh se elementi aktual.
Së fundi, ndërroni elementet në indekset x dhe y pasi të kemi përfunduar përpunimin e çdo çifti elementesh ngjitur.
Për shkak të faktit se metoda e sipërpërmendur kryen vetëm një skanim të vetëm të grupit të hyrjes me madhësi n, kompleksiteti i tij kohor është O(n). Asnjë dhomë shtesë nuk është e nevojshme për zgjidhjen.
20. Si të kombinohen dy grupe të renditura në vend.
Bashkoni artikujt e vargjeve X[] dhe Y[] - dy vargje të renditura me madhësi m dhe n secili - duke ruajtur rendin e renditur, domethënë duke mbushur X[] me elementët e parë m më të vegjël dhe duke mbushur Y[] me elementet e mbetura.
Nëse një element në grupin X[] është tashmë në pozicionin e duhur (dmth. ai që është më i vogli nga elementët e mbetur), shpërfilleni atë; përndryshe, zëvendësojeni atë me elementin më të vogël, i cili gjithashtu ndodh të jetë anëtari i parë i Y[]. Për të ruajtur rendin e renditur pas shkëmbimit, transferoni elementin (tani në Y[0]) në vendndodhjen e tij të duhur në Y[].
Madhësia e grupit të parë është m dhe madhësia e grupit të dytë është n, dhe kompleksiteti kohor është O(mn).
21. Si të rirenditni një grup artikujsh në pozicione të alternuara të larta dhe të ulëta?
Riorganizoni një grup me numra të plotë në mënyrë që çdo anëtar pasues të jetë më i madh se elementët e mëparshëm dhe të mëposhtëm. Supozoni se grupi nuk përfshin ndonjë element të kopjuar.
Renditja e grupit ose përdorimi i hapësirës shtesë nuk është i nevojshëm për një qasje efektive. Plani është, për të filluar, anëtari i dytë i grupit dhe rritet me dy për çdo përsëritje të ciklit.
Ndërroni komponentët nëse elementi i fundit tejkalon të parin. Në të njëjtën mënyrë, ndërroni të dy artikujt nëse elementi vijues është më i madh se elementi aktual. Ne do të marrim grupin e dëshiruar që përputhet me kufizimet e specifikuara në përfundim të ciklit.
22. Si të zëvendësohet çdo element i një vargu pa përdorur një operator ndarjeje me produktin e secilit element në grup?
Pa përdorur operatorin e ndarjes, zëvendësoni çdo element në një grup të plotë me produktin e të gjithë elementëve të tjerë.
Në kohën lineare dhe hapësirën konstante, ne mund të përdorim rekursionin për të adresuar këtë çështje. Llogaritja rekursive e produkteve të secilit element në nëngrupin e djathtë dhe kalimi i produktit të nëngarkimit të majtë si parametra funksioni është nocioni.
Kompleksiteti kohor është O(n).
23. Gjeni elementin më të çuditshëm në një varg në kohën logaritmike
Duke pasur parasysh një grup me numra të plotë në të cilin të gjithë përveç një anëtari kanë numra çift të ndodhive, problemi është të përcaktohet se sa herë shfaqet ky element. Gjeni elementin tek në kohën logaritmike dhe hapësirën konstante nëse të njëjtat elementë ndodhin në çifte në grup dhe nuk mund të ketë kurrë më shumë se dy raste të një elementi të caktuar në një rresht.
Operacioni XOR na mundëson ta zgjidhim këtë çështje në kohë lineare. Qëllimi është të XOR çdo element në grup. Mbeten vetëm elementet teke që ndodhin pasi elementët çift që ndodhin anulojnë njëri-tjetrin.
Ky problem mund të zgjidhet edhe në kohën O(log(n)).
24. Si të merret elementi më i madh pasues për secilin element në një grup rrethor?
Duhet të vendoset elementi tjetër më i madh për çdo element në një grup rrethor me numra të plotë. Numri i parë i plotë më i madh pas një elementi x në grup është elementi më i madh pasues i atij elementi.
Nga e djathta në të majtë, ne mund të operojmë me artikuj të grupit. Synimi është që të bëjmë lak për secilin element x derisa pirgu të jetë bosh ose të kemi një element më të lartë mbi të. Vendosni elementin tjetër më të madh të x që të shfaqet në krye të pirgut kur të shfaqet.
25. Gjeni numrin e përmbysjes së një vargu?
Gjeni numrin total të përmbysjeve të një vargu. Një çift I j) referohet të jetë një përmbysje e një vargu A nëse I j) dhe (A[i] > A[j]). Ne duhet të numërojmë çdo palë prej tyre në grup.
Numërimi i të gjithë anëtarëve të grupit që janë më pak se ai në të djathtë dhe shtimi i rezultatit në dalje është një qasje e drejtpërdrejtë.
Kjo zgjidhje ka një kompleksitet O(n2), ku n është madhësia e hyrjes.
26. Cili është problemi i bllokimit të ujit të shiut?
Gjetja e sasisë më të madhe të ujit që mund të bllokohet në një grup të caktuar shufrash me një gjerësi prej një njësie secila njihet si çështja e "rreshjeve të kurthit".
Qëllimi është të përcaktohet shiriti më i lartë që mund të vendoset në të majtë dhe në të djathtë të çdo shiriti. Minimumi i shufrave drejtuese majtas dhe djathtas, më pak lartësia e shiritit aktual, është sasia e ujit që ruhet në majë të çdo shiriti.
Përfundim
Krahasuar me temat e tjera të strukturës së të dhënave, vargjet janë më të thjeshta. Në mënyrë që të plotësoni pyetjet e intervistës së grupit, ju duhet të keni një kuptim themelor të vargjeve.
Ju duhet të rishikoni gjerësisht themelet e vargjeve, duke përfshirë operacionet e vargjeve (nga deklarimi/krijimi i një grupi te qasja/modifikimi i artikujve të grupit), si dhe konceptet e programimit si unazat, rekursioni dhe operatorët bazë në mënyrë që t'i përgjigjeni me sukses pyetjeve të intervistës së grupit. Njohni plotësisht çështjen.
Ju duhet të kërkoni sqarime nëse keni ndonjë pyetje. Mendoni për ndarjen e çështjes në pjesë më të menaxhueshme. Sigurohuni që të keni parasysh algoritmin përpara se të filloni programimin; shkruajeni ose vizualizoni atë në një diagram. pastaj filloni të shkruani kodin.
Lini një Përgjigju