Genel

Mülakat Sorusu #1 – Verilen Bir Sayı, Listedeki Herhangi İki Elemanın Toplamına Eşit mi?

16 Temmuz 2019

Merhabalar,

Yeni bir yazı serisine başlıyoruz. Her hafta Google, Uber, Facebook vb. büyük şirketlerde sorulmuş olan mülakat sorularını cevaplayacağız. Farklı zorluklardaki soruları, farklı çözüm yollarıyla cevaplamaya çalışacağım. Özellikle bu tarz firmalarda işe girmek isteyen arkadaşlara çok faydalı olacağını düşünüyorum. Genel olarak sorular Python ile çözülecek. Size tavsiyem sorunun çözümüne bakmadan önce kendiniz de çözmeye çalışın. Son olarak tek bir çözüm olmak zorunda olmadığını da aklınızda bulundurun.

Çok uzatmadan ilk sorumuz ile başlayalım.

Google tarafından sorulmuş bir soru.

Verilen bir liste ve n sayısı ile, listenin içinde herhangi iki elemanın toplamının bu sayıyı verip vermediğini gösterin.

Örneğin, listemiz [2, 3, 6, 1, 4] ve n sayımız da 5 ise bize “True” döndürecek. Çünkü, 4+1=5.

Bonus: Bu işlemi listede sadece bir kere dönerek yapabilir misiniz?


Çözüm #1 – Brute Force

Genelde akla gelen ilk çözüm “Brute Force” olur. Çoğu zaman da bu çözüm sizden beklenmez ve açıkçası size pozitif bir etkisi olmaz. Yapacağımız şey çok basit. Öncelikle listenin ilk elemanını iki sayıdan biri olarak alacağız. Aradığımız sayı da (n – o anki sayımız) olacak. Örneğin, listenin ilk elemanı 2 ise ve n sayısı da 4 ise, listenin kalan elemanlarında 2’nin olup olmadığına bakacağız. Bu işlemi listedeki tüm elemanlar için yapacağız. Yani aslında iki tane for loop kullanacağız.

Listeyi iç içe iki kere dolaştığımız için bu kodun çalışma hızı (running time) O(n2) olacak. Tabii ki, böyle bir soruyu n2 gibi bir çözümle bırakmak doğru olmaz.

Çözüm #2 – Set Kullanarak

Bu çözüm ile kodumuzun çalışma hızı O(n) olacak ancak aynı zamanda da space complexity artacak. Brute Force çözümünde herhangi bir space complexity yoktu. Ancak çalışma hızı arttığı için aslında çoğu zaman space complexity’den feragat ediyoruz. Bunun yanında aslında mülakatlarda sunduğunuz çözümlerde, size soruyu soran kişi, space complexity olmadan çözmenizi de isteyebilir. Bu noktada da aslında üçüncü çözümümüze bakacağız.

Bu çözümde yapacağımız şey, listedeki elemanları dolaşırken, her eleman için aradığımız diğer sayısı bir set yapısının içinde tutacağız. Şöyle ki; örneğin, listedeki ilk eleman 3 ve n sayısı da 4. Başta oluşturduğumuz set yapısının içine 1 sayısını koyacağız. Bu sırada listedeki elemanlarda gezerken de, aradığımız sayının, oluşturduğumuz set’in içinde olup olmadığına bakacağız. Koda geçmeden önce küçük bir örnek yapalım. Listemiz [2, 5, 6, 7, 1, 12] elemanlarından oluşsun ve n sayımız da 11 olsun. Listeyi dolaştığımızda ilk elemanımız 2 olacak. 11-2=9 olduğu için önce oluşturduğumuz set’in içinde 9 elemanı var mı diye bakacağız. Yoksa 9 elemanını koyacağız. Varsa True döndüreceğiz. Daha sonra ikinci elemana geçeceğiz. 11-5=6 olduğu için, önce 6 sayısının set’in içinde olup olmadığına bakacağız. Varsa True döndüreceğiz. Yoksa set’in içine ekleyeceğiz. Tüm listeyi bu şekilde dolaşacağız.

Umarım açıklayıcı olmuştur. O zaman kodumuza geçelim:

Kodumuzun çalışma hızı artık O(n) oldu. Çünkü, listeyi sadece bir kere dolaşıyoruz. Aklınıza, set içindeki elemanı aradığımız için çalışma hızı O(n) olmaz şeklinde sorular gelebilir. Ama aslında set yapısını kullanmamızın sebebi de budur. Set yapısında arama işlemi O(1) sürede oluyor. Doğal olarak running complexity O(n) oluyor. Ama aynı zamanda da space complexity de artıyor. Çünkü, her elemanı set yapısının içinde saklıyoruz.

Çözüm #3 – Binary Search

Mülakat sırasında size şunu söyleyebilirler: “Çalışma hızı O(n2)’den az olsun ama aynı zamanda space complexity de olmasın. Yani elemanları bir yapının içinde tutmayın. Çünkü, bizim şirketimizde şu an bunu sağlayacak altyapı bulunmuyor.”.

Tabii ki, büyük şirketlerde böyle küçük ayrıntılar aslında çok önemli bir rol oynuyor. Doğal olarak sizden böyle bir şey istemesi çok olası.

Bu seferde yapacağımız şey çok basit aslında. Öncelikle listeyi sıralayacağız. Sıralama işleminden sonra her eleman için Binary Search uygulayacağız. Binary Search’ün çalışma hızı O(logn) olduğu için, kodumuzun çalışma hızı O(nlogn) olacak. Space complexity de O(1) olacak.

