gömülü yazılım mülakatlar

Knuth–Morris–Pratt Algoritması | Mülakatlar [Codility – Hackerrank – Qualified.io]


Bazı yaklaşım metodlarını, düşünce aşamalarını ilgili konularla ilişkilendiren yapılarda pratik yapmak, yeni gelecek problemlerde artık sorunun çözümünü omurilik soğanına aktarmak için birebir. Her şeyin anahtarı pratik ve pratik. Kimisi için 3 pratik, kimisi için 5 pratik ama pratik.

İnsanın da gördüğü, deneyimlediği kadar bir varlık olduğunu düşünürsek bugün ben de sizlere KMP algoritmasını ve beraberinde bir firmanın mülakatında sorulmuş olan bir soruyu KMP kullanarak ve kullanmayarak çözmeye çalışacağım. Karakter gruplarının bir araya geldiği ifadelerde işlem yapmak – arama, silme, değiştirme gibi günün sonunda belli bir indekse dayandırılması gereken işlemler – zahmetli olabiliyor. Ama aranacak ifade özelinde bir lut oluşturabilirsek ve bu oluşturduğumuz lut ile birlikte asıl aradığımız yere gidersek süreçleri iyileştirebilmekteyiz. Dijital bir sistem üzerinde çalıştığımızı düşünürsek iyileştirdiğimiz şey algoritma karmaşıklığı olacaktır.

Yukarda ifade etmeye çalıştığım gibi KMP algoritması iki aşamadan oluşmakta;

  1. Öncelikle pattern(aranacak ifade) için bir lut oluşturmak.
  2. Text içerisinde arama yaparken lut’u kullanmak.

Nasıl bir metin içerisinde arayacağımızı şu an için düşünmeden, elimizde şöyle bir pattern olduğunu varsayalım.

aabaabaaa
pattern

Bu pattern içerisinde görebileceğiniz gibi kendini parçalı halde kendini tekrar eden bazı bölümler bulunmakta. Yani KMP algoritmasını uygulamak isteyeceğiniz yapıların böyle olması önem arz etmekte. Standart arama algoritmalarından daha verimli sonuçlar verme durumunu ortayan çıkaran bu zaten. Çünkü patternin kendisinde oluşturduğunuz lut sayesinde, arama yaparken eşleşmeyen bir karakter sonrasında tüm süreci başa almak yerine pattern içerisinde hangi karaktere dönüş yapacağımızı belirlemiş oluyoruz. Öncelikle bu lut nasıl oluşturuluyor buna bakalım.

Pattern içerisinde gezinirken iki farklı index değeri tutuyoruz. Bunlar i ve j diyelim. j değerimizin başlangıç değeri 0 ve i değerimizin başlangıç değeri ise 1 olarak başlasın. Buna ek olarak pattern ilk indexli elemanın lut içerisinde ki değeri her zaman 0 olarak başlamalı. Şimdi adım adım bu lut’u oluşturalım.

1.Adım

aabaabaaa
000000000

1.adımda i = 1, j = 0 değeri ile başlamakta. Ve tüm lut şu anda 0 olarak işaretlenmiş. Bir sonraki adım içerisinde i ve j’nin sahip olduğu değerler pattern’e index olarak verilir ve karşılaştırılma yapılır. Eğer karşılaşma sonrası eşleşme meydana gelirse, i’nin lut index değeri j + 1 olarak belirlenir i ve j değeri bir arttırılır. Şayet herhangi bir eşleşme bulunmaz ise bizim için j’nin değerinin 0’a eşit olması ya da olmaması önemli. O kısma geleceğiz.

2.Adım

aabaabaaa
010000000

1.adım açıklama kısmında yazdığımız gibi, şöyle bir kod parçacığı oluşmakta.

if (pattern[j] == pattern[i])
{
      table_array[i] = j + 1;
      i++;
      j++;
}

Karşılaştırmaya pattern sonuna gelene kadar devam ediyoruz, 3.adımda pattern[1] ve pattern[2] karakterlerinde bir karşılaştırma yapacağız. Eğer karakterlerin eşit olmaması durumunda şayet j değeri sıfırdan farklı bir değer ise pattern içerisinde bir tekrar olup olmadığını anlayabilmek adına j’nin yeni değerini lut tablosunda mevcut j değerinin index değerinde bulunan ifadeden bir önceki değere eşitliyoruz, yani şöyle bir kod parçacığı oluşmakta.

if (j != 0)
{
      j = table_array[j - 1];
}

3.Adım

aabaabaaa
010000000

