İçindekiler[Saklamak][Göstermek]
- 1. Bir Diziyi nasıl tanımlarsınız?
- 2. Dinamik Diziler: Bunlar Nelerdir? Onları Temel Dizilerden ayıran nedir?
- 3. Bir dizi ve bir sözlük birbirinden nasıl farklıdır?
- 4. Dizilerin bazı avantajlarını ve dezavantajlarını listeleyin.
- 5. “Sparse Array” neyi ifade eder?
- 6. Bir dizi yerine ne zaman bağlantılı bir liste seçersiniz?
- 7. İndekslenmiş bir diziyi ilişkisel diziden ayıran nedir?
- 8. Heap'in sıralı dizilere göre ne gibi avantajları vardır?
- 9. Dizinin boyutunu negatif olarak tanımlayabilir miyiz?
- 10. 1 ila 100 elemanlı bir dizide eksik tamsayıyı nasıl bulursunuz?
- 11. Bir dizideki bir elemanın indeksini nasıl bulursunuz?
- 12. Bir diziden belirli bir elemandan nasıl kurtulabilirsiniz?
- 13. İki dizinin eşitliği nasıl doğrulanabilir?
- 14. Dizileri tartıştığımızda, “Boyut” ve “Alt Simge” ifadeleriyle ne demek istiyorsunuz?
- Mülakat Sorularını Kodlama
- 15. Belirtilen toplamı olan bir dizide bir çift arayın
- 16. Doğrusal zamanla ikili dizi sıralama
- 17. Bir dizideki en büyük iki-intlik ürünü bulun.
- 18. Dizinin tüm sıfırları nasıl sona kaydırılır
- 19. Bir işlemde değiştirilen iki girişli bir dizi nasıl sıralanır.
- 20. Sıralanmış iki dizi nasıl yerinde birleştirilir.
- 21. Değişken yüksek ve düşük konumlarda bir dizi öğe nasıl yeniden sıralanır?
- 22. Bir dizinin her elemanı, dizideki her elemanın çarpımı ile bölme operatörü kullanmadan nasıl değiştirilir?
- 23. Bir dizideki en tuhaf elemanı logaritmik zamanda bulun
- 24. Dairesel bir dizideki her bir eleman için sonraki daha büyük eleman nasıl elde edilir?
- 25. Bir dizinin ters çevirme sayısı bulunsun mu?
- 26. Yağmur Suyu Kapanma Problemi Nedir?
- Sonuç
Kodlama görüşmeleri bir dizi DSA sorusu içerir. FAANG veya başka bir Tier-1 teknoloji işletmesi ile yapacağınız teknik röportaj için hazırlanıyorsanız, diziler konusunda yetenekli olmalısınız.
Çoğu kodlama röportajında, Strings'e ikinci sırada gelir. Dizi, bellekte birbirine yakın tutulan ilgili veri öğelerinin bir grubudur.
C, C++, Java, Python, Perl ve Ruby gibi tüm programlama dillerine bağlı oldukları için her yerdeler. Bazı uygulama kodlama zorlukları ve dizilere dayalı röportaj soruları ve cevapları için okumaya devam edin.
Python bu yazıda kodlama sorunlarının üstesinden gelmek için kullanılacak çünkü kullanımı, kavranması basit ve çoğumuz için aşina olması gerekiyor.
Hadi başlayalım.
1. Bir Diziyi nasıl tanımlarsınız?
- Bir grup ilgili veri türü bir dizidir.
- Diziler her zaman sabittir.
- Aynı tür değişken, dizi nesneleri tarafından birkaç yerde saklanır.
- İlkel türler ve nesne başvuruları onunla uyumludur.
2. Dinamik Diziler: Bunlar Nelerdir? Onları Temel Dizilerden ayıran nedir?
Dinamik dizilerin (büyütülebilir diziler, yeniden boyutlandırılabilir diziler, değiştirilebilir diziler veya Java'da ArrayLists olarak da adlandırılır) sağladığı otomatik ölçeklendirme önemli bir avantajdır.
Dizilerin sabit bir boyutu olduğundan, dizinizin kaç öğe depolayacağını her zaman önceden bilmelisiniz. Öte yandan dinamik bir dizi, siz ona ek üyeler ekledikçe büyür, bu nedenle önceden tam boyutunu bilmeniz gerekmez.
3. Bir dizi ve bir sözlük birbirinden nasıl farklıdır?
Bu, düzenli olarak sorulan temel bilgilere dayalı bir dizi görüşme sorusudur. Diziler ve sözlükler arasındaki temel farklar şunlardır:
- Dizi, benzer öğelerin sıralı bir listesidir. Sözlük ise anahtar/değer çiftlerine sahiptir.
- Dizi boyutları dinamik olarak değişebilir. Bu tür dinamik fikirler sözlüklerde yoktur.
- Bir diziyi kullanmadan önce boyutu belirtilmelidir. Sözlük boyutlarının özelleştirilmesi gerekmez.
- Dizinin boyutunu genişletmek istiyorsanız Redim ifadesini kullanın. Sözlüklerde, bir bildirim olmadan bir öğe eklenebilir.
4. Dizilerin bazı avantajlarını ve dezavantajlarını listeleyin.
Avantajları:
- Diziler aynı anda birkaç öğeyi sıralayabilir.
- Diğer veri yapılarıyığınlar, kuyruklar, bağlantılı listeler, ağaçlar, grafikler vb. gibi bir dizide uygulanabilir.
- Dizinin bir elemanına ulaşmak için bir indeks kullanılabilir.
Dezavantajları:
- Bir dizinin boyutu önceden bildirilmelidir. Ancak dizi bildirimi anında, ihtiyacımız olan boyutun farkında olmayabiliriz.
- Dizinin yapısı statiktir. Dizi boyutunun her zaman sabit olduğu ve bellek tahsisinin artırılıp azaltılamayacağı anlamına gelir.
5. “Sparse Array” neyi ifade eder?
Seyrek dizi, sıfır değerli çok sayıda girişi olan bir veri dizisidir. Buna karşılık, yoğun bir dizi, öğelerinin çoğunu sıfır olmayan değerlerle içerir. Sayıları nesnelere dönüştüren seyrek bir dizinin dizinleri boşluklar içerebilir. Bir HashMap ile karşılaştırıldığında, bellek açısından daha verimlidirler.
6. Bir dizi yerine ne zaman bağlantılı bir liste seçersiniz?
Diziler yerine bağlantılı listeleri kullanırken şunları göz önünde bulundurun:
- Rastgele erişime sahip olmak için herhangi bir öğeye ihtiyacınız yoktur.
- Zamansal öngörülebilirliğin gerekli olduğu durumlarda, listeden sabit zamanlı eklemelere ve çıkarmalara ihtiyacınız vardır.
- Öncelik sırası oluşturmak için öğeleri listenin ortasına yerleştirmeniz gerekebilir.
- Listenin ne kadar uzun olacağı hakkında hiçbir fikriniz yok. Dizi boyutu artarsa, tıpkı basit dizilerde olduğu gibi belleği yeniden bildirmeli ve çoğaltmalısınız.
7. İndekslenmiş bir diziyi ilişkisel diziden ayıran nedir?
İlişkili ve dizine alınmış diziler arasındaki temel farklar aşağıdaki tabloda listelenmiştir.
- İlişkili bir diziyi sıralamak için metin veya sayısal biçimde bir anahtar/değer çifti kullanılır. Dizine alınmış dizinin anahtarlarının tümü sayısaldır ve her anahtar ayrı bir değere bağlıdır.
- İlişkili bir dizide, anahtar bir dize olabilir. 0'dan başlayan tamsayı tuşlarıyla dizine alınmış dizi.
- İki sütunlu bir tablo, ilişkisel bir dizinin davranışını taklit eder. Tek sütunlu bir tabloya benzer şekilde dizinlenmiş diziler vardır.
- Haritalar bir ilişkisel dizi türüdür. Bir dizin dizisi bir harita değildir.
8. Heap'in sıralı dizilere göre ne gibi avantajları vardır?
Sıralı Diziler Üzerinden Yığın kullanmanın zaman verimliliği, en önemli faydadır. Yığın işlemleri daha hızlı olsa da, bir diziyi sıralamak çok zaman gerektirir. Bir yığın, en küçük elemanı, bir dizinin sıralanabileceğinden çok daha hızlı keşfedebilir.
Belirli bir sayı koleksiyonu, Sıralanmış Diziler kullanılarak iki yoldan biriyle düzenlenebilir. Öte yandan, belirli bir sayı koleksiyonu için birden fazla potansiyel yığın olabilir.
9. Dizinin boyutunu negatif olarak tanımlayabilir miyiz?
Hayır, bir dizinin boyutu olarak negatif bir tamsayı tanımlayamayız. Bildirirsek derleme zamanı hatası olmayacak. Ancak çalışma zamanında bir NegativeArraySizeException ile karşılaşacağız.
10. 1 ila 100 elemanlı bir dizide eksik tamsayıyı nasıl bulursunuz?
Serinin toplamı aşağıdaki fonksiyon uygulanarak hesaplanabilir: n (n + 1) / 2
Yalnızca dizinin kopyası yoksa veya birden fazla tamsayı eksikse bu işlev çalışır. Bir dizinin yinelenen öğeleri olup olmadığına bakılmaksızın, eşdeğer olan herhangi bir öğe olup olmadığını görmek için diziyi sıralayabilirsiniz.
11. Bir dizideki bir elemanın indeksini nasıl bulursunuz?
Bir elemanın dizini, doğrusal veya ikili arama yoluyla keşfedilebilir. Gerekli öğenin eşleşmesini bulana kadar, bir dizideki her bir öğe üzerinde doğrusal bir arama işlevi döngü yapar. Eşleşen öğeyi bulduğunda dizini döndürür. Sonuç olarak, doğrusal aramanın zamansal karmaşıklığı O'dur. (n). Hem sıralanmış hem de sıralanmamış bir dizi doğrusal arama kullanabilir.
Aralığın medyanı gerekli öğeyle eşleşene kadar diziyi sürekli olarak ikiye bölen ve dizini sağlayan ikili aramayı kullanarak, dizi sıralanmışsa öğenin dizinini alabilirsiniz. Sonuç olarak, ikili aramanın zamansal karmaşıklığı O'dur. (log n).
12. Bir diziden belirli bir elemandan nasıl kurtulabilirsiniz?
Öğeleri, tanımlanmış bir boyuta sahip sabit kümeler oldukları için orijinal diziden basitçe silemeyeceğinizden, görüşmeci sizden farklı bir yaklaşım önermenizi ve sorunun ortaya çıkardığı sorunla ilgilenmenizi istiyor. En iyi hareket tarzı, bir elemanı silmek için yeni bir dizi oluşturmaktır. Bu dizideki ilk dizideki öğeleri çoğaltabilir ve yalnızca silmek istediğiniz öğeyi dahil edebilirsiniz.
Başka bir strateji, dizideki hedef öğeyi bulmayı ve ardından hedef öğenin sağındaki tüm öğelerin sırasını tersine çevirmeyi içerir.
13. İki dizinin eşitliği nasıl doğrulanabilir?
Önce sağlanan iki dizinin uzunluklarını doğrulamanız gerekir. Her iki dizinin eşleşen öğeleri, uzunlukları eşit olduğunda karşılaştırılır. İki dizi eşit olarak kabul edilecektir. her yazışmadaki her bileşen çifti eşitse. Bu yaklaşım, çok zaman alacağından, diziler büyükse, iki dizinin eşitliğini kontrol etmeniz önerilmez. Arrays sınıfında bulunan equals() yöntemini de kullanabilirsiniz, ancak görüşmeci sizden yerleşik yöntemleri kullanmadan iki diziyi karşılaştırmanızı isterse, bu yöntem yararlı olacaktır.
14. Dizileri tartıştığımızda, “Boyut” ve “Alt Simge” ifadeleriyle ne demek istiyorsunuz?
Bir dizinin "Boyutu", her bir üyeyi tanımlamak için gereken dizin veya alt simge sayısıdır. Abonelikler ve boyutlar belirsiz olabilir. Boyut, izin verilen anahtar aralığının açıklamasıdır, alt simge ise bir sayıdır. Her dizi boyutu için yalnızca bir alt simge gereklidir.
Örneğin, arr[10][5] dizisinin iki boyutu vardır. Birinde 10, diğerinde 5 beden. Bileşenlerini ele almak için iki abonelik gerekir. Her ikisi de 0 ile 4 arasındadır; 0 ile 9 arasında bir, dahil.
Mülakat Sorularını Kodlama
15. Belirtilen toplamı olan bir dizide bir çift arayın
Örneğin,
Giriş:
- sayılar = [8, 7, 2, 5, 3, 1]
- hedef = 10
Çıktı:
- Çift bulundu (8, 2)
- Or
- Çift bulundu (7, 3)
Giriş:
- sayılar = [5, 2, 6, 8, 1, 9]
- hedef = 12
Çıktı:
- çift bulunamadı
16. Doğrusal zamanla ikili dizi sıralama
Bir ikili diziyi doğrusal zamanda ve sabit bir alanda sıralayın. Çıktı önce tüm sıfırları, ardından hepsini göstermelidir.
Örneğin,
- Giriş: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Çıktı: { 0, 0, 0, 0, 1, 1, 1, 1 }
Basit bir yaklaşım, dizinin toplam 0 sayısını, diyelim ki k'yi hesaplamak ve ardından dizideki ilk k indeksi 0'larla ve kalan indeksleri 1 ile doldurmak olacaktır. Alternatif olarak, toplamda kaç tane 1'in olduğunu hesaplayabiliriz. dizi k, dizideki son k dizini 1 ile doldurun ve geri kalan dizinleri 0 ile dolu bırakın.
Verilen yaklaşımın bir O(n) zaman karmaşıklığı vardır ve n'nin girdinin boyutu olduğu ek depolama kullanmaz.
17. Bir dizideki en büyük iki-intlik ürünü bulun.
Bir tamsayı dizisindeki iki sayının en büyük ürününü bulun.
Örnek olarak 10 3 5 6 2 dizisini düşünün. (-10, -3) veya (5, 6) çifti en yüksek çarpımdır.
Her öğe kombinasyonunu düşünmek ve ürünlerini bulmak aptalca bir yaklaşımdır. Mevcut çiftin ürünü, o ana kadar elde edilen maksimum üründen büyükse, maksimum ürünü güncelleyin. Son ürünün bileşenlerini en son yazdırın.
n'nin girdi miktarı olduğu yukarıdaki çözüm, O(n2) zaman karmaşıklığına sahiptir ve daha fazla yer kaplamaz.
18. Dizinin tüm sıfırları nasıl sona kaydırılır
Bir tamsayı dizisindeki tüm sıfırları sona taşı. Cevap, sabit alan kullanmaktan kaçınmalı ve dizinin bileşenlerinin göreli sırasını korumalıdır.
Giriş: {1,2,3,0,8,0,4,7}
Çıktı {1,2,3,8,4,7,0,0} olacaktır
Geçerli öğe sıfır değilse, öğeyi dizide aşağıdaki uygun konuma yerleştirin. Dizinin tüm öğeleri işlendikten sonra kalan tüm dizinleri 0 ile doldurun.
Önceki çözüm, bir O(n) zaman karmaşıklığına sahiptir, burada n, girdinin boyutudur.
19. Bir işlemde değiştirilen iki girişli bir dizi nasıl sıralanır.
Değiştirilmiş iki öğe ve tüm öğeleri artan düzende düzenlenmiş bir dizi verilen doğrusal zamanda bir diziyi sıralayın. Dizinin kopya içermediğini varsayın.
Girdi:= [1,9,3,4,7,2] veya [9,3,7,2,1,4] veya [2,4,1,7,3,9]
Çıktı: = [1,2,3,4,7,9]
Dizideki ikinci elemandan başlayarak, amaç her bir elemanı bir öncekiyle karşılaştırmaktır. Anlaşmazlığın konumu, x ve y olmak üzere iki işaretçi alınarak kaydedilir.
x'i önceki öğenin dizinine ve y'yi geçerli öğenin dizinine güncelleyin, eğer birincisi ikincisinden daha büyükse. Önceki öğenin geçerli öğeden daha büyük olduğu ortaya çıkarsa, y'yi geçerli öğenin dizinine güncelleyin.
Son olarak, her bitişik öğe çiftini işlemeyi bitirdikten sonra, x ve y dizinlerindeki öğeleri değiştirin.
Yukarıda bahsedilen yöntemin, n boyutundaki girdi dizisinin yalnızca tek bir taramasını gerçekleştirmesi nedeniyle, zaman karmaşıklığı O(n)'dir. Çözüm için ek odaya gerek yoktur.
20. Sıralanmış iki dizi nasıl yerinde birleştirilir.
Her biri m ve n boyutunda iki sıralanmış dizi olan X[] ve Y[] dizilerinin öğelerini, sıralı düzeni koruyarak, yani X[] öğesini ilk m en küçük öğeyle ve Y[] öğesini aşağıdaki öğelerle doldurarak birleştirin. kalan unsurlar.
X[] dizisindeki bir öğe zaten doğru konumdaysa (yani, kalan öğeler arasında en küçüğü olan), onu dikkate almayın; aksi takdirde, onu Y[]'nin ilk üyesi olan en küçük elemanla değiştirin. Değiştirdikten sonra sıralı düzeni korumak için öğeyi (şimdi Y[0] konumunda) Y[] içindeki uygun konumuna aktarın.
İlk dizinin boyutu m'dir ve ikinci dizinin boyutu n'dir ve zaman karmaşıklığı O(mn)'dir.
21. Değişken yüksek ve düşük konumlarda bir dizi öğe nasıl yeniden sıralanır?
Bir tamsayı dizisini, sonraki her üye önceki ve sonraki öğelerden daha büyük olacak şekilde yeniden düzenleyin. Dizinin yinelenen öğeler içermediğini varsayalım.
Etkili bir yaklaşım için diziyi sıralamak veya ek alan kullanmak gerekli değildir. Plan, dizinin ikinci üyesiyle başlamak ve her döngü yinelemesi için ikiye çıkmaktır.
Son öğe birinciyi aşarsa bileşenleri değiştirin. Benzer şekilde, aşağıdaki öğe mevcut öğeden daha büyükse her iki öğeyi de değiştirin. Döngünün sonunda belirtilen kısıtlamalara uyan istenen diziyi elde edeceğiz.
22. Bir dizinin her elemanı, dizideki her elemanın çarpımı ile bölme operatörü kullanmadan nasıl değiştirilir?
Bölme operatörünü kullanmadan, bir tamsayı dizisindeki her öğeyi diğer tüm öğelerin çarpımı ile değiştirin.
Doğrusal zaman ve sabit uzayda, bu sorunu çözmek için özyinelemeyi kullanabiliriz. Sağ alt dizideki her bir elemanın ürünlerini yinelemeli olarak hesaplamak ve sol alt dizi ürününü fonksiyon parametreleri olarak geçirmek kavramdır.
Zaman karmaşıklığı O(n)'dir.
23. Bir dizideki en tuhaf elemanı logaritmik zamanda bulun
Bir üye hariç hepsinin çift sayıda meydana geldiği bir tamsayı dizisi verildiğinde, sorun bu elemanın kaç kez göründüğünü belirlemektir. Aynı elemanlar dizide çiftler halinde bulunuyorsa ve belirli bir elemanın bir satırda hiçbir zaman ikiden fazla örneği olamazsa, logaritmik zaman ve sabit uzayda tek meydana gelen elemanı bulun.
XOR işlemi, bu sorunu doğrusal zamanda çözmemizi sağlar. Amaç, dizideki her öğeyi XOR yapmaktır. Çift meydana gelen elemanlar birbirini iptal ettikten sonra sadece tek meydana gelen elemanlar kalır.
Bu sorun O(log(n)) zamanında bile çözülebilir.
24. Dairesel bir dizideki her bir eleman için sonraki daha büyük eleman nasıl elde edilir?
Dairesel bir tamsayı dizisindeki her eleman için bir sonraki büyük eleman bulunmalıdır. Dizideki bir x öğesinden sonraki ilk büyük tam sayı, o öğenin sonraki büyük öğesidir.
Sağdan sola, dizi öğeleri üzerinde çalışabiliriz. Amaç, yığın boşalana veya üzerinde daha yüksek bir öğe olana kadar her x öğesi için döngü yapmaktır. Bir sonraki büyük x öğesini, göründüğünde yığının üstünde görünecek şekilde ayarlayın.
25. Bir dizinin ters çevirme sayısı bulunsun mu?
Bir dizinin toplam ters çevirme sayısını bulun. Bir I j) çifti, eğer I j) ve (A[i] > A[j]) ise A dizisinin tersi olarak adlandırılır. Dizideki bunların her çiftini saymalıyız.
Sağında kendisinden daha az olan tüm dizi üyelerini saymak ve sonucu çıktıya eklemek basit bir yaklaşımdır.
Bu çözüm O(n2) karmaşıklığına sahiptir, burada n girdinin boyutudur.
26. Yağmur Suyu Kapanma Problemi Nedir?
Her biri bir birim genişliğindeki belirli bir çubuk setinde tutulabilecek en fazla suyu bulmak, “yağışın tutulması” sorunu olarak bilinir.
Amaç, her bir çubuğun soluna ve sağına yerleştirilebilecek en yüksek çubuğu belirlemektir. Soldaki ve sağdaki önde gelen çubukların minimumu, mevcut çubuğun yüksekliğinden daha az, her bir çubuğun üzerinde depolanan su miktarıdır.
Sonuç
Diğer veri yapısı konularına kıyasla diziler daha basittir. Dizi mülakat sorularında başarılı olmak için diziler hakkında temel bir anlayışa sahip olmanız gerekir.
Dizi görüşme sorularını başarılı bir şekilde yanıtlamak için dizi işlemleri (bir dizi bildirmekten/oluşturmaktan dizi öğelerine erişmeye/değiştirmeye kadar) ve döngüler, özyineleme ve temel operatörler gibi programlama kavramları da dahil olmak üzere dizilerin temellerini kapsamlı bir şekilde gözden geçirmelisiniz. Sorunu tamamen tanıyın.
Herhangi bir sorunuz varsa açıklama istemelisiniz. Sorunu daha yönetilebilir parçalara bölmeyi düşünün. Programlamaya başlamadan önce algoritmayı aklınızda bulundurduğunuzdan emin olun; yazın veya bir akış şemasında görselleştirin. ardından kod yazmaya başlayın.
Yorum bırak