Burada şuna da dikkat etmek gerekiyor. Biz Python ile yazıyoruz kodumuzu. Sıralama işlemi Python’ın içinde önceden tanımlanmış olan Timsort’u kullanıyor. Timsort, Merge Sort’un bir versiyonu denilebilir. Bu sıralama işleminin çalışma süresi ise O(nlogn). Doğal olarak aslında kodumuzun çalışma hızı O(2nlogn) ama baştaki 2’nin burada bir anlamı olmadığı için çalışma hızımız O(nlogn) olacak.

https://www.quora.com/What-is-the-time-complexity-of-the-Python-built-in-sorted-function

Önce kodu yazalım, daha sonra da kısa bir açıklama yapalım. 🙂

Neler oluyor?

Binary Search, eğer aradığımız eleman listede varsa, o elemanın indeksini döndürüyor. Yok ise, -1 döndürüyor. j olarak atadığımız değişken ise Binary Search’ten bize gelen değer. Doğal olarak j’nin değerine göre True veya False döndüreceğiz. Eğer j değeri -1 ise, eleman bulunmamış demektir. Bu durumda yapacak bir şey yok, bir sonraki eleman için arama işlemini yapacağız.

Eğer j sayısı -1 değilse, demek ki eleman bulunmuştur. Bu durumda da öncelikle j’nin o anki indekse eşit olmadığına dikkat etmemiz gerekiyor. Çünkü sayının kendisi olmasını istemiyoruz. Örneğin, aradığımız toplam 4 olsun. O anki sayımız da 2 olsun. Binary Search ile 2’yi aradığımızda zaten elimizde olan 2’yi bulmasını istemiyoruz.

Sonraki yaptığımız iki tane if condition’ı aslında j sayısının i sayısına eşit olma ihtimalinden kaynaklanıyor. Başlangıçta listemizi sıralamıştık. Doğal olarak eğer j sayısı i sayısına eşitse, bu durumda listedeki bir önceki ve bir sonraki elemanlara bakmamız gerekecek. Çünkü, şöyle bir senaryo ile karşılaşabiliriz:

Listemiz [2, 3, 3, 5, 7, 9, 11] elemanlarından oluşur ve aradığımız sayı 6 olur. Listede ikinci ve üçüncü elemanlarda 3 sayısı var. Biz ikinci elemanda iken, Binary Search bize 1 döndürecek. Çünkü, 0 bazlı indekste 3 sayısının indeksi aslında 1. Aynı zamanda bizim o an bulunduğumuz indeks de 1. Eğer daha sonra eklemiş olduğumuz iki tane if condition’ı olmazsa, yukarıdaki listede False cevabını bekliyor olacağız. Doğal olarak indekslerin eşit olma durumunda elemanın sağına ve soluna bakacağız ki, böyle bir problem yaşanmasın.

Son olarak eğer hiçbir şekilde eleman bulunamazsa, False döndüreceğiz.

Artık kodumuzu yazdığımıza göre, her zaman yaptığımız gibi test işlemine geçeceğiz. Onu da artık size bırakıyorum. 🙂


Sonuç

Hemen yaptıklarımızın bir özetini yapalım. Birbirinden farklı 3 çözüm yolumuz vardı. Bunlardan ilki Brute Force ve genelde tercih edilmeyen, kabul görmeyen çözüm. Akla gelen ilk çözüm. İkincisi ise space complexity kullanarak kodumuzu çok hızlandıran bir yöntem. İhtiyaca göre kabul edilebilir. Eğer, memory konusunda sıkıntınız yok ise, bu yöntemi kullanmak mantıklı olacaktır. Algoritmanız çok daha hızlı çalışır. Üçüncü yöntem ise, biraz daha karışık görünen, aslında ilk iki yöntemin kombinasyonu denilebilecek bir yöntem. Listeyi bir kere dolaşıyoruz ama her defasında Binary Search yapıyoruz. Space complexity O(1) olurken -ki bu gayet kabul edilebilir- running time ise O(nlogn) oldu. Kodumuz birinci yöntemden daha hızlı çalışıyor, ancak ikinci yöntemden de biraz daha yavaş çalışıyor.

Bundan sonra, soru bana kolay geldi diyenler için, bu sorunun aynısını iki elemanın toplamı yerine 3 elemanın toplamı şeklinde çözmeye çalışabilirsiniz. Hatta, bunu daha da ileri götürerek, n elemanın toplamı olacak şekilde genişletebilirsiniz. Yani sorumuzun son ve zor hali şöyle olabilir:

Verilen bir listede, listedeki 2 veya daha fazla elemanın toplamı ile aradığımız bir n sayısının bulabilir miyiz? (İpucu: Dynamic Programming)

Sonuç olarak eğer karşınıza bu tarz bir problem çıkarsa farklı yöntemlerle, karşınızdaki kişinin ihtiyaçlarına göre çözmeniz gerekebilir. Bir sonraki yazı için soruyu buraya yazayım, siz de bu arada düşünün:

Uber tarafından sorulmuş bir soru.

Verilen bir liste ile listenin elemanları o anki eleman dışında diğer elemanların çarpımından oluşan yeni bir liste oluşturun.

Örneğin, size verilen liste [1, 2, 3, 4, 5] olsun. Beklenen sonuç [120, 60, 40, 30, 24] olmalı. Çünkü, listenin ilk elemanında 1 dışında diğer sayıların çarpımı 120, 2 dışında diğer sayıların çarpımı 60, 3 dışında diğer sayıların çarpımı 40 ve bu böyle gidiyor.

Bir örnek daha verelim. Bize verilen liste [6, 3, 5] olsun. Beklenen sonuç [15, 30, 18] olacaktır.

Ekstra: Bölme işlemi yapmanıza izin verilmeseydi ne yapardınız?

 

    Bir Cevap Yazın

    This site uses Akismet to reduce spam. Learn how your comment data is processed.