Kısa bir soru

Arada bir teknik mülakatların sorularını inceliyorum. Bazıları basit olsa da nedense bir hoşuma gidiyor. Bu da onlardan bir tanesi :)

Bu soruyla bir tane teknik mülakatta karşılaşmıştım. Sonrasında mülakat sorularını incelerken bir yerde daha denk geldim. Sorunun kendisi gayet kısa, verilen bir dizide toplamları N’e eşit olan alt dizilerin sayılarının bulunması isteniyor.

Misal elimizdeki dizi [1, 23, -5, 7, 21, 3, 3, 2, -5], toplam olarak istenen N değeri de 23 olsun.

En basit çözüm olarak aşağıdaki çözüm verilebilir.

 

Bu çözüm tüm index çiftleri için toplamı hesaplayıp, toplam N’e eşitse sonucu 1 arttırıyor. O(n^3)‘lük bir çözüm, bu yüzden büyük diziler için çok da güzel bir çözüm değil. Aşağıdaki çözüm ise kümülatif toplamları tuttuğundan çözümü en içteki for’dan kurtarıyor ve complexity O(n^2) oluyor.

 

Bu iki çözümü de O(n)‘e yaklaştırmak istiyoruz. Kümülatif toplamları hesapladığımıza göre, totals dizisinin i. elemanı için yapmamız gereken (aslında 2. çözümde de yaptığımız) kümülatif toplamı totals[i] – N olan elemanların sayısını bulmak. Bunun içinse tekrar tekrar lineer arama yapmamıza gerek yok.

 

Son çözümde, her kümülatif toplamdan önceki toplamları bir hashtable’da tuttuk. Böylece, istenen değerlerinin sayısını O(1) zamanda hesaplayabiliyoruz. O(n) zaman da diziyi dolaşmakla geçiyor ve son çözümün complexity’si O(n) oluyor.

Umarım bir hata yapmamışımdır :)