Bir Mülakat Sorusu Örneği ve Çözümü

Merhabalar,

Yaklaşık 4 aydan sonra yazı yazmak aklıma gelebildi. Dün youtube’da takılırken bir video izledim. Videoda söylendiğine göre basit bir mülakat sorusu ve Google’da sorulmuş.

Soru şöyle: Elimizde bir string var ve bu stringdeki karakterlerden tekrar edenlerden ilki hangisidir? Örneğin ‘ABCDABC’ kelimesinde ilk tekrar eden karakter ‘A’ dır. Bu problemi Java koduyla çözmeye çalışacağım.

Yukarıda yazdığım kodu incelersek, givenString adında bir String tipinde değişken tanımladım. Onun altında ise ilk for döngüsünü bütün harfler üzerinde gezinmek için yazdım. İçerideki for döngüsü ise seçilen harften bir sonraki harflerin üzerinden gezinmek için yazdım. if koşulu ise ilk döngüde üzerinde olduğum harf ile ondan sonra gelen harfleri tek tek karşılaştırıyor, eğer karakterler aynıysa ekrana yazıp programı sonlandırıyor.

Yukarıdaki algoritmada verilen kelimenin uzunluğu n olursa; ilk döngü n defa dönerse, ikinci döngü n-1 defa dönecek. O yüzden algoritma O(n^2) hızında çalışacaktır.

Peki bu algoritmayı nasıl iyileştirebiliriz?

Verilen kelime içindeki karakterler için bir tablo tutsak ve sayılarını karşılarına yazsak, sonra tablodan sayısı birden fazla olan ilk karakteri alsak güzel olabilir.

Yukarıda yazılan koda baktığımızda ise, harf ve sayılarını tutacağımız bir map oluşturuyoruz. Yine bir for döngümüz var, if koşulunda eğer o harf daha önceden eklenmişse harfi yazdırıp programdan çıkıyoruz. Eğer harf daha önceden eklenmemişse map imize harfi ekliyoruz. Böylece ilk tekrar eden harf eklenmeyip if koşuluna girip programı sonlandırıyor. Bu algoritmada sadece bir for döngüsü var ve String in uzunluğuna n dersek, n defa dönüyor. O yüzden bu algoritmamız 0(n) hızında çalışacaktır. Diğer algoritmaya göre hızlı çalışacaktır.

Bu yazıda basit bir mülakat sorusunu Java kodu ile anlatmaya çalıştım. Umarım işinize yarar, iyi çalışmalar.

Leave a Reply

Your email address will not be published. Required fields are marked *

%d bloggers like this: