Teknik mülakatlara hazırlanma süreci çoğu geliştiriciler için hep stresli olmuştur. Yazıda da mülakatlarda sorulan algoritmaların çözüm tekniklerinden, yaklaşımlarından ve çözüm için kullanılan ortak desenlerden bahsedip biraz da olsa bu yaşanılan stresi azaltmasını umuyorum. Yazının sonunda da yazdığım hem benim faydalandığım hem de sizin işinize yarayacağını düşündüğüm kaynakları incelemeyi unutmayın.

Her gün en az bir tane algoritma problemi çözmeye çalışıyorum. Bazen basit problemlerde dahi, çözümü göremediğim veya zorlandığım yerler olabiliyor. HackerRank ve Leetcode gibi siteler bazen çözümlerinizi kabul etmeyebiliyorlar. Test case’lerinde daha büyük veriler ile test ettiklerinden çözüm yeterli olmuyor. Çözülen problemin karmaşıklığı da çok önemli oluyor ve yazdığınız kodu daha verimli yazmak için kodu refactor etmeniz gerekiyor.

Benzer durumlarla teknik mülakat süreçlerinde de karşılaşabiliyoruz. Bazen algoritmayı çözüp karmaşıklığını düşüremediğim problemler olabiliyor. Böyle durumlarda başkalarının çözümlerini inceleyerek ve karşılaştığım desenleri kullanarak daha verimli çözümler elde ediyorum. Size de bu desenlerden bahsetmeye çalışacağım. Dolayısıyla bu yazının mülakatlara girecek geliştiricilere de yardımcı olmasını amaçlıyorum. Bu desenleri mülakata hazırlanırken ne kadar çok uygularsanız, desenlere uygun bir problem çözerken alternatifleri değerlendirebilecek ve kodunuzu daha verimli halde yazabileceksiniz.

Temel anlamda algoritmayı, bazı değerleri girdi olarak alan ve bazı değerleri çıktı olarak üreten hesaplamaların bir bütünüdür diye tanımlayabiliriz. Dolayısıyla girdileri çıktılara dönüştüren hesaplama adımlarının tamamıdır. Algoritma çözme becerisi başarılı bir geliştirici olmamız için gereken en önemli temeldir. Bu yazıda tabii ki çok karışık algoritmaların çözümlerinden bahsetmeyeceğim. Amacım problemlere yaklaşırken kendi uyguladığım adımları size anlatmak. Konu algoritmalar olunca ilk akla gelen teknik mülakatlar oluyor. Ama bu ikisi arasındaki bağlantıyı düşünmezsek yani algoritma çözmeyi mülakatlar için gerekliliğini düşünmeden kendimizi geliştirmek ve farklı bakış açıları kazanmak için çözmeye çalışırsak çok zevkli bir hale gelebilir. Kişisel olarak benim bakış açım ve davranışım bu şekilde.

Algoritma problemlerini çözmek her alanda size problem çözebilme becerisi kazandıracaktır. Bazı geliştiricilerin problemleri çözme yetenekleri diğerlerinden daha iyi veya kötü olabilir. Bu tamamen kendini kontrol etmek ve stres yönetiminden geçer. Algoritma çözme desenlerine geçmeden önce her problemde alınabilecek aksiyonlardan kısa kısa bahsedelim.

Teknik mülakat esnasında çoğu kişi o anda strese bağlı olarak direkt problemi çözmeye girişiyor. Bu ilk yapılan yanlışlardan biridir. Girdiğim mülakatlarda aynısını ben de yaptım ve problemin içinden çıkamadım. İlk yapmamız gereken sakin olup problemi tam anlamıyla anlamaya çalışmaktır. Kimse sizi hızlı bir çözüm için zorlamıyor. Problemi anlamadığımız zaman kesinlikle mülakatı yapan kişiye sorular yönelterek anlamaya çalışın. Aşağıdaki aşamaları sırasıyla uygulayabilirsiniz;

