Talaan ng nilalaman[Tago][Ipakita]
- 1. Paano mo tukuyin ang isang Array?
- 2. Mga Dynamic na Array: Ano Sila? Ano ang pinagkaiba nila sa Basic Arrays?
- 3. Paano nag-iiba ang array at diksyunaryo sa isa't isa?
- 4. Ilista ang ilan sa mga pakinabang at kawalan ng mga array.
- 5. Ano ang tinutukoy ng “Sparse Array”?
- 6. Kailan ka pipili ng naka-link na listahan sa isang array?
- 7. Ano ang pagkakaiba ng isang naka-index na array mula sa isang nag-uugnay na array?
- 8. Ano ang mga pakinabang ng Heap kaysa sa mga pinagsunod-sunod na array?
- 9. Maaari ba nating tukuyin ang laki ng array upang maging negatibo?
- 10. Paano mo mahahanap ang nawawalang integer sa isang 1 hanggang 100-element array?
- 11. Paano mo mahahanap ang index ng isang elemento sa isang array?
- 12. Paano mo maaalis ang isang partikular na elemento mula sa isang array?
- 13. Paano mapapatunayan ang pagkakapantay-pantay ng dalawang array?
- 14. Kapag tinatalakay natin ang mga array, ano ang ibig mong sabihin sa mga pariralang "Dimensyon" at "Subscript"?
- Mga Tanong sa Panayam sa Pag-coding
- 15. Maghanap ng isang pares sa isang array na may tinukoy na kabuuan
- 16. Binary array sorting na may linear time
- 17. Hanapin ang pinakamalaking two-int na produkto sa isang array.
- 18. Paano ilipat ang lahat ng mga zero ng array hanggang sa dulo
- 19. Paano pag-uri-uriin ang isang array na may dalawang entry na inililipat sa isang operasyon.
- 20. Paano pagsamahin ang dalawang pinagsunod-sunod na array sa lugar.
- 21. Paano muling ayusin ang isang hanay ng mga item sa alternating mataas at mababang posisyon?
- 22. Paano palitan ang bawat elemento ng array nang hindi gumagamit ng division operator sa produkto ng bawat elemento sa array?
- 23. Hanapin ang oddest elemento sa isang array sa logarithmic time
- 24. Paano makukuha ang kasunod na mas malaking elemento para sa bawat elemento sa isang pabilog na hanay?
- 25. Maghanap ng bilang ng pagbabaligtad ng array?
- 26. Ano ang Problema sa Rain Water Trapping?
- Konklusyon
Ang mga panayam sa coding ay naglalaman ng isang serye ng mga tanong sa DSA. Dapat ay sanay ka sa mga arrays kung naghahanda ka para sa iyong nalalapit na tech interview sa FAANG o isa pang Tier-1 tech na negosyo.
Sa karamihan ng mga panayam sa coding, nasa pangalawang lugar ito sa Strings. Ang array ay isang pagpapangkat ng mga kaugnay na elemento ng data na pinananatiling malapit sa isa't isa sa memorya.
Dahil nakakonekta sila sa lahat ng mga programming language, tulad ng C, C++, Java, Python, Perl, at Ruby, nasa lahat sila. Magpatuloy sa pagbabasa para sa ilang mga hamon sa pagsasanay sa coding at mga tanong at sagot sa pakikipanayam batay sa mga array.
Gagamitin ang Python sa post na ito upang harapin ang mga isyu sa coding dahil simple itong gamitin, intindihin, at dapat pamilyar sa karamihan sa atin.
Magsimula tayo.
1. Paano mo tukuyin ang isang Array?
- Ang isang pangkat ng mga nauugnay na uri ng data ay isang array.
- Ang mga array ay palaging naayos.
- Ang parehong uri ng variable ay naka-imbak sa ilang mga lugar sa pamamagitan ng array object.
- Ang mga primitive na uri at object reference ay parehong tugma dito.
2. Mga Dynamic na Array: Ano Sila? Ano ang pinagkaiba nila sa Basic Arrays?
Malaking bentahe ang awtomatikong pag-scale na ibinibigay ng mga dynamic na array (tinutukoy din bilang growable array, resizable array, changeable array, o ArrayLists sa Java).
Dapat mong laging malaman kung gaano karaming mga elemento ang iimbak ng iyong array nang maaga dahil ang mga array ay may nakapirming laki. Ang isang dynamic na array, sa kabilang banda, ay lumalaki habang nagdaragdag ka ng mga karagdagang miyembro dito, kaya hindi mo na kailangang malaman ang eksaktong sukat nito nang maaga.
3. Paano nag-iiba ang array at diksyunaryo sa isa't isa?
Ito ay isang batayan na hanay ng mga tanong sa panayam na regular na itinatanong. Ang mga sumusunod ay ang mga pangunahing pagkakaiba sa pagitan ng mga array at mga diksyunaryo:
- Ang array ay isang nakaayos na listahan ng mga katulad na item. Ang diksyunaryo, sa kabilang banda, ay may mga pares ng key-value.
- Maaaring dynamic na magbago ang mga laki ng array. Ang gayong mga dinamikong ideya ay hindi umiiral sa mga diksyunaryo.
- Bago gumamit ng array, dapat tukuyin ang laki nito. Hindi kailangang i-customize ang mga sukat ng diksyunaryo.
- Gamitin ang Redim statement kung gusto mong palawakin ang laki ng array. Sa mga diksyunaryo, maaaring magdagdag ng elemento nang walang deklarasyon.
4. Ilista ang ilan sa mga pakinabang at kawalan ng mga array.
Bentahe:
- Maaaring pag-uri-uriin ng mga array ang ilang elemento nang sabay-sabay.
- iba mga kaayusan ng data, tulad ng mga stack, queues, naka-link na listahan, puno, graph, atbp., ay maaaring ipatupad sa isang array.
- Maaaring gamitin ang isang index upang maabot ang isang elemento ng isang array.
Disadvantages:
- Dapat ideklara nang maaga ang laki ng isang array. Sa sandali ng deklarasyon ng array, maaaring hindi namin, gayunpaman, magkaroon ng kamalayan sa laki na kailangan namin.
- Ang istraktura ng array ay static. Ipinahihiwatig nito na ang laki ng array ay palaging naayos at ang paglalaan ng memorya ay hindi maaaring dagdagan o bawasan.
5. Ano ang tinutukoy ng “Sparse Array”?
Ang kalat-kalat na array ay isang data array na may maraming mga entry na may mga zero na halaga. Sa kabaligtaran, ang isang siksik na array ay naglalaman ng karamihan sa mga item nito na may mga hindi zero na halaga. Ang mga indeks ng isang kalat-kalat na hanay, na nagko-convert ng mga numero sa mga bagay, ay maaaring magsama ng mga puwang. Kung ikukumpara sa isang HashMap, ang mga ito ay mas mahusay sa memorya.
6. Kailan ka pipili ng naka-link na listahan sa isang array?
Kapag gumagamit ng mga naka-link na listahan sa halip na mga array, isaalang-alang ang:
- Hindi mo kailangan ng anumang elemento para magkaroon ng random na access.
- Kung saan mahalaga ang temporal na predictability, kailangan mo ng patuloy na pagpasok at pagtanggal sa listahan.
- Upang makagawa ng priyoridad na pila, maaaring kailanganin mong ilagay ang mga item sa gitna ng listahan.
- Wala kang ideya kung gaano katagal ang listahan. Kung tumaas ang laki ng array, kailangan mong muling ideklara at i-duplicate ang memory, tulad ng sa mga simpleng array.
7. Ano ang pagkakaiba ng isang naka-index na array mula sa isang nag-uugnay na array?
Ang mga pangunahing pagkakaiba sa pagitan ng associative at indexed arrays ay nakalista sa sumusunod na talahanayan.
- Ang isang key-value pair sa text o numeric na format ay ginagamit upang pagbukud-bukurin ang isang associative array. Ang mga key ng naka-index na array ay numeric lahat, at ang bawat key ay konektado sa isang natatanging halaga.
- Sa isang associative array, ang susi ay maaaring isang string. Naka-index na array na may mga integer key na nagsisimula sa 0.
- Ginagaya ng dalawang-column table ang gawi ng isang associative array. Ang mga naka-index na array ay katulad ng isang single-column table.
- Ang mga mapa ay isang associative array type. Ang index array ay hindi isang mapa.
8. Ano ang mga pakinabang ng Heap kaysa sa mga pinagsunod-sunod na array?
Ang kahusayan sa oras ng paggamit ng Heap over Sorted Arrays ay ang pangunahing benepisyo. Habang ang mga heap operation ay mas mabilis, ang pag-uuri ng isang array ay nangangailangan ng maraming oras. Maaaring matuklasan ng isang heap ang pinakamaliit na elemento nang mas mabilis kaysa sa isang array ay maaaring pagbukud-bukurin.
Maaaring isaayos ang isang ibinigay na koleksyon ng mga numero sa isa sa dalawang paraan gamit ang Sorted Arrays. Sa kabilang banda, para sa isang naibigay na koleksyon ng mga numero, maaaring mayroong higit sa isang potensyal na tambak.
9. Maaari ba nating tukuyin ang laki ng array upang maging negatibo?
Hindi, hindi namin matukoy ang isang negatibong integer bilang laki ng isang array. Hindi magkakaroon ng error sa compile-time kung idedeklara namin. Sa runtime, gayunpaman, makakatagpo tayo ng NegativeArraySizeException.
10. Paano mo mahahanap ang nawawalang integer sa isang 1 hanggang 100-element array?
Ang kabuuan ng serye ay maaaring kalkulahin sa pamamagitan ng paglalapat ng sumusunod na function: n (n + 1) / 2
Tanging kung ang array ay walang anumang mga duplicate o mayroong higit sa isang integer na nawawala ang function na ito ay gagana. Kung ang isang array ay may mga duplicate na elemento, maaari mong ayusin ang array upang makita kung mayroong anumang mga elemento na katumbas.
11. Paano mo mahahanap ang index ng isang elemento sa isang array?
Maaaring matuklasan ang index ng elemento sa pamamagitan ng linear o binary na paghahanap. Hanggang sa mahanap nito ang tugma ng kinakailangang elemento, ang isang linear na function ng paghahanap ay umiikot sa bawat elemento sa isang array. Ibinabalik nito ang index kapag nahanap na nito ang tumutugmang elemento. Dahil dito, ang temporal complexity ng linear na paghahanap ay O. (n). Parehong isang pinagsunod-sunod at isang unsorted array ay maaaring gumamit ng linear na paghahanap.
Gamit ang isang binary na paghahanap, na patuloy na hinahati ang array sa kalahati hanggang ang median ng interval ay tumugma sa kinakailangang elemento at nagbibigay ng index, maaari mong makuha ang index ng elemento kung ang array ay pinagsunod-sunod. Dahil dito, ang temporal complexity ng binary search ay O. (log n).
12. Paano mo maaalis ang isang partikular na elemento mula sa isang array?
Dahil hindi mo basta-basta matatanggal ang mga elemento mula sa orihinal na hanay dahil ang mga ito ay mga nakapirming set na may tinukoy na laki, hinahanap ka ng tagapanayam na magmungkahi ng ibang diskarte at harapin ang problemang ibinabangon ng tanong. Ang pinakamahusay na paraan ng pagkilos ay ang gumawa ng bagong array upang matanggal ang isang elemento. Maaari mong i-duplicate ang mga elemento mula sa unang array sa array na ito at isama lang ang elementong gusto mong tanggalin.
Kasama sa isa pang diskarte ang paghahanap ng target na elemento sa array at pagkatapos ay binabaligtad ang pagkakasunud-sunod ng lahat ng item na nasa kanan ng target na elemento.
13. Paano mapapatunayan ang pagkakapantay-pantay ng dalawang array?
Dapat mo munang i-verify ang haba ng dalawang ibinigay na array. Ang mga katugmang item ng parehong array ay inihahambing kapag ang kanilang mga haba ay pantay. Ang dalawang array ay ituturing na pantay. kung ang bawat pares ng mga bahagi sa bawat sulat ay pantay. Ang diskarte na ito ay hindi pinapayuhan na suriin ang pagkakapantay-pantay ng dalawang array kung ang mga array ay malaki sa laki dahil ito ay aabutin ng maraming oras. Maaari mo ring gamitin ang equals() na pamamaraan na kasama sa klase ng Arrays, gayunpaman, kung hihilingin sa iyo ng tagapanayam na ihambing ang dalawang array nang hindi gumagamit ng mga built-in na pamamaraan, ang paraang ito ay magiging kapaki-pakinabang.
14. Kapag tinatalakay natin ang mga array, ano ang ibig mong sabihin sa mga pariralang "Dimensyon" at "Subscript"?
Ang "Dimensyon" ng isang array ay ang bilang ng mga indeks, o mga subscript, na kinakailangan upang matukoy ang bawat indibidwal na miyembro. Maaaring hindi malinaw ang mga subscript at dimensyon. Ang isang dimensyon ay isang paglalarawan ng hanay ng mga pinapahintulutang key, samantalang ang isang subscript ay isang numero. Mayroon lamang isang subscript na kinakailangan para sa bawat dimensyon ng array.
Halimbawa, ang array arr[10][5] ay may dalawang dimensyon. Sukat 10 sa isa at 5 sa isa. Upang matugunan ang mga bahagi nito, kailangan mo ng dalawang subscript. Parehong nasa pagitan ng 0 at 4; isa sa pagitan ng 0 at 9, kasama.
Mga Tanong sa Panayam sa Pag-coding
15. Maghanap ng isang pares sa isang array na may tinukoy na kabuuan
Halimbawa,
input:
- numero = [8, 7, 2, 5, 3, 1]
- target = 10
output:
- Natagpuan ang pares (8, 2)
- Or
- Natagpuan ang pares (7, 3)
input:
- numero = [5, 2, 6, 8, 1, 9]
- target = 12
output:
- Hindi nakita ang pares
16. Binary array sorting na may linear time
Pagbukud-bukurin ang isang binary array sa linear na oras at sa isang nakapirming lugar. Dapat ipakita muna ng output ang lahat ng mga zero, pagkatapos ay ang lahat.
Halimbawa,
- Input: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Output: { 0, 0, 0, 0, 1, 1, 1, 1 }
Ang isang tuwirang diskarte ay ang kalkulahin ang kabuuang bilang ng array na 0s, sabihin nating k, at pagkatapos ay punan ang unang k index sa array ng 0s at ang natitirang mga indeks ng 1. Bilang kahalili, maaari nating kalkulahin kung gaano karaming 1 ang kabuuang sa array k, punan ang huling k na mga indeks sa array ng 1, at iwanan ang natitirang mga indeks na puno ng 0.
Ang ibinigay na diskarte ay may O(n) pagiging kumplikado ng oras at hindi gumagamit ng karagdagang storage, kung saan ang n ay ang laki ng input.
17. Hanapin ang pinakamalaking two-int na produkto sa isang array.
Hanapin ang pinakamalaking produkto ng dalawang numero sa isang integer array.
Isipin ang array 10 3 5 6 2 bilang isang halimbawa. Ang (-10, -3) o (5, 6) na pares ay ang pinakamataas na produkto.
Ang pag-iisip tungkol sa bawat kumbinasyon ng elemento at alamin ang kanilang produkto ay isang hangal na diskarte. Kung ang produkto ng kasalukuyang pares ay mas malaki kaysa sa maximum na produkto na nakuha sa ngayon, i-update ang maximum na produkto. I-print ang mga bahagi ng huling produkto sa huli.
Ang solusyon sa itaas, kung saan ang n ay ang halaga ng input, ay may kumplikadong oras ng O(n2) at hindi na kumukuha ng anumang espasyo.
18. Paano ilipat ang lahat ng mga zero ng array hanggang sa dulo
Ilipat ang lahat ng mga zero sa isang integer array hanggang sa dulo. Dapat iwasan ng sagot ang paggamit ng pare-parehong espasyo at panatilihin ang kaugnay na pagkakasunud-sunod ng mga bahagi ng array.
Input: {1,2,3,0,8,0,4,7}
Ang output ay magiging {1,2,3,8,4,7,0,0}
Ilagay ang elemento sa sumusunod na available na posisyon sa array kung ang kasalukuyang elemento ay hindi zero. Punan ang lahat ng natitirang mga indeks ng 0 kapag naproseso na ang lahat ng mga item ng array.
Ang naunang solusyon ay may O(n) na pagiging kumplikado ng oras, kung saan ang n ay ang laki ng input.
19. Paano pag-uri-uriin ang isang array na may dalawang entry na inililipat sa isang operasyon.
Pagbukud-bukurin ang isang array sa linear na oras na binigyan ng dalawang pinagpalit na item at isang array na ang lahat ng mga elemento nito ay nakaayos sa pataas na pagkakasunud-sunod. Magkunwaring walang mga duplicate ang array.
Input:= [1,9,3,4,7,2] o [9,3,7,2,1,4] o [2,4,1,7,3,9]
Output: = [1,2,3,4,7,9]
Simula sa pangalawang elemento sa array, ang layunin ay ihambing ang bawat elemento sa hinalinhan nito. Ang posisyon ng hindi pagkakaunawaan ay iniimbak sa pamamagitan ng pagkuha ng dalawang pointer, x, at y.
I-update ang x sa index ng nakaraang elemento at y sa index ng kasalukuyang elemento kung mas malaki ang una kaysa sa huli. I-update ang y sa index ng kasalukuyang elemento kung lumalabas na ang nakaraang elemento ay mas malaki kaysa sa kasalukuyang elemento.
Panghuli, ilipat ang mga elemento sa mga index na x at y kapag natapos na namin ang pagproseso sa bawat katabing pares ng mga elemento.
Dahil sa ang katunayan na ang nabanggit na pamamaraan ay gumaganap lamang ng isang solong pag-scan ng input array ng laki n, ang pagiging kumplikado ng oras nito ay O(n). Walang karagdagang silid ang kinakailangan para sa solusyon.
20. Paano pagsamahin ang dalawang pinagsunod-sunod na array sa lugar.
Pagsamahin ang mga item ng array X[] at Y[]—dalawang pinagsunod-sunod na array na may sukat na m at n bawat isa—sa pamamagitan ng pananatili sa pinagsunod-sunod na pagkakasunud-sunod, iyon ay, sa pamamagitan ng pagpuno sa X[] ng unang m pinakamaliit na elemento at pagpuno sa Y[] ng natitirang mga elemento.
Kung ang isang elemento sa array X[] ay nasa tamang posisyon na (ibig sabihin, ang isa na pinakamaliit sa mga natitirang elemento), balewalain ito; kung hindi, palitan ito ng pinakamaliit na elemento, na nangyayari rin na unang miyembro ng Y[]. Upang mapanatili ang pinagsunod-sunod na pagkakasunud-sunod pagkatapos ng pagpapalit, ilipat ang elemento (ngayon sa Y[0]) sa tamang lokasyon nito sa Y[].
Ang laki ng unang array ay m at ang laki ng pangalawang array ay n, at ang pagiging kumplikado ng oras ay O(mn).
21. Paano muling ayusin ang isang hanay ng mga item sa alternating mataas at mababang posisyon?
Muling ayusin ang isang integer array upang ang bawat kasunod na miyembro ay mas malaki kaysa sa nauna at sumusunod na mga elemento. Ipagpalagay na ang array ay hindi kasama ang anumang mga duplicate na elemento.
Ang pag-uuri ng array o paggamit ng karagdagang espasyo ay hindi kailangan para sa isang epektibong diskarte. Ang plano ay, sa simula, ang pangalawang miyembro ng array at tumaas ng dalawa para sa bawat pag-ulit ng loop.
Palitan ang mga bahagi kung ang huling elemento ay lumampas sa una. Sa katulad na paraan, ilipat ang parehong mga item kung ang sumusunod na elemento ay mas malaki kaysa sa kasalukuyang elemento. Makukuha namin ang nais na array na sumusunod sa tinukoy na mga paghihigpit sa pagtatapos ng loop.
22. Paano palitan ang bawat elemento ng array nang hindi gumagamit ng division operator sa produkto ng bawat elemento sa array?
Nang hindi gumagamit ng division operator, palitan ang bawat elemento sa isang integer array ng produkto ng lahat ng iba pang elemento.
Sa linear na oras at pare-parehong espasyo, maaari naming gamitin ang recursion upang matugunan ang isyung ito. Ang paulit-ulit na pagkalkula ng mga produkto ng bawat elemento sa kanang subarray at pagpasa sa kaliwang produkto ng subarray bilang mga parameter ng function ay ang paniwala.
Ang pagiging kumplikado ng oras ay O(n).
23. Hanapin ang oddest elemento sa isang array sa logarithmic time
Dahil sa isang integer array kung saan ang lahat maliban sa isang miyembro ay may pantay na bilang ng mga pangyayari, ang problema ay upang matukoy kung ilang beses lumilitaw ang isang elementong ito. Hanapin ang kakaibang nagaganap na elemento sa logarithmic time at constant space kung ang parehong mga elemento ay nangyayari sa mga pares sa array at hindi kailanman maaaring magkaroon ng higit sa dalawang pagkakataon ng isang partikular na elemento sa isang row.
Ang operasyon ng XOR ay nagbibigay-daan sa amin upang malutas ang isyung ito sa linear na oras. Ang layunin ay i-XOR ang bawat elemento sa array. Tanging ang mga kakaibang nagaganap na elemento lamang ang natitira pagkatapos na kanselahin ng mga kahit na nagaganap na elemento ang isa't isa.
Ang problemang ito ay maaaring malutas sa oras ng O(log(n)).
24. Paano makukuha ang kasunod na mas malaking elemento para sa bawat elemento sa isang pabilog na hanay?
Ang susunod na mas malaking elemento para sa bawat elemento sa isang circular integer array ay dapat na matatagpuan. Ang unang mas malaking integer pagkatapos ng elementong x sa array ay ang kasunod na mas malaking elemento ng elementong iyon.
Mula kanan hanggang kaliwa, maaari kaming magpatakbo sa mga array item. Ang layunin ay i-loop para sa bawat elemento x hanggang sa alinman sa stack ay walang laman o mayroon kaming mas mataas na elemento sa ibabaw nito. Itakda ang susunod na mas malaking elemento ng x na lalabas sa ibabaw ng stack kapag nangyari ito.
25. Maghanap ng bilang ng pagbabaligtad ng array?
Hanapin ang kabuuang bilang ng mga inversion ng isang array. Ang isang pares I j) ay tinutukoy bilang isang inversion ng isang array A kung I j) at (A[i] > A[j]). Dapat nating bilangin ang bawat pares ng mga ito sa array.
Ang pagbibilang ng lahat ng mga miyembro ng array na mas kaunti kaysa dito sa kanan nito at pagdaragdag ng resulta sa output ay isang tapat na diskarte.
Ang solusyon na ito ay may O(n2) kumplikado, kung saan ang n ay ang laki ng input.
26. Ano ang Problema sa Rain Water Trapping?
Ang paghahanap ng pinakamaraming tubig na maaaring ma-trap sa isang partikular na hanay ng mga bar na may lapad na tig-iisang yunit ay kilala bilang isyu sa "pagbabalot ng ulan."
Ang layunin ay upang matukoy ang pinakamataas na bar na maaaring ilagay sa kaliwa at kanan ng bawat bar. Ang pinakamababa sa mga nangungunang bar sa kaliwa at kanan, mas mababa ang taas ng kasalukuyang bar, ay ang dami ng tubig na nakaimbak sa ibabaw ng bawat bar.
Konklusyon
Kung ikukumpara sa iba pang mga paksa ng istruktura ng data, mas simple ang mga array. Upang makasagot sa mga tanong sa panayam ng array, kailangan mong magkaroon ng pangunahing pag-unawa sa mga array.
Dapat mong suriin nang husto ang mga pundasyon ng mga array, kabilang ang mga operasyon ng array (mula sa pagdedeklara/paggawa ng array hanggang sa pag-access/pagbabago ng mga item ng array), pati na rin ang mga konsepto ng programming tulad ng mga loop, recursion, at pangunahing operator upang matagumpay na masagot ang mga tanong sa panayam ng array. Kilalanin ang isyu nang lubusan.
Dapat kang humingi ng paglilinaw kung mayroon kang anumang mga katanungan. Pag-isipang hatiin ang isyu sa mga mas mapapamahalaang bahagi. Tiyaking nasa isip mo ang algorithm bago mo simulan ang programming; isulat ito o ilarawan sa isang flowchart. pagkatapos ay simulan ang pagsulat ng code.
Mag-iwan ng Sagot