Mündəricat[Gizlət][Göstər]
- 1. Massivi necə təyin edirsiniz?
- 2. Dinamik massivlər: Onlar nədir? Onları əsas massivlərdən fərqləndirən nədir?
- 3. Massiv və lüğət bir-birindən necə fərqlənir?
- 4. Massivlərin bəzi üstünlüklərini və çatışmazlıqlarını sadalayın.
- 5. “Nadir massiv” nəyə istinad edir?
- 6. Siz nə vaxt massiv üzərində əlaqəli siyahını seçərdiniz?
- 7. İndeksli massivi assosiativ massivdən nə ilə fərqləndirir?
- 8. Heap çeşidlənmiş massivlərdən hansı üstünlüklərə malikdir?
- 9. Massivin ölçüsünü mənfi olaraq təyin edə bilərikmi?
- 10. 1-dən 100-ə qədər elementli massivdə çatışmayan tam ədədi necə tapmaq olar?
- 11. Massivdə elementin indeksini necə tapmaq olar?
- 12. Massivdən konkret elementi necə çıxarmaq olar?
- 13. İki massivin bərabərliyini necə yoxlamaq olar?
- 14. Biz massivləri müzakirə edərkən “Ölçü” və “Altyazı” ifadələri ilə nəyi nəzərdə tutursunuz?
- Müsahibə suallarının kodlaşdırılması
- 15. Göstərilən cəmi olan massivdə cüt axtarın
- 16. Xətti vaxtla binar massivlərin çeşidlənməsi
- 17. Massivdə ən böyük iki int hasilini tapın.
- 18. Massivin bütün sıfırlarını sona necə köçürmək olar
- 19. Bir əməliyyatda kommutasiya edilən iki qeydli massiv necə çeşidlənir.
- 20. İki çeşidlənmiş massivi yerində necə birləşdirmək olar.
- 21. Yüksək və aşağı mövqelərdə növbə ilə bir sıra elementləri necə sıralamaq olar?
- 22. Bölmə operatorundan istifadə etmədən massivin hər bir elementini massivdəki hər bir elementin hasili ilə necə əvəz etmək olar?
- 23. Loqarifmik zamanda massivdə ən qəribə elementi tapın
- 24. Dairəvi massivdə hər bir element üçün sonrakı daha böyük elementi necə əldə etmək olar?
- 25. Massivin inversiya sayını tapın?
- 26. Yağış suyunun tutulması problemi nədir?
- Nəticə
Kodlaşdırma müsahibələri bir sıra DSA suallarını ehtiva edir. FAANG və ya digər Tier-1 texnoloji biznes ilə qarşıdakı texnoloji müsahibənizə hazırlaşırsınızsa, seriallarda bacarıqlı olmalısınız.
Əksər kodlaşdırma müsahibələrində Strings-dən sonra ikinci yerdədir. Massiv yaddaşda bir-birinə yaxın saxlanılan əlaqəli məlumat elementlərinin qruplaşdırılmasıdır.
C, C++, Java, Python, Perl və Ruby kimi bütün proqramlaşdırma dillərinə qoşulduqları üçün hər yerdə mövcuddurlar. Bəzi təcrübə kodlaşdırma problemləri və massivlərə əsaslanan müsahibə sualları və cavabları üçün oxumağa davam edin.
Python bu yazıda kodlaşdırma problemlərini həll etmək üçün istifadə olunacaq, çünki istifadəsi sadədir, başa düşülür və çoxumuza tanış olmalıdır.
Başlayaq.
1. Massivi necə təyin edirsiniz?
- Əlaqədar məlumat növləri qrupu massivdir.
- Massivlər həmişə sabitdir.
- Eyni növ dəyişən massiv obyektləri tərəfindən bir neçə yerdə saxlanılır.
- Primitiv tiplər və obyekt istinadları onunla uyğun gəlir.
2. Dinamik massivlər: Onlar nədir? Onları əsas massivlərdən fərqləndirən nədir?
Dinamik massivlərin (həmçinin böyüyə bilən massivlər, ölçüsü dəyişdirilə bilən massivlər, dəyişən massivlər və ya Java-da ArrayLists adlanır) təmin etdiyi avtomatik miqyaslama əhəmiyyətli bir üstünlükdür.
Siz həmişə massivinizin neçə elementi saxlayacağını əvvəlcədən bilməlisiniz, çünki massivlərin sabit ölçüsü var. Dinamik massiv isə ona əlavə üzvlər əlavə etdikcə böyüyür, ona görə də əvvəlcədən onun dəqiq ölçüsünü bilməyə ehtiyac yoxdur.
3. Massiv və lüğət bir-birindən necə fərqlənir?
Bu, mütəmadi olaraq verilən müsahibə suallarının əsas əsaslı toplusudur. Massivlər və lüğətlər arasında əsas fərqlər aşağıdakılardır:
- Massiv oxşar elementlərin ardıcıl siyahısıdır. Lüğətdə isə açar-dəyər cütləri var.
- Massiv ölçüləri dinamik olaraq dəyişə bilər. Belə dinamik fikirlər lüğətlərdə yoxdur.
- Massivdən istifadə etməzdən əvvəl onun ölçüsü müəyyən edilməlidir. Lüğət ölçülərinin fərdiləşdirilməsinə ehtiyac yoxdur.
- Massivin ölçüsünü genişləndirmək istəyirsinizsə, Redim ifadəsindən istifadə edin. Lüğətlərdə bir element elan edilmədən əlavə edilə bilər.
4. Massivlərin bəzi üstünlüklərini və çatışmazlıqlarını sadalayın.
Üstünlükləri:
- Massivlər eyni vaxtda bir neçə elementi çeşidləyə bilər.
- digər məlumat strukturlarıməsələn, yığınlar, növbələr, əlaqəli siyahılar, ağaclar, qrafiklər və s. kimi, massivdə həyata keçirilə bilər.
- İndeks massivin elementinə çatmaq üçün istifadə edilə bilər.
Dezavantajları:
- Massivin ölçüsü əvvəlcədən elan edilməlidir. Massiv elanı anında biz tələb etdiyimiz ölçüdən xəbərdar olmaya bilərik.
- Massivin strukturu statikdir. Bu, massiv ölçüsünün həmişə sabit olduğunu və yaddaşın ayrılmasını artırmaq və ya azaltmaq mümkün olmadığını nəzərdə tutur.
5. “Nadir massiv” nəyə istinad edir?
Seyrək massiv, sıfır dəyəri olan çoxlu girişlərə malik məlumat massividir. Bunun əksinə olaraq, sıx massiv sıfırdan fərqli dəyərlərə malik elementlərinin əksəriyyətini ehtiva edir. Nömrələri obyektlərə çevirən seyrək massivin indekslərinə boşluqlar daxil ola bilər. HashMap ilə müqayisədə onlar daha səmərəli yaddaşa malikdirlər.
6. Siz nə vaxt massiv üzərində əlaqəli siyahını seçərdiniz?
Massivlər əvəzinə əlaqəli siyahılardan istifadə edərkən nəzərə alın:
- Təsadüfi giriş əldə etmək üçün heç bir elementə ehtiyacınız yoxdur.
- Müvəqqəti proqnozlaşdırmanın vacib olduğu yerlərdə, siyahıdan daimi əlavələr və silinmələr lazımdır.
- Prioritet növbəsi yaratmaq üçün elementləri siyahının mərkəzinə yerləşdirməli ola bilərsiniz.
- Siyahının nə qədər davam edəcəyini bilmirsiniz. Massiv ölçüsü artarsa, sadə massivlərdə olduğu kimi yaddaşı yenidən elan etməli və dublikat etməlisiniz.
7. İndeksli massivi assosiativ massivdən nə ilə fərqləndirir?
Assosiativ və indeksli massivlər arasında əsas fərqlər aşağıdakı cədvəldə verilmişdir.
- Mətn və ya rəqəmli formatda açar-dəyər cütü assosiativ massivi çeşidləmək üçün istifadə olunur. İndekslənmiş massivin düymələri hamısı rəqəmlidir və hər bir açar ayrı bir dəyərə bağlıdır.
- Assosiativ massivdə açar sətir ola bilər. 0-dan başlayan tam ədəd düymələri ilə indeksləşdirilmiş massiv.
- İki sütunlu cədvəl assosiativ massivin davranışını təqlid edir. Bir sütunlu cədvələ oxşar olaraq indekslənmiş massivlərdir.
- Xəritələr assosiativ massiv növüdür. İndeks massivi xəritə deyil.
8. Heap çeşidlənmiş massivlərdən hansı üstünlüklərə malikdir?
Sıralanmış massivlər üzərində yığından istifadənin vaxt səmərəliliyi əsas faydadır. Yığın əməliyyatları daha sürətli olsa da, massivin çeşidlənməsi çox vaxt tələb edir. Yığın ən kiçik elementi massivin çeşidlənməsindən xeyli tez kəşf edə bilər.
Verilmiş ədədlər toplusu Sorted Massivlərdən istifadə etməklə iki üsuldan biri ilə təşkil edilə bilər. Digər tərəfdən, verilmiş nömrələr toplusu üçün birdən çox potensial yığın ola bilər.
9. Massivin ölçüsünü mənfi olaraq təyin edə bilərikmi?
Xeyr, biz mənfi tam ədədi massivin ölçüsü kimi təyin edə bilmərik. Biz bəyan etsək, tərtib zamanı xətası olmayacaq. İş vaxtı biz NegativeArraySizeException ilə qarşılaşacağıq.
10. 1-dən 100-ə qədər elementli massivdə çatışmayan tam ədədi necə tapmaq olar?
Seriyanın cəmi aşağıdakı funksiyanı tətbiq etməklə hesablana bilər: n (n + 1) / 2
Yalnız massivin heç bir dublikatı yoxdursa və ya birdən çox tam ədəd yoxdursa, bu funksiya işləyəcək. Massivin dublikat elementləri olub-olmamasından asılı olmayaraq, ekvivalent elementlərin olub-olmadığını görmək üçün massivi çeşidləyə bilərsiniz.
11. Massivdə elementin indeksini necə tapmaq olar?
Elementin indeksi xətti və ya ikili axtarış vasitəsilə aşkar edilə bilər. Tələb olunan elementin uyğunluğunu tapana qədər xətti axtarış funksiyası massivdəki hər bir element üzərində dövr edir. Uyğun elementi tapdıqdan sonra indeksi qaytarır. Nəticə etibarilə, xətti axtarışın müvəqqəti mürəkkəbliyi O. (n)-dir. Həm çeşidlənmiş, həm də çeşidlənməmiş massiv xətti axtarışdan istifadə edə bilər.
Aralığın medianı tələb olunan elementə uyğun gələnə və indeksi təmin edənə qədər massivi davamlı olaraq yarıya bölən ikili axtarışdan istifadə edərək, massiv çeşidlənərsə elementin indeksini əldə edə bilərsiniz. Nəticə etibarilə, binar axtarışın müvəqqəti mürəkkəbliyi O. (log n)-dir.
12. Massivdən konkret elementi necə çıxarmaq olar?
Elementləri orijinal massivdən sadəcə silmək mümkün olmadığından, onlar müəyyən ölçüdə sabit dəstlər olduğundan, müsahibə götürən şəxs sizə fərqli yanaşma təklif etməyi və sualın doğurduğu problemi həll etməyinizi axtarır. Ən yaxşı hərəkət yolu elementi silmək üçün yeni massiv yaratmaqdır. Siz bu massivdə birinci massivin elementlərini təkrarlaya və yalnız silmək istədiyiniz elementi daxil edə bilərsiniz.
Başqa bir strategiya massivdə hədəf elementi tapmağı və sonra hədəf elementin sağında olan bütün elementlərin sırasını dəyişdirməyi əhatə edir.
13. İki massivin bərabərliyini necə yoxlamaq olar?
Əvvəlcə təqdim olunan iki massivin uzunluğunu yoxlamalısınız. Hər iki massivin uyğun elementləri uzunluqları bərabər olduqda müqayisə edilir. İki massiv bərabər hesab ediləcək. hər yazışmada komponentlərin hər bir cütü bərabərdirsə. Əgər massivlər böyükdürsə, bu yanaşma iki massivin bərabərliyini yoxlamaq tövsiyə edilmir, çünki bu, çox vaxt aparacaq. Siz həmçinin Arrays sinfinə daxil olan equals() metodundan istifadə edə bilərsiniz, lakin əgər müsahibiniz daxili metodlardan istifadə etmədən sizdən iki massivi müqayisə etməyi xahiş etsə, bu üsul faydalı olacaq.
14. Biz massivləri müzakirə edərkən “Ölçü” və “Altyazı” ifadələri ilə nəyi nəzərdə tutursunuz?
Massivin “Ölçüsü” hər bir fərdi üzvü müəyyən etmək üçün tələb olunan indekslərin və ya alt yazıların sayıdır. Alt yazılar və ölçülər qeyri-müəyyən ola bilər. Ölçü icazə verilən düymələr diapazonunun təsviridir, alt yazı isə rəqəmdir. Hər massiv ölçüsü üçün tələb olunan yalnız bir alt yazı var.
Məsələn, arr[10][5] massivinin iki ölçüsü var. Birində 10, digərində 5 ölçü. Onun komponentlərinə müraciət etmək üçün sizə iki alt işarə tələb olunur. Hər ikisi 0 ilə 4 arasındadır; 0 ilə 9 arasında bir, daxil olmaqla.
Müsahibə suallarının kodlaşdırılması
15. Göstərilən cəmi olan massivdə cüt axtarın
Misal üçün,
Input:
- ədədlər = [8, 7, 2, 5, 3, 1]
- hədəf = 10
Çıxış:
- Cüt tapıldı (8, 2)
- Or
- Cüt tapıldı (7, 3)
Input:
- ədədlər = [5, 2, 6, 8, 1, 9]
- hədəf = 12
Çıxış:
- Cüt tapılmadı
16. Xətti vaxtla binar massivlərin çeşidlənməsi
İkili massivi xətti vaxt və sabit sahədə çeşidləyin. Çıxış əvvəlcə bütün sıfırları, sonra isə hamısını göstərməlidir.
Misal üçün,
- Daxiletmə: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Çıxış: { 0, 0, 0, 0, 1, 1, 1, 1 }
Sadə yanaşma, massivin ümumi 0-ların sayını hesablamaqdır, deyək ki, k və sonra massivdəki ilk k indeksləri 0-larla, qalan indeksləri isə 1-lə doldurmaq olar. Alternativ olaraq, cəmi neçə 1-in olduğunu hesablaya bilərik. k massivi, massivdəki son k indeksləri 1 ilə doldurun və qalan indeksləri 0 ilə doldurun.
Verilmiş yanaşma O(n) vaxt mürəkkəbliyinə malikdir və əlavə yaddaşdan istifadə etmir, burada n girişin ölçüsüdür.
17. Massivdə ən böyük iki int hasilini tapın.
Tam ədədlər massivində iki ədədin ən böyük hasilini tapın.
Nümunə olaraq 10 3 5 6 2 massivini düşünün. (-10, -3) və ya (5, 6) cütü ən yüksək məhsuldur.
Hər bir element birləşməsini düşünmək və onların məhsulunu anlamaq axmaq bir yanaşmadır. Cari cütün məhsulu indiyə qədər əldə edilmiş maksimum məhsuldan böyükdürsə, maksimum məhsulu yeniləyin. Son məhsulun komponentlərini çap edin.
Yuxarıdakı həll, burada n girişin miqdarıdır, O(n2) zaman mürəkkəbliyinə malikdir və daha çox yer tutmur.
18. Massivin bütün sıfırlarını sona necə köçürmək olar
Tam ədəd massivindəki bütün sıfırları sonuna qədər köçürün. Cavab sabit boşluqdan istifadə etməməli və massiv komponentlərinin nisbi sırasını qorumalıdır.
Giriş: {1,2,3,0,8,0,4,7}
Çıxış {1,2,3,8,4,7,0,0} olacaq
Cari element sıfır deyilsə, elementi massivdə aşağıdakı mövcud mövqeyə qoyun. Massivin bütün elementləri işləndikdən sonra bütün qalan indeksləri 0 ilə doldurun.
Əvvəlki həll O(n) zaman mürəkkəbliyinə malikdir, burada n girişin ölçüsüdür.
19. Bir əməliyyatda kommutasiya edilən iki qeydli massiv necə çeşidlənir.
İki dəyişdirilmiş element və onun bütün elementləri artan qaydada düzülmüş massiv verilmiş xətti vaxtda massivi çeşidləyin. Massivin heç bir dublikat olmadığını iddia edin.
Giriş:= [1,9,3,4,7,2] və ya [9,3,7,2,1,4] və ya [2,4,1,7,3,9]
Nəticə: = [1,2,3,4,7,9]
Massivdəki ikinci elementdən başlayaraq, məqsəd hər bir elementi sələfi ilə müqayisə etməkdir. Mübahisənin mövqeyi iki göstərici, x və y götürülməklə saxlanılır.
Əvvəlki elementin indeksinə x-i, əgər birincisi sonuncudan böyükdürsə, y-ni cari elementin indeksinə yeniləyin. Əvvəlki elementin cari elementdən böyük olduğu ortaya çıxarsa, y-ni cari elementin indeksinə yeniləyin.
Nəhayət, hər bir qonşu element cütünü emal etdikdən sonra x və y indekslərindəki elementləri dəyişdirin.
Yuxarıda qeyd olunan metodun yalnız n ölçülü giriş massivinin tək skanını yerinə yetirdiyinə görə onun zaman mürəkkəbliyi O(n) təşkil edir. Həll üçün əlavə otaq lazım deyil.
20. İki çeşidlənmiş massivi yerində necə birləşdirmək olar.
X[] və Y[] massivlərinin elementlərini - hər biri m və n ölçülü iki çeşidlənmiş massiv - çeşidlənmiş sıranı saxlamaqla, yəni X[]-ni ilk m ən kiçik elementlə və Y[]-ni isə qalan elementlər.
X[] massivindəki element artıq düzgün mövqedədirsə (yəni, qalan elementlər arasında ən kiçik olan), ona əhəmiyyət verməyin; əks halda onu ən kiçik elementlə əvəz et, o da Y[]-nin ilk üzvüdür. Mübadilədən sonra çeşidlənmiş sıranı saxlamaq üçün elementi (indi Y[0]-da) Y[]-də lazımi yerə köçürün.
Birinci massivin ölçüsü m, ikinci massivin ölçüsü n, zaman mürəkkəbliyi isə O(mn)-dir.
21. Yüksək və aşağı mövqelərdə növbə ilə bir sıra elementləri necə sıralamaq olar?
Tam ədəd massivini elə təşkil edin ki, hər bir sonrakı üzv əvvəlki və sonrakı elementlərdən böyük olsun. Tutaq ki, massiv heç bir dublikat elementi ehtiva etmir.
Effektiv yanaşma üçün massivi çeşidləmək və ya əlavə yerdən istifadə etmək lazım deyil. Plan, başlamaq üçün, serialın ikinci üzvüdür və hər döngə iterasiyası üçün iki yuxarı qalxın.
Sonuncu element birincidən çox olarsa, komponentləri dəyişdirin. Oxşar şəkildə, əgər aşağıdakı element cari elementdən böyükdürsə, hər iki elementi dəyişin. Döngənin sonunda göstərilən məhdudiyyətlərə uyğun gələn istənilən massivi alacağıq.
22. Bölmə operatorundan istifadə etmədən massivin hər bir elementini massivdəki hər bir elementin hasili ilə necə əvəz etmək olar?
Bölmə operatorundan istifadə etmədən, tam ədəd massivindəki hər bir elementi bütün digər elementlərin məhsulu ilə əvəz edin.
Xətti zaman və sabit məkanda bu problemi həll etmək üçün rekursiyadan istifadə edə bilərik. Sağ alt massivdə hər bir elementin hasillərinin rekursiv hesablanması və sol altmassiv məhsulunun funksiya parametrləri kimi ötürülməsi anlayışdır.
Zaman mürəkkəbliyi O(n)-dir.
23. Loqarifmik zamanda massivdə ən qəribə elementi tapın
Bir üzvdən başqa hamısının cüt sayda baş verdiyi tam ədəd massivini nəzərə alsaq, problem bu elementin neçə dəfə göründüyünü müəyyən etməkdir. Eyni elementlər massivdə cüt-cüt baş verərsə və heç vaxt bir cərgədə verilmiş elementin ikidən çox nümunəsi ola bilməzsə, loqarifmik zamanda və sabit fəzada tək baş verən elementi tapın.
XOR əməliyyatı bizə bu problemi xətti vaxtda həll etməyə imkan verir. Məqsəd massivdəki hər bir elementi XOR etməkdir. Cüt baş verən elementlər bir-birini ləğv etdikdən sonra yalnız tək baş verən elementlər qalır.
Bu problem hətta O(log(n)) vaxtında həll edilə bilər.
24. Dairəvi massivdə hər bir element üçün sonrakı daha böyük elementi necə əldə etmək olar?
Dairəvi tam ədəd massivindəki hər bir element üçün növbəti daha böyük element yerləşdirilməlidir. Massivdəki x elementindən sonra ilk böyük tam ədəd həmin elementin sonrakı böyük elementidir.
Sağdan sola, biz massiv elementləri üzərində işləyə bilərik. Məqsəd hər bir x elementi üçün ya yığın boş olana, ya da onun üstündə daha yüksək element olana qədər dövrə vurmaqdır. Növbəti böyük x elementini yığının üstündə görünməsi üçün təyin edin.
25. Massivin inversiya sayını tapın?
Massivin inversiyalarının ümumi sayını tapın. I j) və (A[i] > A[j]) olduqda I j) cütü A massivinin inversiyasına istinad edilir. Massivdə bunların hər bir cütünü saymalıyıq.
Ondan az olan bütün massiv üzvlərini onun sağında saymaq və nəticəni çıxışa əlavə etmək sadə bir yanaşmadır.
Bu həll O(n2) mürəkkəbliyə malikdir, burada n girişin ölçüsüdür.
26. Yağış suyunun tutulması problemi nədir?
Hər birinin eni bir vahid olan müəyyən çubuqlar dəstində tutula bilən ən çox suyun tapılması “tutulan yağış” problemi kimi tanınır.
Məqsəd hər bir çubuğun solunda və sağında yerləşdirilə bilən ən yüksək çubuğu müəyyən etməkdir. Sol və sağdakı aparıcı çubuqların minimumu, cari çubuğun hündürlüyündən az, hər bir çubuğun üstündə saxlanılan suyun miqdarıdır.
Nəticə
Digər verilənlər strukturu mövzuları ilə müqayisədə massivlər daha sadədir. Massiv müsahibə suallarını həll etmək üçün massivlər haqqında fundamental anlayışa sahib olmalısınız.
Siz massivlərin əsaslarını, o cümlədən massiv əməliyyatlarını (massiv elan etməkdən/yaratmaqdan massiv elementlərinə daxil olmaq/dəyişiklik etməyə), eləcə də massiv müsahibə suallarına uğurla cavab vermək üçün döngələr, rekursiya və əsas operatorlar kimi proqramlaşdırma konsepsiyalarını geniş şəkildə nəzərdən keçirməlisiniz. Problemi tamamilə tanıyın.
Hər hansı bir sualınız varsa, aydınlaşdırmağa çalışmalısınız. Məsələni daha idarə edilə bilən hissələrə bölməyi düşünün. Proqramlaşdırmaya başlamazdan əvvəl alqoritmi nəzərə aldığınızdan əmin olun; onu yazın və ya axın sxemində görüntüləyin. sonra kod yazmağa başlayın.
Cavab yaz