1. Problemi iyi analiz edin.
2. Problemi kendi cümleleriniz ile ifade edebiliyor musunuz? Eğer bunu yapamıyorsanız problemi yeterince anlamamışsınızdır.
3. Probleme ait girdi ve çıktı değerlerini iyi analiz edip, edge caseleri mülakat yapan kişiye sorabilirsiniz.
4. Problemi parçalara ayırın ve yorum satırlarıyla ifade edin.
5. Kodlamaya başlayın.
6. Kodu refactor edin.

Mülakat sırasında bu maddeleri uygulamak zaman alır diye düşünmeyin. Mülakata hazırlık aşamasında çözdüğünüz her probleme bunları uygularsanız zaten bu süreç kendiliğinden oturacaktır ve farkında olmadan bunları uygulayacaksınız.

Problemi sadece okumak o problemi anlamak anlamına gelmiyor. Probleme ilk baktığınızda bir fikriniz oluşabilir. Detaylı analiz ederek iyi anlamaya çalışın. Sorunu anlamazsanız varsaydığınız yanlış bir çözümü uygulayabilirsiniz.

Problemi kendi cümlelerimiz ile ifade edebilmek kendimiz için anlamlı olacaktır. Teknik mülakatta bunu karşınızdaki kişiye ifade ederseniz problemi doğru anladığınızın onayını alırsınız.

Basit girdilerle problemi düşünebilirsiniz ve sonrasında boş veya geçersiz girdilerin gelmesi durumunda nasıl davranmalısınız sorusuna cevap arayabilirsiniz. Bu sizin analitik düşünmenizi de geliştirecektir.

Kodu yazmaya başlamadan önce problemi çözmek için problemi parçalara ayırın ve adımları tek tek yazın. Bu size anlamlı bir yol haritası çıkaracaktır ve kod yazarken detayları atlamanızı engelleyecektir. Ayrıca tüm alt parçaları ayrı ayrı test edebilirsiniz. Eğer teknik mülakatta iseniz problemi çözemediğiniz zaman geride mülakat yapan kişinin incelemesi için çözüm yaklaşımınız kalacaktır. Bu da sizin işe alınmanıza yardımcı olabilir.

Yukarıdaki adımları ne kadar güzel uygularsanız kodlama aşaması o kadar kolay geçecektir. İlk aşamada kodun kalitesine bakmadan ve karmaşıklığını düşünmeden böldüğünüz aşamaları tek tek tamamlayın ve ortaya bir çözüm çıkarın. Sonrasında kodu düzelterek çözümün karmaşıklığını iyileştirebilirsiniz. Bu arada alışkanlık olması açısından koda girişmeden önce çıkardığınız adımların testlerini yazıp ondan sonra koda girişmeniz sizin gelişiminiz açısından çok daha iyi olacaktır.

Algoritmaları çözerken genelde en kötü duruma göre düşünmek ve çözümü buna göre üretmek daha iyi olacaktır. Algoritmanın en kötü durumda çalışması bize herhangi bir girdinin çalışma zamanı hakkında bir üst sınır bilgisi verir. Dolayısıyla bazı denemelere ihtiyaç duymayız ve çözümün daha kötü olmayacağını anlarız. Bazı algoritmalar genel olarak en kötü durumda çalışabilir. Herhangi bir arama algoritmasında verinin bulunmaması o algoritma için en kötü durumdur diyebiliriz.

Algoritma Desenleri

Bu kısımda algoritma çözümleri için kullanılan ve bize yardımcı olabilecek bazı ortak desenlerden bahsedeceğim. Bu desenler tabii ki tüm algoritma problemlerini çözmemize yardımcı olmuyor ama spesifik olan probleme yaklaşımımızı değiştirir ve daha verimli bir çözüm üretmemizi sağlar. Desenleri açıklarken daha iyi anlaşılması için sık kullanılan örnek problem ve çözümlerine yer verdim. Bu problemlerin çözümlerini yazının sonunda belirttiğim kaynaklardan aldım.

