Mundarija[Yashirish][Show]
- 1. Massivni qanday aniqlash mumkin?
- 2. Dinamik massivlar: ular nima? Ularni asosiy massivlardan nimasi bilan ajratib turadi?
- 3. Massiv va lug‘at bir-biridan qanday farqlanadi?
- 4. Massivlarning afzalliklari va kamchiliklarini sanab bering.
- 5. “Sirak massiv” nimani anglatadi?
- 6. Qachon massiv o‘rniga bog‘langan ro‘yxatni tanlagan bo‘lardingiz?
- 7. Indekslangan massiv assotsiativ massivdan nimasi bilan farqlanadi?
- 8. Heapning tartiblangan massivlarga nisbatan qanday afzalliklari bor?
- 9. Massiv hajmini manfiy deb belgilay olamizmi?
- 10. 1 dan 100 tagacha elementli massivda etishmayotgan butun sonni qanday topish mumkin?
- 11. Massivdagi element indeksi qanday topiladi?
- 12. Massivdan ma'lum bir elementdan qanday qutulish mumkin?
- 13. Ikki massivning tengligini qanday tekshirish mumkin?
- 14. Massivlarni muhokama qilganimizda, “O‘lcham” va “Subscript” iboralari deganda nimani tushunasiz?
- Intervyu savollarini kodlash
- 15. Belgilangan yig'indiga ega bo'lgan massivdagi juftlikni qidiring
- 16. Ikkilik massivlarni chiziqli vaqt bilan saralash
- 17. Massivdagi eng katta ikki int hosilani toping.
- 18. Massivning barcha nollarini oxirigacha qanday siljitish mumkin
- 19. Bir amalda almashtiriladigan ikkita yozuvli massiv qanday tartiblanadi.
- 20. Ikki tartiblangan massivni joyida qanday birlashtirish mumkin.
- 21. Obyektlar massivini yuqori va past o‘rinlarni almashishda qanday tartiblash mumkin?
- 22. Massivning har bir elementini massivdagi har bir elementning ko‘paytmasi bilan bo‘lish operatoridan foydalanmasdan qanday qilib almashtirish mumkin?
- 23. Logarifmik vaqtda massivdagi eng toq elementni toping
- 24. Doiraviy massivdagi har bir element uchun keyingi kattaroq element qanday olinadi?
- 25. Massivning inversiya sonini toping?
- 26. Yomg'ir suvini ushlab qolish muammosi nima?
- Xulosa
Kodlash intervyularida bir qator DSA savollari mavjud. Agar siz FAANG yoki boshqa 1-darajali texnologik biznes bilan bo'lajak texnologik intervyuga tayyorlanayotgan bo'lsangiz, massivlar bo'yicha malakali bo'lishingiz kerak.
Ko'pgina kodlash intervyularida u Stringsdan keyin ikkinchi o'rinda turadi. Massiv - bu xotirada bir-biriga yaqin joylashgan o'zaro bog'liq ma'lumotlar elementlari guruhi.
Ular C, C++, Java, Python, Perl va Ruby kabi barcha dasturlash tillariga ulanganligi sababli ular hamma joyda mavjud. Ba'zi amaliyot kodlash muammolari va massivlarga asoslangan intervyu savollari va javoblari uchun o'qishni davom ettiring.
Python ushbu postda kodlash muammolarini hal qilish uchun ishlatiladi, chunki uni ishlatish, tushunish oson va ko'pchiligimiz uchun tanish bo'lishi kerak.
Keling, boshlaymiz.
1. Massivni qanday aniqlash mumkin?
- O'zaro bog'liq ma'lumotlar turlari guruhi massivdir.
- Massivlar har doim aniqlangan.
- Xuddi shu turdagi o'zgaruvchilar massiv ob'ektlari tomonidan bir nechta joyda saqlanadi.
- Ibtidoiy turlar va ob'ekt havolalari unga mos keladi.
2. Dinamik massivlar: ular nima? Ularni asosiy massivlardan nimasi bilan ajratib turadi?
Dinamik massivlar (shuningdek, oʻstiriladigan massivlar, oʻlchami oʻzgartiriladigan massivlar, oʻzgaruvchan massivlar yoki Java-da ArrayLists deb ataladi) avtomatik masshtablash muhim afzallik hisoblanadi.
Siz har doim massivingiz qancha elementni saqlashini oldindan bilishingiz kerak, chunki massivlar qat'iy o'lchamga ega. Dinamik massiv esa unga qoʻshimcha aʼzolar qoʻshganda oʻsib boradi, shuning uchun uning aniq hajmini oldindan bilish shart emas.
3. Massiv va lug‘at bir-biridan qanday farqlanadi?
Bu muntazam ravishda so'raladigan intervyu savollarining asoslari to'plamidir. Quyida massivlar va lug'atlar o'rtasidagi asosiy farqlar keltirilgan:
- Massiv - bu o'xshash elementlarning tartiblangan ro'yxati. Lug'atda esa kalit-qiymat juftliklari mavjud.
- Massiv o'lchamlari dinamik ravishda o'zgarishi mumkin. Bunday dinamik g‘oyalar lug‘atlarda yo‘q.
- Massivni ishlatishdan oldin uning o'lchamini belgilash kerak. Lug'at o'lchamlarini moslashtirish shart emas.
- Agar siz massiv hajmini kengaytirmoqchi bo'lsangiz, Redim iborasidan foydalaning. Lug'atlarda element deklaratsiyasiz qo'shilishi mumkin.
4. Massivlarning afzalliklari va kamchiliklarini sanab bering.
afzalliklari:
- Massivlar bir vaqtning o'zida bir nechta elementlarni saralashi mumkin.
- boshqa ma'lumotlar tuzilmalaristeklar, navbatlar, bog'langan ro'yxatlar, daraxtlar, grafiklar va boshqalar kabi massivda amalga oshirilishi mumkin.
- Indeks massiv elementiga erishish uchun ishlatilishi mumkin.
Kamchiliklari:
- Massivning o'lchami oldindan e'lon qilinishi kerak. Massiv deklaratsiyasida biz talab qilayotgan hajmni bilmasligimiz mumkin.
- Massivning tuzilishi statikdir. Bu massiv o'lchami har doim o'zgarmasligini va xotira taqsimotini oshirish yoki kamaytirish mumkin emasligini anglatadi.
5. “Sirak massiv” nimani anglatadi?
Siyrak massiv - bu nol qiymatga ega bo'lgan juda ko'p yozuvlarga ega bo'lgan ma'lumotlar massivi. Bundan farqli o'laroq, zich massiv o'z elementlarining ko'p qismini nolga teng bo'lmagan qiymatlarga ega. Raqamlarni ob'ektlarga aylantiruvchi siyrak massiv indekslari bo'shliqlarni o'z ichiga olishi mumkin. HashMap bilan solishtirganda, ular xotiradan tejamkorroq.
6. Qachon massiv o‘rniga bog‘langan ro‘yxatni tanlagan bo‘lardingiz?
Massivlar o'rniga bog'langan ro'yxatlardan foydalanilganda, quyidagilarni hisobga oling:
- Tasodifiy kirish uchun sizga hech qanday element kerak emas.
- Vaqtinchalik bashorat qilish muhim bo'lgan joyda, ro'yxatdan doimiy ravishda qo'shish va olib tashlash kerak bo'ladi.
- Ustuvor navbat yaratish uchun elementlarni roʻyxatning oʻrtasiga joylashtirishingiz kerak boʻlishi mumkin.
- Ro'yxat qancha davom etishini bilmaysiz. Agar massiv o'lchami oshsa, oddiy massivlar kabi xotirani qayta e'lon qilish va takrorlash kerak.
7. Indekslangan massiv assotsiativ massivdan nimasi bilan farqlanadi?
Assotsiativ va indekslangan massivlar orasidagi asosiy farqlar quyidagi jadvalda keltirilgan.
- Assotsiativ massivni saralash uchun matn yoki raqamli formatdagi kalit-qiymat juftligidan foydalaniladi. Indekslangan massivning kalitlari hammasi raqamli bo'lib, har bir kalit alohida qiymatga ulangan.
- Assotsiativ massivda kalit satr bo'lishi mumkin. 0 dan boshlanadigan butun sonli kalitlarga ega indekslangan massiv.
- Ikki ustunli jadval assotsiativ massivning harakatini taqlid qiladi. Indekslangan massivlar bitta ustunli jadvalga o'xshaydi.
- Xaritalar assotsiativ massiv turidir. Indeks massivi xarita emas.
8. Heapning tartiblangan massivlarga nisbatan qanday afzalliklari bor?
Saralangan massivlar ustida yig'ishdan foydalanishning vaqt samaradorligi asosiy afzallikdir. Uyum operatsiyalari tezroq bo'lsa-da, massivni saralash ko'p vaqtni talab qiladi. Uyum eng kichik elementni massivni tartiblashdan ko'ra tezroq topishi mumkin.
Berilgan raqamlar to'plamini Saralangan massivlar yordamida ikkita usuldan birida joylashtirish mumkin. Boshqa tomondan, berilgan raqamlar to'plami uchun bir nechta potentsial to'p bo'lishi mumkin.
9. Massiv hajmini manfiy deb belgilay olamizmi?
Yo'q, biz manfiy butun sonni massiv o'lchami sifatida belgilay olmaymiz. Agar biz e'lon qilsak, kompilyatsiya vaqtida xato bo'lmaydi. Ishlash vaqtida biz NegativeArraySizeExceptionga duch kelamiz.
10. 1 dan 100 tagacha elementli massivda etishmayotgan butun sonni qanday topish mumkin?
Seriyalarning umumiy miqdorini quyidagi funktsiyani qo'llash orqali hisoblash mumkin: n (n + 1) / 2
Agar massivda dublikatlar bo'lmasa yoki bir nechta tamsayılar etishmayotgan bo'lsa, bu funksiya ishlaydi. Massiv ikki nusxadagi elementlarga ega bo'ladimi, siz massivni ekvivalent elementlar mavjudligini ko'rish uchun saralashingiz mumkin.
11. Massivdagi element indeksi qanday topiladi?
Element indeksini chiziqli yoki ikkilik qidiruv orqali topish mumkin. Kerakli elementning mosligini topmaguncha, chiziqli qidiruv funksiyasi massivdagi har bir element ustida aylanadi. U mos keladigan elementni topgandan so'ng indeksni qaytaradi. Binobarin, chiziqli qidiruvning vaqtinchalik murakkabligi O. (n). Saralangan va tartiblanmagan massiv chiziqli qidiruvdan foydalanishi mumkin.
Intervalning medianasi kerakli elementga to'g'ri kelguncha va indeksni ta'minlamaguncha massivni doimiy ravishda ikkiga bo'ladigan ikkilik qidiruvdan foydalanib, agar massiv tartiblangan bo'lsa, element indeksini olishingiz mumkin. Binobarin, ikkilik qidiruvning vaqtinchalik murakkabligi O. (log n).
12. Massivdan ma'lum bir elementdan qanday qutulish mumkin?
Asl massivdagi elementlarni oddiygina oʻchirib tashlab boʻlmaydi, chunki ular belgilangan oʻlchamga ega boʻlgan toʻplamlardir, intervyu oluvchi sizdan boshqa yondashuvni taklif qilishingizni va savol tugʻdiradigan muammoni hal qilishingizni soʻraydi. Elementni o'chirish uchun yangi massiv yaratish eng yaxshi harakat yo'nalishidir. Siz ushbu massivdagi birinchi massivdagi elementlarni ko'paytirishingiz va faqat o'chirmoqchi bo'lgan elementni kiritishingiz mumkin.
Boshqa strategiya massivdagi maqsadli elementni topishni va keyin maqsad elementning o'ng tomonidagi barcha elementlarning tartibini o'zgartirishni o'z ichiga oladi.
13. Ikki massivning tengligini qanday tekshirish mumkin?
Avval taqdim etilgan ikkita massivning uzunligini tekshirishingiz kerak. Ikkala massivning mos keladigan elementlari ularning uzunligi teng bo'lganda solishtiriladi. Ikki massiv teng deb hisoblanadi. agar har bir yozishmadagi komponentlar juftligi teng bo'lsa. Agar massivlar katta bo'lsa, ikkita massivning tengligini tekshirish tavsiya etilmaydi, chunki bu juda ko'p vaqtni oladi. Massivlar sinfiga kiritilgan teng() usulidan ham foydalanishingiz mumkin, ammo agar suhbatdosh sizdan o'rnatilgan usullardan foydalanmasdan ikkita massivni solishtirishni so'rasa, bu usul foydali bo'ladi.
14. Massivlarni muhokama qilganimizda, “O‘lcham” va “Subscript” iboralari deganda nimani tushunasiz?
Massivning "o'lchami" - har bir alohida a'zoni identifikatsiyalash uchun zarur bo'lgan indekslar yoki pastki belgilar soni. Subscripts va o'lchamlar noaniq bo'lishi mumkin. O'lchov - bu ruxsat etilgan kalitlar diapazoni tavsifi, pastki belgisi esa raqam. Har bir massiv o'lchami uchun faqat bitta subscript talab qilinadi.
Masalan, arr[10][5] massivi ikkita o'lchovga ega. Birida 10, ikkinchisida 5 o'lcham. Uning tarkibiy qismlariga murojaat qilish uchun sizga ikkita subscript kerak bo'ladi. Ikkalasi ham 0 dan 4 gacha; biri 0 va 9 orasida, shu jumladan.
Intervyu savollarini kodlash
15. Belgilangan yig'indiga ega bo'lgan massivdagi juftlikni qidiring
Masalan,
Kiritish:
- raqamlar = [8, 7, 2, 5, 3, 1]
- maqsad = 10
chiqish:
- Juft topildi (8, 2)
- Or
- Juft topildi (7, 3)
Kiritish:
- raqamlar = [5, 2, 6, 8, 1, 9]
- maqsad = 12
chiqish:
- Juft topilmadi
16. Ikkilik massivlarni chiziqli vaqt bilan saralash
Ikkilik massivni chiziqli vaqtda va belgilangan maydonda tartiblang. Chiqish birinchi navbatda barcha nollarni, keyin esa barchani ko'rsatishi kerak.
Masalan,
- Kirish: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Chiqish: { 0, 0, 0, 0, 1, 1, 1, 1 }
To'g'ridan-to'g'ri yondashuv massivning umumiy 0 sonini hisoblab chiqish, deylik k, so'ngra massivdagi birinchi k indeksni 0 bilan, qolgan indekslarni esa 1 bilan to'ldirishdir. massiv k, massivdagi oxirgi k indekslarni 1 bilan to'ldiring va qolgan indekslarni 1 bilan to'ldiring.
Berilgan yondashuv O(n) vaqt murakkabligiga ega va qo'shimcha xotiradan foydalanmaydi, bu erda n - kirish hajmi.
17. Massivdagi eng katta ikki int hosilani toping.
Butun massivdagi ikkita sonning eng katta mahsulotini toping.
Misol tariqasida 10 3 5 6 2 massivini tasavvur qiling. (-10, -3) yoki (5, 6) juftligi eng yuqori mahsulot hisoblanadi.
Har bir element kombinatsiyasi haqida o'ylash va ularning mahsulotini aniqlash ahmoqona yondashuvdir. Agar joriy juftlik mahsuloti shu paytgacha olingan maksimal mahsulotdan katta bo'lsa, maksimal mahsulotni yangilang. Yakuniy mahsulotning tarkibiy qismlarini oxirgi marta chop eting.
Yuqoridagi yechim, bu erda n - kirish miqdori, O(n2) vaqt murakkabligiga ega va boshqa joy egallamaydi.
18. Massivning barcha nollarini oxirigacha qanday siljitish mumkin
Butun sonlar massividagi barcha nollarni oxirigacha siljiting. Javob doimiy bo'sh joydan foydalanishdan qochishi va massiv komponentlarining nisbiy tartibini saqlashi kerak.
Kirish: {1,2,3,0,8,0,4,7}
Chiqish: {1,2,3,8,4,7,0,0}
Agar joriy element nolga teng bo'lmasa, elementni massivning quyidagi mavjud joyiga qo'ying. Massivning barcha elementlari qayta ishlanganidan keyin qolgan barcha indekslarni 0 bilan to'ldiring.
Oldingi yechim O (n) vaqt murakkabligiga ega, bu erda n - kirish hajmi.
19. Bir amalda almashtiriladigan ikkita yozuvli massiv qanday tartiblanadi.
Ikki almashtirilgan element va uning barcha elementlari o'sish tartibida joylashtirilgan massivni chiziqli vaqt bo'yicha tartiblang. Massivda dublikatlar yo'qligini ko'rsating.
Kirish:= [1,9,3,4,7,2] yoki [9,3,7,2,1,4] yoki [2,4,1,7,3,9]
Chiqish: = [1,2,3,4,7,9]
Massivdagi ikkinchi elementdan boshlab, maqsad har bir elementni o'zidan oldingi bilan solishtirishdir. Bahsning pozitsiyasi ikkita ko'rsatkich, x va y olish orqali saqlanadi.
Agar birinchi element ikkinchisidan katta bo'lsa, x ni oldingi element indeksiga va y ni joriy element indeksiga yangilang. Agar oldingi element joriy elementdan kattaroq ekanligi aniqlansa, y ni joriy element indeksiga yangilang.
Nihoyat, har bir qo'shni element juftligini qayta ishlashni tugatganimizdan so'ng, x va y indekslaridagi elementlarni almashtiring.
Yuqorida aytib o'tilgan usul n o'lchamdagi kirish massivini faqat bitta skanerlashni amalga oshirishi sababli, uning vaqt murakkabligi O(n). Yechim uchun qo'shimcha xona kerak emas.
20. Ikki tartiblangan massivni joyida qanday birlashtirish mumkin.
X[] va Y[] massivlari elementlarini — har biri m va n oʻlchamdagi ikkita tartiblangan massivlarni — tartiblangan tartibni saqlab, yaʼni X[] ni birinchi m ta eng kichik element bilan va Y[] ni toʻldirish orqali birlashtiring. qolgan elementlar.
Agar X[] massividagi element allaqachon to'g'ri holatda bo'lsa (ya'ni, qolgan elementlar orasida eng kichigi bo'lgan), unga e'tibor bermang; aks holda uni eng kichik element bilan almashtiring, u ham Y[] ning birinchi a'zosi bo'ladi. Almashtirilgandan so'ng tartiblangan tartibni saqlab qolish uchun elementni (hozir Y[0] da) Y[] dagi to'g'ri joyiga o'tkazing.
Birinchi massivning o‘lchami m, ikkinchi massivning o‘lchami esa n, vaqt murakkabligi esa O(mn).
21. Obyektlar massivini yuqori va past o‘rinlarni almashishda qanday tartiblash mumkin?
Butun sonli massivni har bir keyingi a'zo oldingi va keyingi elementlardan kattaroq bo'lishi uchun o'zgartiring. Massiv ikki nusxadagi elementlarni o'z ichiga olmaydi, deb faraz qiling.
Massivni saralash yoki qo'shimcha joydan foydalanish samarali yondashuv uchun shart emas. Reja, birinchi navbatda, massivning ikkinchi a'zosi va har bir tsikl iteratsiyasi uchun ikkiga ko'tariladi.
Agar oxirgi element birinchisidan oshsa, komponentlarni almashtiring. Xuddi shunday tarzda, agar quyidagi element joriy elementdan kattaroq bo'lsa, ikkala elementni almashtiring. Biz tsikl oxirida ko'rsatilgan cheklovlarga mos keladigan kerakli massivni olamiz.
22. Massivning har bir elementini massivdagi har bir elementning ko‘paytmasi bilan bo‘lish operatoridan foydalanmasdan qanday qilib almashtirish mumkin?
Bo'lish operatoridan foydalanmasdan, butun sonli massivdagi har bir elementni boshqa barcha elementlarning mahsuloti bilan almashtiring.
Chiziqli vaqt va doimiy fazoda biz ushbu muammoni hal qilish uchun rekursiyadan foydalanishimiz mumkin. O'ng pastki qatordagi har bir elementning mahsulotini rekursiv hisoblash va chap pastki qator mahsulotini funktsiya parametrlari sifatida o'tkazish tushunchasidir.
Vaqt murakkabligi O(n) ga teng.
23. Logarifmik vaqtda massivdagi eng toq elementni toping
Bitta a'zodan tashqari barcha ishtirokchilar juft sonlarga ega bo'lgan butun sonli massivni hisobga olsak, muammo bu element necha marta paydo bo'lishini aniqlashdir. Agar massivda bir xil elementlar juft bo‘lib uchrasa va hech qachon bir qatorda berilgan elementning ikkitadan ortiq nusxasi bo‘lmasa, logarifmik vaqt va doimiy fazoda toq uchraydigan elementni toping.
XOR operatsiyasi bizga ushbu muammoni chiziqli vaqtda hal qilish imkonini beradi. Maqsad massivdagi har bir elementni XOR qilishdir. Juft bo'lgan elementlar bir-birini bekor qilgandan so'ng faqat toq elementlar qoladi.
Bu muammoni hatto O(log(n)) vaqtida hal qilish mumkin.
24. Doiraviy massivdagi har bir element uchun keyingi kattaroq element qanday olinadi?
Dumaloq butun qatordagi har bir element uchun keyingi kattaroq element joylashgan bo'lishi kerak. Massivdagi x elementdan keyingi birinchi kattaroq butun son shu elementning keyingi katta elementidir.
O'ngdan chapga biz massiv elementlari bilan ishlashimiz mumkin. Maqsad har bir x elementi uchun stek bo'sh bo'lguncha yoki uning ustida yuqoriroq element bo'lgunga qadar aylanishdir. X ning keyingi kattaroq elementi paydo bo'lganda stek tepasida paydo bo'ladigan qilib o'rnating.
25. Massivning inversiya sonini toping?
Massiv inversiyalarining umumiy sonini toping. Agar I j) va (A[i] > A[j]) boʻlsa, I j) jufti A massivning inversiyasi deb ataladi. Biz massivdagi bularning har bir juftini sanashimiz kerak.
Massivning o'ng tomonida kamroq bo'lgan barcha a'zolarni sanash va natijani natijaga qo'shish oddiy yondashuvdir.
Bu yechim O(n2) murakkablikka ega, bu yerda n - kirish hajmi.
26. Yomg'ir suvini ushlab qolish muammosi nima?
Har birining kengligi bir birlik bo'lgan ma'lum bir qatorda to'planishi mumkin bo'lgan eng ko'p suvni topish "yomg'irni ushlab turish" muammosi deb nomlanadi.
Maqsad har bir satrning chap va o'ng tomoniga joylashtirilishi mumkin bo'lgan eng yuqori chiziqni aniqlashdir. Chap va o'ngdagi etakchi chiziqlarning minimal darajasi, joriy barning balandligidan kam, har bir barning tepasida saqlanadigan suv miqdori.
Xulosa
Boshqa ma'lumotlar strukturasi mavzulari bilan solishtirganda, massivlar oddiyroq. Massiv intervyu savollariga javob berish uchun siz massivlar haqida asosiy tushunchaga ega bo'lishingiz kerak.
Massivlar asoslarini, jumladan massiv operatsiyalarini (massivni e'lon qilish/yaratishdan massiv elementlariga kirish/o'zgartirishgacha), shuningdek, massiv intervyu savollariga muvaffaqiyatli javob berish uchun tsikllar, rekursiya va asosiy operatorlar kabi dasturlash tushunchalarini batafsil ko'rib chiqishingiz kerak. Muammoni to'liq tan oling.
Agar sizda biron bir savol bo'lsa, aniqlik kiritishingiz kerak. Muammoni boshqariladigan qismlarga bo'lish haqida o'ylab ko'ring. Dasturlashni boshlashdan oldin algoritmni yodda tutganingizga ishonch hosil qiling; uni qog'ozga yozing yoki uni sxemada tasavvur qiling. keyin kod yozishni boshlang.
Leave a Reply