2.Adım içerisinde bahsettiğimiz üzere yapılan karşılaştırma sonrasında j değeri şu anda 0 olmuş durumda çünkü table_array[0] değerimiz 0’dı. i değeri ise 2 olarak durmakta. Bu döngünün bir while içerisinde döndüğünü düşünürsek şu anda pattern[0] ve pattern[2] üzerinde bir karşılaştırma yapılmakta. Burada yeni bir durum çıkmakta. Şayet j değeri 0’a eşit ise lut içerisinde ki i’nin lut index değeri 0 olmakta. Yani şöyle bir kod parçacığı oluşmakta.

if (j != 0) 
{
       j = table_array[j - 1];
}

else
{                
       table_array[i] = 0;
       i++;     
}

Buradan anlayabiliriz ki ilgili index ve öncesinin başlangıcında herhangi bir şekilde tekrar bulunmamakta. Bir adım daha yapacağım ve diğer adımları size bırakacağım.

4.Adım

Karşılaştırmaya devam ediyoruz şu anda j değerimiz 0, i değerimiz ise 3 olmuş durumda. pattern[0] ve pattern[3] arasında bir eşleşme olduğuna göre, 1.adımda ki süreç gerçekleşiyor.

aabaabaaa
010100000

Tüm bu adımlar sonrasında lut şu halini almakta.

010123452

2. aşama olan arama kısmında benzer bir süreç gerçekleşmekte. Eğer j kısmı verilen pattern uzunluğuna eşit ise pattern bulunmuş demektir ve i – j değeri bizim aradığım text içerisinde patternin başladığı indexi döndürmekte. Tüm bu süreçleri ve ilgili örneğin koda dökülmüş haline şuradan erişebilirsiniz.

Şimdi gelelim bir mülakatta sorulmuş bir soruyu çözmeye çalışalım. Bu soruda KMP kullanmak zorunda elbette değiliz. Nedenini zaten lut oluşturduğumuzda görebiliriz.

We are given a string S of length N consisting only of letters ‘A’ and/or ‘B’. Our goal is to obtain a string in the format “A…AB B” (all letters ‘A’ occur before all letters ‘B’) by deleting some letters from S. In particular, strings consisting only of letters ‘A’ or only of letters ‘B’ fit this format.

Examples :

Given S = “BAAABABA”, the function should return 2.

Given S = “BBABAA”, the function should return 3.

Given S = “AABBBB”, the function should return 0.

İnsanın karşısına string algoritmaları ile ilgili bir soru geldiğinde ve belli bir süre içerisinde bir çözüm sağlaması gerektiğinde hatta ve hatta karşı taraf sesli düşünerek biz çözüm istiyorsa fakat daha önce çok fazla pratik yapılmamış ise biraz dumor olabiliyor. Belki daha öncesinde öğrenilen bir yaklaşım mevcut soru için verilen doğruluk, zaman karmaşıklığı gibi çözüm parametreleri açısında iyi olmayabilir ama o yaklaşım sayesinde farklı bir yaklaşım sergileyebiliriz.

Ben kendi çözümümden bahsedeceğim, belki farklı yaklaşımlara sahip olabilirsiniz ki bu çok normal. Bu soruda ilk olarak bb ve ba gibi patternin varlığının olup olmamasını sınamak benim için doğru bir yaklaşım gibi geldi. Bu yaklaşımda önemli olan şu eğer bb patterni mevcut ise şöyle bir şey gelebilir bba ama ba patterni mevcut ise başlangıçta minumum 4 karakterlik bir arayış gerçekleşmesi gerekir. Buna ek olarak bb patterni mevcut ise bu pattern öncesinde ba gibi patternin varlığı gerçekleşmiş ya da devamında gerçekleşecek mi ?

Benim bu soru özelinde gerçekleştirmiş olduğum ve kmp kullandığım yapıyı şuradan görebilirsiniz. Aklınıza gelen bir test vakasını denediğinizde bir problem var ise bildirirseniz çok sevinirim. Peki bu soruda KMP kullanmak mantıklı mı ? Çözümü incelerseniz KMP yaklaşımında ufak tefek bazı değişikler yapıldığını görebilirsiniz. Soruya bir çözüm sağlayıp rahatladıktan sonra tekrar bakıldığında aslında lut tablosu bb patterni için 0 1 ba patterni için 0 0 değerini almakta. Ve arama kısmında bu lut tablosu çokta işlevsel değil. Tekrar düşünüldüğünde ortaya şu yapı çıkmakta. İşte bahsetmeye çalıştığım olay bu aslında KMP algoritmasını bilmiyor olsaydım o konuda bir pratiğim olmasaydı belki de bu yaklaşımı yapamıyor olabilirdim.

Pratik, pratik, pratik yazılımın anahtarı bence bu. Bir sonraki string algoritmasında görüşmek üzere.