Frequency Counter Pattern

Diziler veya stringlerle ilgili problemler ile uğraşıyorsanız bu desen doğru bir çözüm olabilir. Bu desen bir veri yapısında diğer veri yapısının elemanlarının sayılması, karşılaştırılması veya aranmasını gerektiren problemlerde kullanılabilir. Bu tür problemlerde genelde direkt kodu yazmaya giriştiğimizde karmaşıklığı O(N²) olur. Ama bu deseni kullanırsak çoğu durumda O(N)’i yakalayabiliriz. Bu deseni örnekle açıklamak için sık kullanılan aşağıdaki problemi ele alalım;

Problem: Parametre olarak verilen iki string’e göre, ikinci string birinci string’in anagramı ise true değilse false döndüren programı yazalım.

isAnagram('', '') //true
isAnagram('aaz', 'zza') //false
isAnagram('qweryt', 'qeywrt') //true

Bu problemi çözmek için yapmamız gereken ilk diziyi döngüyle dönüp her elemanı aldıktan sonra ikinci dizide var mı yok mu diye kontrol etmektir. Yoksa zaten anagramı olmuyor.

function isAnagram(str1, str2) {
    if (str1.length !== str2.length) {
        return false;
    }
    for (var i = 0; i < str1.length; i++) {
        var indx = str2.indexOf(str1[i]);
        if (indx === -1) {
            return false;
        }
        str2 = str2.substring(0, indx) + str2.substring(indx + 1);
    }
    return true;
}

Bu çözümde de gördüğümüz gibi for döngüsü ve indexOf fonksiyonu O(N) karmaşıklığına sahiptir. Çözümümüzün karmaşıklığı ise O(N²) oluyor. Bu probleme desenimizi uygularsak;

function isAnagram(str1, str2){
    if (str1.length !== str2.length) {
        return false;
    }
    var count1 = {};
    var count2 = {};
    var ch;
    var i;
    for (i = 0; i < str1.length; i++) {
        ch = str1[i];
        count1[ch] = ++count1[ch] || 1;
    }
    for (i = 0; i < str2.length; i++) {
        ch = str2[i];
        count2[ch] = ++count2[ch] || 1;
    }
    var keys = Object.keys(count1);
    for (ch = 0; ch < keys.length; ch++) {
        if (
            !count2[keys[ch]] ||
            count1[keys[ch]] !== count2[keys[ch]]
        ) {
            return false;
        }
    }
    return true;
}

Bu çözümde ise dizilerin bir elemanı ulaşma karmaşıklığı O(1) olduğundan toplamda iç içe olmayan üç tane ayrı for döngüsü görüyorsunuz. Her bir döngünün karmaşıklığı O(N) olduğundan problemin toplam karmaşıklığı da O(N)’e inmiş oluyor. Alıştırma olarak siz de aşağıdaki problemi bu deseni kullanarak çözebilirsiniz.

Problem: Verilen parametrelerden herhangi birinin çiftinin olup olmadığını bulan programı yazın. Çözüm O(N) karmaşıklığında olmalıdır.

areDuplicates(3, 9, 1) // false
areDuplicates(4, 3, 8, 4) // true
areDuplicates('n', '6', '3', 'Z') // false

Multiple Pointers Pattern

Bu desen, sıralı veri yapısında başlangıç ve bitişte olmak üzere iki tane pointer oluşturuyor. Döngünün her adımında koşula göre bu pointer’ı veri yapısının ortasına doğru hareket ettiriyor. Veri yapısındaki elemanların aranması veya sayılmasını gerektiren problemlerde kullanılabilir. Bu desen için aşağıdaki problemi ele alalım;

Problem: Verilen sıralı bir dizide toplamı sıfır olan ilk çifti bulan programı yazalım.

