Orodha ya Yaliyomo[Ficha][Onyesha]
- 1. Je, unafafanuaje Array?
- 2. Safu Zenye Nguvu: Ni Nini? Ni nini kinachowatofautisha na Mifumo ya Msingi?
- 3. Je, safu na kamusi hutofautianaje kutoka kwa nyingine?
- 4. Orodhesha baadhi ya faida na hasara za safu.
- 5. Je, “Sparse Array” inarejelea nini?
- 6. Je, ni wakati gani unaweza kuchagua orodha iliyounganishwa juu ya safu?
- 7. Ni nini kinachotofautisha safu iliyoorodheshwa kutoka kwa safu shirikishi?
- 8. Je, Heap ina faida gani juu ya safu zilizopangwa?
- 9. Je, tunaweza kufafanua ukubwa wa safu kuwa hasi?
- 10. Je, unapataje nambari kamili iliyokosekana katika safu ya vipengele 1 hadi 100?
- 11. Je, unapataje faharasa ya kipengele katika safu?
- 12. Unawezaje kuondokana na kipengele maalum kutoka kwa safu?
- 13. Usawa wa safu mbili unawezaje kuthibitishwa?
- 14. Tunapozungumzia safu, unamaanisha nini kwa maneno “Dimension” na “Subscript”?
- Maswali ya Mahojiano ya Kuandika
- 15. Tafuta jozi katika safu ambayo ina jumla iliyobainishwa
- 16. Kupanga safu ya binary kwa wakati wa mstari
- 17. Pata bidhaa kubwa zaidi ya mbili-int katika safu.
- 18. Jinsi ya kuhamisha zero zote za safu hadi mwisho
- 19. Jinsi ya kupanga safu na maingizo mawili ambayo yanabadilishwa katika operesheni moja.
- 20. Jinsi ya kuchanganya safu mbili zilizopangwa mahali.
- 21. Jinsi ya kupanga upya safu ya vitu katika kubadilisha nafasi za juu na za chini?
- 22. Jinsi ya kubadilisha kila kipengele cha safu bila kutumia operator wa mgawanyiko na bidhaa ya kila kipengele katika safu?
- 23. Tafuta kipengele kisicho cha kawaida katika safu katika muda wa logarithmic
- 24. Jinsi ya kupata kipengele kikubwa kinachofuata kwa kila kipengele katika safu ya mviringo?
- 25. Tafuta hesabu ya ubadilishaji wa safu?
- 26. Tatizo la Kukamata Maji ya Mvua ni Gani?
- Hitimisho
Mahojiano ya kuweka msimbo yana mfululizo wa maswali ya DSA. Unapaswa kuwa na ujuzi wa kutumia safu ikiwa unajitayarisha kwa mahojiano yako ya kiufundi na FAANG au biashara nyingine ya teknolojia ya Tier-1.
Katika mahojiano mengi ya usimbaji, huja katika nafasi ya pili kwa Strings. Mkusanyiko ni mkusanyo wa vipengee vya data vinavyohusiana vilivyowekwa kwa ukaribu katika kumbukumbu.
Kwa kuwa zimeunganishwa kwa lugha zote za programu, kama vile C, C++, Java, Python, Perl, na Ruby, ziko kila mahali. Endelea kusoma kwa baadhi ya changamoto za mazoezi ya kuweka msimbo na maswali ya mahojiano na majibu kulingana na safu.
Python itatumika katika chapisho hili kushughulikia maswala ya usimbaji kwa sababu ni rahisi kutumia, kuelewa, na lazima tuifahamu wengi wetu.
Hebu kuanza.
1. Je, unafafanuaje Array?
- Kundi la aina za data zinazohusiana ni safu.
- Safu zimewekwa kila wakati.
- Aina sawa ya kutofautisha huhifadhiwa katika sehemu kadhaa na vitu vya safu.
- Aina za awali na marejeleo ya vitu vyote vinaendana nayo.
2. Safu Zenye Nguvu: Ni Nini? Ni nini kinachowatofautisha na Mifumo ya Msingi?
Uongezaji wa kiotomatiki unaotolewa na safu zinazobadilika (pia hujulikana kama mkusanyiko unaoweza kukua, mkusanyiko unaoweza kubadilishwa ukubwa, safu zinazoweza kubadilishwa, au Orodha za Array katika Java) ni faida kubwa.
Lazima kila wakati ujue ni vipengee vingapi ambavyo safu yako itahifadhi mapema kwa kuwa safu zina saizi isiyobadilika. Safu inayobadilika, kwa upande mwingine, hukua unapoongeza washiriki wa ziada kwake, kwa hivyo huhitaji kujua ukubwa wake kamili kabla.
3. Je, safu na kamusi hutofautianaje kutoka kwa nyingine?
Hii ni safu ya msingi ya maswali ya mahojiano ambayo huulizwa mara kwa mara. Zifuatazo ni tofauti kuu kati ya safu na kamusi:
- Safu ni orodha iliyoagizwa ya vitu sawa. Kamusi, kwa upande mwingine, ina jozi za thamani-msingi.
- Saizi za safu zinaweza kubadilika kwa nguvu. Mawazo hayo yenye nguvu hayapo katika kamusi.
- Kabla ya kutumia safu, saizi yake lazima ibainishwe. Ukubwa wa kamusi hauhitaji kubinafsishwa.
- Tumia taarifa ya Redim ikiwa ungependa kupanua saizi ya safu. Katika kamusi, kipengele kinaweza kuongezwa bila tamko.
4. Orodhesha baadhi ya faida na hasara za safu.
Manufaa:
- Mkusanyiko unaweza kupanga idadi ya vipengele kwa wakati mmoja.
- nyingine miundo ya data, kama vile rafu, foleni, orodha zilizounganishwa, miti, grafu, n.k., zinaweza kutekelezwa katika safu.
- Faharasa inaweza kutumika kufikia kipengele cha safu.
Hasara:
- Saizi ya safu lazima itangazwe mapema. Wakati wa tamko la safu, hatuwezi, hata hivyo, kufahamu saizi tunayohitaji.
- Muundo wa safu ni tuli. Inamaanisha kuwa saizi ya safu hurekebishwa kila wakati na kwamba mgao wa kumbukumbu hauwezi kuongezwa au kupunguzwa.
5. Je, “Sparse Array” inarejelea nini?
Safu ndogo ni safu ya data ambayo ina maingizo mengi yenye thamani sifuri. Kinyume chake, safu mnene ina wingi wa vipengee vyake vyenye thamani zisizo sifuri. Fahirisi za safu ndogo, ambazo hubadilisha nambari kuwa vitu, zinaweza kujumuisha mapungufu. Ikilinganishwa na HashMap, zinafaa zaidi kwa kumbukumbu.
6. Je, ni wakati gani unaweza kuchagua orodha iliyounganishwa juu ya safu?
Unapotumia orodha zilizounganishwa badala ya safu, zingatia:
- Huhitaji vipengele vyovyote ili kupata ufikiaji wa nasibu.
- Ambapo utabiri wa muda ni muhimu, unahitaji kuingizwa na kuondolewa mara kwa mara kutoka kwenye orodha.
- Ili kuunda foleni ya kipaumbele, unaweza kuhitaji kuweka vipengee katikati ya orodha.
- Hujui orodha itakuwa ya muda gani. Saizi ya mkusanyiko ikiongezeka, lazima utangaze tena na urudie kumbukumbu, kama tu kwa safu rahisi.
7. Ni nini kinachotofautisha safu iliyoorodheshwa kutoka kwa safu shirikishi?
Tofauti za msingi kati ya safu shirikishi na zilizoorodheshwa zimeorodheshwa katika jedwali lifuatalo.
- Jozi ya thamani-msingi katika muundo wa maandishi au nambari hutumiwa kupanga safu shirikishi. Vifunguo vya safu iliyoonyeshwa zote ni nambari, na kila ufunguo umeunganishwa kwa thamani tofauti.
- Katika safu ya ushirika, ufunguo unaweza kuwa kamba. Safu iliyoorodheshwa yenye funguo kamili kuanzia 0.
- Jedwali la safu wima mbili huiga tabia ya safu shirikishi. Sawa na jedwali la safu wima moja ni safu zenye faharasa.
- Ramani ni aina ya safu shirikishi. Safu ya faharasa si ramani.
8. Je, Heap ina faida gani juu ya safu zilizopangwa?
Ufanisi wa wakati wa kutumia Lundo juu ya Mikusanyiko Iliyopangwa ndio faida kuu. Ingawa shughuli za lundo ni za haraka, kupanga safu kunahitaji muda mwingi. Lundo linaweza kugundua kipengele kidogo zaidi kwa haraka zaidi kuliko safu inavyoweza kupangwa.
Mkusanyiko fulani wa nambari unaweza kupangwa katika mojawapo ya njia mbili kwa kutumia Mikusanyiko Iliyopangwa. Kwa upande mwingine, kwa mkusanyiko fulani wa nambari, kunaweza kuwa na zaidi ya lundo moja linalowezekana.
9. Je, tunaweza kufafanua ukubwa wa safu kuwa hasi?
Hapana, hatuwezi kufafanua nambari kamili hasi kuwa saizi ya safu. Hakutakuwa na hitilafu ya wakati wa kukusanya ikiwa tutatangaza. Wakati wa kukimbia, hata hivyo, tutakutana na NegativeArraySizeException.
10. Je, unapataje nambari kamili iliyokosekana katika safu ya vipengele 1 hadi 100?
Jumla ya safu inaweza kuhesabiwa kwa kutumia kazi ifuatayo: n (n + 1) / 2
Ikiwa tu safu haina nakala zozote au ina zaidi ya nambari moja inayokosekana, chaguo hili la kukokotoa litafanya kazi. Iwapo mkusanyiko una nakala za vipengee, unaweza kupanga safu ili kuona kama kuna vipengele vyovyote vinavyolingana.
11. Je, unapataje faharasa ya kipengele katika safu?
Faharasa ya kipengele inaweza kugunduliwa kupitia utafutaji wa mstari au wa binary. Hadi itakapopata kilinganifu cha kipengee kinachohitajika, kitendakazi cha utafutaji cha mstari hujikita juu ya kila kipengele katika safu. Hurudisha faharasa mara tu inapopata kipengee kinacholingana. Kwa hivyo, utata wa muda wa utafutaji wa mstari ni O. (n). Safu iliyopangwa na isiyopangwa inaweza kutumia utafutaji wa mstari.
Kwa kutumia utafutaji wa binary, ambao mara kwa mara hugawanya safu katika nusu hadi wastani wa muda ulingane na kipengele kinachohitajika na kutoa faharasa, unaweza kupata faharasa ya kipengele ikiwa safu imepangwa. Kwa hivyo, utata wa muda wa utafutaji wa binary ni O. (logi n).
12. Unawezaje kuondokana na kipengele maalum kutoka kwa safu?
Kwa kuwa huwezi kufuta vipengee kutoka kwa safu asili kwa kuwa ni seti zisizobadilika zenye ukubwa uliobainishwa, anayekuhoji anatafuta ili upendekeze mbinu tofauti na ushughulikie tatizo ambalo swali linazusha. Njia bora ya utekelezaji ni kutengeneza safu mpya ili kufuta kipengele. Unaweza kunakili vipengele kutoka kwa safu ya kwanza katika safu hii na kujumuisha tu kipengele unachotaka kufuta.
Mkakati mwingine unahusisha kutafuta kipengele lengwa katika safu na kisha kubadilisha mpangilio wa vitu vyote vilivyo upande wa kulia wa kipengele lengwa.
13. Usawa wa safu mbili unawezaje kuthibitishwa?
Lazima kwanza uthibitishe urefu wa safu mbili zilizotolewa. Vipengee vinavyolingana vya safu zote mbili hulinganishwa wakati urefu wao ni sawa. Safu mbili zitazingatiwa kuwa sawa. ikiwa kila jozi ya vipengele katika kila mawasiliano ni sawa. Mbinu hii haishauriwi kuangalia usawa wa safu mbili ikiwa safu ni kubwa kwa saizi kwani itachukua muda mwingi. Unaweza pia kutumia equals() njia iliyojumuishwa katika darasa la Arrays, hata hivyo, ikiwa mhojiwa atakuuliza ulinganishe safu mbili bila kutumia njia zilizojumuishwa, njia hii itakuwa muhimu.
14. Tunapozungumzia safu, unamaanisha nini kwa maneno “Dimension” na “Subscript”?
"Kipimo" cha safu ni idadi ya fahirisi, au usajili, unaohitajika ili kutambua kila mwanachama. Maandishi na vipimo vinaweza visiwe wazi. Kipimo ni maelezo ya anuwai ya funguo zinazoruhusiwa, ilhali usajili ni nambari. Kuna usajili mmoja tu unaohitajika kwa kila kipimo cha safu.
Kwa mfano, safu arr[10][5] ina vipimo viwili. Ukubwa 10 kwa moja na 5 kwa nyingine. Ili kushughulikia vipengele vyake, unahitaji usajili mbili. Wote ni kati ya 0 na 4; moja kati ya 0 na 9, ikijumuisha.
Maswali ya Mahojiano ya Kuandika
15. Tafuta jozi katika safu ambayo ina jumla iliyobainishwa
Kwa mfano,
Pembejeo:
- nambari = [8, 7, 2, 5, 3, 1]
- shabaha = 10
Matokeo:
- Jozi imepatikana (8, 2)
- Or
- Jozi imepatikana (7, 3)
Pembejeo:
- nambari = [5, 2, 6, 8, 1, 9]
- shabaha = 12
Matokeo:
- Jozi haijapatikana
16. Kupanga safu ya binary kwa wakati wa mstari
Panga safu ya jozi kwa wakati wa mstari na katika eneo lisilobadilika. Pato linapaswa kuonyesha sufuri zote kwanza, kisha zote.
Kwa mfano,
- Ingizo: {1, 0, 1, 0, 1, 0, 0, 1}
- Pato: {0, 0, 0, 0, 1, 1, 1, 1}
Mbinu ya moja kwa moja itakuwa kukokotoa jumla ya idadi ya safu ya sekunde 0, sema k, na kisha ujaze fahirisi za k za kwanza katika safu na 0 na fahirisi zilizobaki na 1. Kama mbadala, tunaweza kuhesabu ni ngapi 1 ni jumla katika safu k, jaza fahirisi za k mwisho katika safu na 1, na uache fahirisi zingine zikijazwa na 0.
Mbinu iliyotolewa ina ugumu wa wakati wa O(n) na haitumii hifadhi ya ziada, ambapo n ni saizi ya ingizo.
17. Pata bidhaa kubwa zaidi ya mbili-int katika safu.
Pata bidhaa kubwa zaidi ya nambari mbili katika safu kamili.
Fikiria juu ya safu 10 3 5 6 2 kama mfano. Jozi ya (-10, -3) au (5, 6) ndiyo bidhaa ya juu zaidi.
Kufikiria juu ya kila mchanganyiko wa vitu na kujua bidhaa zao ni njia ya kijinga. Ikiwa bidhaa ya jozi ya sasa ni kubwa kuliko kiwango cha juu zaidi cha bidhaa iliyopatikana kufikia sasa, sasisha bidhaa ya juu zaidi. Chapisha vipengele vya bidhaa ya mwisho mwisho.
Suluhisho hapo juu, ambapo n ni kiasi cha ingizo, lina ugumu wa wakati wa O(n2) na hauchukui nafasi zaidi.
18. Jinsi ya kuhamisha zero zote za safu hadi mwisho
Sogeza sufuri zote katika safu kamili hadi mwisho. Jibu linapaswa kuzuia kutumia nafasi ya mara kwa mara na kuhifadhi mpangilio wa jamaa wa vifaa vya safu.
Ingizo: {1,2,3,0,8,0,4,7}
Pato litakuwa {1,2,3,8,4,7,0,0}
Weka kipengele katika nafasi ifuatayo inayopatikana katika safu ikiwa kipengele cha sasa sio sifuri. Jaza fahirisi zote zilizosalia na 0 mara tu vitu vya safu vimechakatwa.
Suluhisho lililotangulia lina utata wa wakati wa O(n), ambapo n ni saizi ya ingizo.
19. Jinsi ya kupanga safu na maingizo mawili ambayo yanabadilishwa katika operesheni moja.
Panga safu katika muda wa mstari uliopewa vipengee viwili vilivyobadilishwa na safu yenye vipengele vyake vyote vilivyopangwa kwa mpangilio wa kupanda. Fanya kuwa safu haina nakala.
Ingizo:= [1,9,3,4,7,2] au [9,3,7,2,1,4] au [2,4,1,7,3,9]
Pato: = [1,2,3,4,7,9]
Kuanzia na kipengele cha pili katika safu, lengo ni kulinganisha kila kipengele na mtangulizi wake. Nafasi ya mzozo huhifadhiwa kwa kuchukua viashiria viwili, x, na y.
Sasisha x kwa faharasa ya kipengele kilichotangulia na y kwenye faharasa ya kipengele cha sasa ikiwa cha kwanza ni kikubwa kuliko cha mwisho. Sasisha y kwa faharasa ya kipengee cha sasa ikiwa itabadilika kuwa kipengele cha awali ni kikubwa kuliko kipengele cha sasa.
Hatimaye, badilisha vipengele katika faharasa x na y mara tu tunapomaliza kuchakata kila jozi ya vipengele vilivyo karibu.
Kwa sababu ya ukweli kwamba njia iliyotajwa hapo juu hufanya skanisho moja tu ya safu ya pembejeo ya saizi n, ugumu wake wa wakati ni O(n). Hakuna chumba cha ziada kinachohitajika kwa suluhisho.
20. Jinsi ya kuchanganya safu mbili zilizopangwa mahali.
Unganisha vipengee vya safu X[] na Y[]—safu mbili zilizopangwa za saizi m na n kila moja—kwa kuhifadhi mpangilio uliopangwa, yaani, kwa kujaza X[] na vipengee vya kwanza m vidogo zaidi na kujaza Y[] na vipengele vilivyobaki.
Ikiwa kipengele katika safu X[] tayari kiko katika nafasi sahihi (yaani, kile ambacho ni kidogo zaidi kati ya vipengele vilivyosalia), kipuuze; vinginevyo, ibadilishe na kipengele kidogo zaidi, ambacho pia kinatokea kuwa mwanachama wa kwanza wa Y[]. Ili kuhifadhi mpangilio uliopangwa baada ya kubadilishana, hamisha kipengele (sasa kiko Y[0]) hadi mahali pake panapofaa katika Y[].
Saizi ya safu ya kwanza ni m na saizi ya safu ya pili ni n, na ugumu wa wakati ni O(mn).
21. Jinsi ya kupanga upya safu ya vitu katika kubadilisha nafasi za juu na za chini?
Panga upya safu kamili ili kila mwanachama anayefuata awe mkubwa kuliko vipengele vilivyotangulia na vifuatavyo. Chukulia kuwa safu haijumuishi vipengele vyovyote vinavyorudiwa.
Kupanga safu au kutumia nafasi ya ziada sio lazima kwa mbinu bora. Mpango ni, kwa kuanzia, mwanachama wa pili wa safu na kwenda juu kwa mbili kwa kila iteration ya kitanzi.
Badilisha vipengele ikiwa kipengele cha mwisho kinazidi cha kwanza. Kwa mshipa sawa, badilisha vitu vyote viwili ikiwa kipengele kifuatacho ni kikubwa kuliko kipengele cha sasa. Tutapata safu inayotaka ambayo inaambatana na vizuizi vilivyoainishwa katika hitimisho la kitanzi.
22. Jinsi ya kubadilisha kila kipengele cha safu bila kutumia operator wa mgawanyiko na bidhaa ya kila kipengele katika safu?
Bila kutumia kiendesha mgawanyiko, badilisha kila kipengele katika safu kamili na bidhaa ya vipengele vingine vyote.
Katika muda wa mstari na nafasi isiyobadilika, tunaweza kutumia kujirudia kushughulikia suala hili. Kuhesabu kwa kujirudia bidhaa za kila kipengele katika safu ndogo ya kulia na kupitisha bidhaa ya safu ndogo ya kushoto kama vigezo vya utendaji ndilo wazo.
Utata wa wakati ni O(n).
23. Tafuta kipengele kisicho cha kawaida katika safu katika muda wa logarithmic
Kwa kuzingatia mkusanyiko kamili ambapo wanachama wote isipokuwa mmoja wana idadi hata ya matukio, tatizo ni kubainisha ni mara ngapi kipengele hiki kimoja kinaonekana. Tafuta kipengele kinachotokea katika muda wa logarithmic na nafasi isiyobadilika ikiwa vipengele sawa vinatokea kwa jozi katika safu na kamwe hakuwezi kuwa na zaidi ya matukio mawili ya kipengele fulani kwa mfululizo.
Uendeshaji wa XOR hutuwezesha kutatua suala hili kwa wakati wa mstari. Lengo ni XOR kila kipengele katika safu. Vipengee tu vinavyotokea visivyo vya kawaida husalia baada ya hata vipengele vinavyotokea kufuta kila kimoja.
Shida hii inaweza kutatuliwa kwa wakati wa O(logi(n)).
24. Jinsi ya kupata kipengele kikubwa kinachofuata kwa kila kipengele katika safu ya mviringo?
Kipengele kikubwa kinachofuata kwa kila kipengele katika mkusanyiko kamili wa duara kinapaswa kupatikana. Nambari kamili ya kwanza baada ya kipengele x katika safu ni kipengele kikuu kinachofuata cha kipengele hicho.
Kutoka kulia kwenda kushoto, tunaweza kufanya kazi kwenye vitu vya safu. Lengo ni kuzunguka kwa kila kipengele x hadi rafu iwe tupu au tuwe na kipengele cha juu juu yake. Weka kipengee kikubwa kinachofuata cha x ili kionekane juu ya rafu kitakapotokea.
25. Tafuta hesabu ya ubadilishaji wa safu?
Pata jumla ya idadi ya ubadilishaji wa safu. Jozi I j) inarejelewa kuwa ni ubadilishaji wa safu A ikiwa mimi j) na (A[i] > A[j]). Lazima tuhesabu kila jozi ya hizi katika safu.
Kuhesabu washiriki wote wa safu ambao ni wachache kuliko hiyo kulia kwake na kuongeza matokeo kwenye matokeo ni mbinu iliyonyooka.
Suluhisho hili lina utata wa O(n2), ambapo n ni saizi ya pembejeo.
26. Tatizo la Kukamata Maji ya Mvua ni Gani?
Kupata maji mengi zaidi ambayo yanaweza kunaswa katika seti fulani ya baa zenye upana wa kitengo kimoja kila moja inajulikana kama suala la "kunasa mvua".
Lengo ni kuamua upau wa juu zaidi ambao unaweza kuwekwa upande wa kushoto na kulia wa kila upau. Kiwango cha chini cha baa zinazoongoza kushoto na kulia, chini ya urefu wa bar ya sasa, ni kiasi cha maji ambacho huhifadhiwa juu ya kila bar.
Hitimisho
Ikilinganishwa na mada zingine za muundo wa data, safu ni rahisi zaidi. Ili kujibu maswali ya mahojiano, unahitaji kuwa na uelewa wa kimsingi wa safu.
Unapaswa kukagua kwa kina misingi ya safu, ikijumuisha utendakazi wa safu (kutoka kutangaza/kuunda safu hadi kufikia/kurekebisha vipengee vya safu), pamoja na dhana za upangaji kama vile vitanzi, urejeshaji, na waendeshaji msingi ili kujibu maswali ya usaili kwa ufanisi. Tambua suala hilo kabisa.
Unapaswa kutafuta ufafanuzi ikiwa una maswali yoyote. Fikiria kuhusu kugawanya suala hilo katika sehemu zinazoweza kudhibitiwa zaidi. Hakikisha kuwa una algorithm akilini kabla ya kuanza kupanga programu; iandike au ione kwa taswira katika mtiririko wa chati. kisha uanze kuandika msimbo.
Acha Reply