sumZero([-3, -2, -1, 0, 1, 2, 3]); // [-3, 3]
sumZero([-2, 0, 1, 3]); // undefined
sumZero([1, 2, 3]); // undefined

Deseni düşünmeden direkt çözmeye başladığımız zaman ilk aklımıza gelen iç içe döngü ile sayıları gezip toplamlarının sıfıra eşit olup olmadığını kontrol etmektir.

function sumZero(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] + arr[j] === 0){
                return [arr[i], arr[j]];
            }
        }
    }
}

Çözümün karmaşıklığı bu şekilde O(N²) olacaktır. Bu çözüm çok büyük diziler için verimli olmaz. Bu probleme deseni uyguladığımız zaman aşağıdaki gibi bir çözüm olur.

function sumZero (arr) {
   let left = 0;
   let right = arr.length - 1;
   while(left < right) {
       let sum = arr[left] + arr[right]
       if(sum === 0) {
          return [arr[left], arr[right])
       } else if(sum > 0) {
            right --;     
       } else {
            left ++;       
       }
   }
}

Çözümde de görüldüğü gibi iç içe olan döngüleri teke indirerek karmaşıklığı O(N)’e çektik. Dizinin sağından ve solundan birer elemanı pointer olarak belirledik. Döngünün her koşulunda aradaki farkın durumuna göre bu pointer’ı dizinin ortasına kaydırdık. Bu desenle daha fazla uğraşmak için bu linkte bulunan problemleri inceleyebilirsiniz.

Sliding Window Pattern

Bu desen de diğer desenler gibi dizi ve string problemlerini çözmekte çok etkilidir. Problemin çözümünün karmaşıklığını O(N²)’den O(N)’e indirir. Yaptığı iş ise verilen veri yapısının başından belli uzunlukta bir alt dizi oluşturarak istenilen koşula göre bu alt diziyi sonucu bulana kadar kaydırır. Bu desen için aşağıdaki problemi ele alalım;

Problem: Birinci parametre olarak verilen dizinin ardışık ikinci parametre kadar elemanın maksimum toplamını hesaplayan programı yazalım.

maxSubarraySum([-3,4,0,-2,6,-1], 2);    // 5
maxSubarraySum([3,-2,7,-4,1,-1,4,-2,1], 2); // 5
maxSubarraySum([2,3], 3);   // null

function maxSubarraySum(arr, num) {
    if (arr.length < num) {
        return null;
    }
    var sum = -Infinity;
    for (var i = 0; i < arr.length - num + 1; i++) {
        var temp = 0;
        for (let j = 0; j < num; j++) {
            temp += arr[i + j];
        }
        if (temp > sum) {
            sum = temp;
        }
    }
    return sum;
};

Deseni uygulamadan çözülen örneği incelediğimizde iç içe iki döngünün olduğunu görüyoruz. Dolayısıyla çözümün karmaşıklığı O(N²) oluyor.

function maxSubarraySum(arr, num) {
    if (arr.length < num) {
        return null;
    }
    var maxSum = 0;
    var tempSum = 0;
    for (let i = 0; i < num; i++) {
        maxSum += arr[i];
    }
    tempSum = maxSum;
    for(let i = num; i < arr.length; i++) {
        tempSum = tempSum - arr[i - num] + arr[i];
        if (tempSum > maxSum) {
            maxSum = tempSum;
        }
    }
    return maxSum;
};

Deseni uyguladığımızda ise karmaşıklık O(N)’e düşüyor. İlk döngüde verilen ikinci parametre kadar elemanın toplamını alıyoruz. Daha sonra ilk döngüde nerede kaldıysak oradan başlayıp yine ikinci parametre kadar eleman alıp diğer toplamla kıyaslıyoruz. Aldığımız bu alt diziyi sona kadar kaydırarak maksimum toplamı elde ediyoruz. Bu desenle daha fazla uğraşmak için bu linkte bulunan problemleri inceleyebilirsiniz.

Divide and Conquer Pattern

Diğer desenlere göre daha çok bilinen bir desendir. Bu yaklaşım, problemi alt problemlere böler (divide), bu alt problemleri özyinelemeli olarak çözer (conquer) ve ana problemin çözümünü oluşturmak için bu çözümleri birleştirir. Sıralamala algoritmalarından quickSort ve mergeSort , arama algoritmalarından ise binary search bu desene örneklerdir. Bu desen için aşağıdaki problemi ele alalım;

Problem: Birinci parametre olarak verilen sıralı dizide ikinci parametreyi arayan ve bulursa index’ini bulamazsa -1 dönen programı yazalım.

search([1, 2, 3, 4, 5], 3) //2
search([1, 2, 3, 4, 5], 5) //4
search([1, 2, 3, 4, 5], 8) //-1

function search(arr, num) {
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] === num) {
            return i;
        }
    }
    return -1;
}

Çözüm çok basit ama deseni uygulamazsak çözümün karmaşıklığı O(N) oluyor.

function search(arr, num) {
    let start = 0;
    let end = arr.length - 1;
    while (start <= end) {
        let mid = Math.floor(start + end / 2);
        if (arr[mid] === num) {
            return mid;
        } else if (arr[mid] < num) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

Deseni uyguladıktan sonra karmaşıklık O(log n)’e iniyor ve daha verimli çalışıyor. Çözümde de görüldüğü gibi dizinin ortasındaki elemanı bularak sayının o elemandan büyük mü küçük mü olduğu kontrol ediliyor. Dolayısıyla dizinin diğer yarısını gezmemize gerek kalmıyor. Bu şekilde en ufak parçaya kadar diziyi parçalıyor ve çözüme ulaşıyor. Daha fazla alıştırma için bu linkteki problemleri inceleyebilirsiniz.

Bu yazımda, algoritma problemlerinin çözümünü daha verimli yazabilmek için bazı desenlerden kısa kısa bahsetmeye çalıştım. Desenleri daha detaylı incelemenizde fayda var. Bunları sık sık tekrar etmeniz çok önemli. HackerRank ve Leetcode gibi sitelerde mümkün olduğunca fazla zaman harcayın. En önemli nokta, problemi çözmek için ilk başta kendiniz uğraşın ve bir yere geldikten sonra çözemezseniz tartışma bölümünde diğer geliştiricilerin farklı programlama dillerindeki çözümlerini inceleyin. Zaten onlar şu desenle çözdüm, şu karmaşıklığı aldım, çözüm şu şekilde gibi yorumlar yapıyorlar.

Yazılım şirketlerince sorulan en popüler problemlerin ve çözümlerinin olduğu şu linki ve veri yapıları ve algoritmaların detaylı anlatıldığı şu linki kesinlikle inceleyin. Cracking the Coding Interview ve Introduction to Algorithm kitaplarını okumanızı şiddetle öneririm. Ayrıca Grokking Algorithms kitabı ise algoritmaların anlatımını görselleştirerek anlattığı için daha rahat anlamanızı sağlayabilir. Bu kitaplar algoritmalar ve çözüm yöntemleri konusunda sizi çok geliştirecektir. Kurs olarak ise internette baya bir eğitim var bunlarla ilgili ama benim izlediğim ve bu yazıda anlattığım desenleri ve örneklerini kullandığım JavaScript Algorithms and Data Structures Masterclass kursunu öneririm. Bu kursta sizi geliştirecek ve teknik mülakatlara hazırlayacak arama, sıralama ve çoğu veri yapısının detaylı açıklamaları, çözümleri ve örnekleri mevcut.

Saydığım kaynaklardan çalışıp, sitelerden de her gün en az bir tane soru çözdüğünüz zaman teknik mülakatlardan korkmak için sebep kalmıyor. Herhangi bir durumda profilimdeki sosyal medya hesaplarımdan bana ulaşabilirsiniz.