Birçok zor LeetCode problemi aslında kolay kısıt problemi

• LeetCode'daki zor problemler bile kısıt çözücüleri kullanıldığında çok daha kolay çözülebilir
• Karmaşık dinamik programlama ya da özel algoritmalar yerine MiniZinc gibi kısıt çözücüleri kullanılarak matematiksel optimizasyon problemleri basitçe çözülebilir
• Geleneksel programlama dilleri bu tür matematiksel optimizasyon problemlerini ifade etmekte zorlandığından, kısıt tabanlı yaklaşım burada güçlüdür
• İstisna durumları veya ek kısıtlar ortaya çıktığında da kısıt çözücülerindeki modelde çok az değişiklik yapmak yeterlidir
• Çalışma zamanı karmaşıklığı elle yazılmış optimize algoritmalardan daha yavaş olabilir, ancak esneklik ve geliştirme verimliliği açısından birçok avantaj sunar

---

Kısıt çözücü ile çözülen LeetCode problemleri

Doğru aracın seçimi

• Yazar, üniversiteden mezun olduktan sonraki ilk mülakatında "bozuk para üstü problemi" ile karşılaştı

  • Verilen bozuk para birimleriyle, belirli bir tutarı ödemek için gereken en az bozuk para sayısını bulma problemidir
  • Basit bir açgözlü algoritma kullandı, ancak bu yöntem her durumda en iyi çözümü garanti etmiyordu
  • Doğru yaklaşım dinamik programlamaydı, ancak bunu uygulayamadığı için mülakatta başarısız oldu

• Ancak algoritmayı doğrudan kendiniz yazmak yerine MiniZinc gibi bir kısıt çözücü kullanarak bunu çok kolay çözebilirsiniz

  • Örnek kod:

    int: total;
    array[int] of int: values = [10, 9, 1];
    array[index_set(values)] of var 0..: coins;
    
    constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
    solve minimize sum(coins);
    

  • Çevrimiçi olarak doğrudan MiniZinc örneğini çalıştırabilirsiniz

  • Çözücü en iyi çözümü adım adım bulur

Çeşitli optimizasyon/tatmin problemleri

• LeetCode vb. platformlarda sık görülen matematiksel optimizasyon problemleri (amaç fonksiyonunu maksimize/minimize etme ve birden çok kısıt içerme),
  programlama dilleriyle çözüldüğünde düşük seviyeli uygulama ayrıntıları yüzünden zordur; ancak kısıt çözücüler için uygundur
• Örneğin, aşağıdaki türde çeşitli problemler buna girer

Örnek 1: Maksimum hisse senedi kârı problemi

• "Liste halinde verilen hisse fiyatları verisinde, bir kez alıp daha sonra satarak elde edilebilecek maksimum kârı bulun"
  • Geleneksel olarak O(n²) brute force ya da O(n) optimal algoritma gerekir
  • MiniZinc'te bu, aşağıdaki gibi basit bir kısıt problemi olarak tanımlanabilir

    array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    var int: buy;
    var int: sell;
    var int: profit = prices[sell] - prices[buy];
    
    constraint sell > buy;
    constraint profit > 0;
    solve maximize profit;
    

Örnek 2: Belirli sayıların toplanması/çıkarılmasıyla 0 elde etmek (tatmin problemi)

• "Bir listedeki üç sayıyı toplayarak veya çıkararak 0 elde etmek mümkün mü?"
  • En iyi değeri değil, yalnızca tatmin edilebilir bir çözüm bulmak yeterlidir
  • Kısıt çözücüde şu şekilde ifade edilebilir

    include "globals.mzn";
    array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    array[index_set(numbers)] of var {0, -1, 1}: choices;
    
    constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
    constraint count(choices, -1) + count(choices, 1) = 3;
    solve satisfy;
    

Örnek 3: Histogramda en büyük dikdörtgen alanı

• "Çubuk yükseklikleri verilen bir histogramda oluşturulabilecek en büyük dikdörtgen alanını bulun"
  • Geleneksel olarak karmaşık algoritmalar ve çok sayıda durum yönetimi gerekir
  • Çözüm yalnızca kısıtlarla özlü biçimde anlatılabilir

    array[int] of int: numbers = [2,1,5,6,2,3];
    
    var 1..length(numbers): x; 
    var 1..length(numbers): dx;
    var 1..: y;
    
    constraint x + dx <= length(numbers);
    constraint forall (i in x..(x+dx)) (y <= numbers[i]);
    
    var int: area = (dx+1)*y;
    solve maximize area;
    
    output ["(\(x)->\(x+dx))*\(y) = \(area)"]
    

Kısıt çözücü yaklaşımı daha mı iyi?

• Mülakat ortamında zaman karmaşıklığı gibi sorular karşısında zayıf kalabilir

  • Kısıt çözücülerin çalışma süresini öngörmek zordur ve genellikle özel tasarlanmış optimal algoritmalardan daha yavaştır
  • Ancak kötü uygulanmış düşük kaliteli bir algoritmadan yine de daha iyidir; ayrıca çoğu programcı için her seferinde en iyi çözümü sıfırdan yazmak kolay değildir

• Asıl güçlü yön, yeni kısıtlar eklerken sağlanan esnekliktir

  • Örneğin, hisse senedi örneğinde yalnızca bir kez değil birçok kez alım satım yapacak şekilde değiştirmek istendiğinde algoritmanın karmaşıklığı hızla artar
  • MiniZinc'in kısıt modelinde ise çok küçük kod değişiklikleriyle çok daha karmaşık gereksinimler karşılanabilir

    include "globals.mzn";
    int: max_sales = 3;
    int: max_hold = 2;
    array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    array [1..max_sales] of var int: buy;
    array [1..max_sales] of var int: sell;
    array [index_set(prices)] of var 0..max_hold: stocks_held;
    var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);
    
    constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
    constraint profit > 0;
    
    constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
    constraint alldifferent(buy ++ sell);
    solve maximize profit;
    
    output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];
    

• Çevrimiçi kısıt problemi örnekleri genellikle Sudoku gibi bulmacalara odaklansa da, gerçekte iş mantığı veya optimizasyon gereksinimi olan problemlerde daha ilginç ve pratik şekilde kullanılabilir

  • Örneğin symmetry breaking (simetri kırma) gibi ileri optimizasyon tekniklerini uygulama potansiyeli de yüksektir

Kapanış ve notlar

• Bu yazı, yazarın haftalık bülteninden alınmıştır ve yazılım tarihi, biçimsel yöntemler, yeni teknolojiler, yazılım mühendisliği teorisi gibi konuları ele alır
• İlgileniyorsanız abone olabilir veya yazarın ana web sitesine göz atabilirsiniz
• Yazarın yeni kitabı "Logic for Programmers" da yayımlanıyor

[kohs100]

Genelde algoritma problemlerinde zaman/bellek karmaşıklığı şartları olmaz mı? Bunu bir kısıt çözücüyle çözebilmek aslında esasen problemi kısıt ifadelerine dönüştürme becerisini göstermekten ibaret ama... bunun gerçekten sahada gerekli bir beceri olup olmadığından pek emin değilim...

[GN⁺]

Hacker News görüşü

• Leetcode tarzı mülakat sorularındaki en büyük sorun, ek açıklama isteyememek; benim düşünme biçimim yaygın olandan farklı olduğu için Leetcode daha çok doğru cevapları ezberlemeye dayanıyormuş gibi geliyor. Yeterli bağlamı olan sorular gerçekçi bir anlayış kurabildiğim için sorun olmuyor ama çoğunda açıklama yetersiz kaldığından problemi doğru düzgün kavrayamıyorum. Bu yüzden artık Leetcode ya da yapay zeka destekli otomatik mülakat aşamalarını en baştan reddediyorum. Ödev, 1:1 veya ekran paylaşımıyla yapılan görüşmeler benim için sorun değil. Leetcode sitesinde düzgün açıklamalar ve cevaplar olsa kendi kendine çalışmak da çok daha kolay olurdu ama gerçekte fazlasıyla zor. Bu sadece yetenek meselesi değil; düşünme tarzımla soru tipinin uyumsuzluğu. Soru da soramadan sürekli çoktan seçmeli sorular çözmek, başarısız olman için tasarlanmış bir sistem gibi geliyor. Özellikle ön mülakat için kullanılan AI/Leetcode tarzı sorulardan bahsediyorum; gerçek bir insanın olduğu, soru-cevap akışının bulunduğu mülakat ortamlarını ise gayet olumlu buluyorum

  • LC (Leetcode) mülakatı, sanki çalışılmış 100 metre sprint hızını ölçmek gibi; gerçek iş ise defalarca durup devam edilen uzun bir maratona benziyor. Yine de bugün SMEGMA gibi büyük şirketlerde yüksek maaş almak istiyorsan bu oyunu oynaman gerekiyor. Örneğin ben kendi 2D oyun motorumu yaptım ama birkaç LC hard sorusunu takla ata ata çözmeni bekleyen bir LC mülakatını geçebileceğimi sanmıyorum. Bunu artık kabullendim. Yaptığım motor

  • Her şey çözüm ezberlemekten ibaret değil; ezberlesen bile ek sorularda tıkanabilirsin. Ama ezberlemiş halde ek soruları da iyi çözüyorsan, Leetcode tarzı sorularda bir sorun yok demektir diye düşünüyorum. Problem çözme becerisi bir tür örüntü eşleştirme yeteneği ve ne kadar çok örüntü bilirsen o kadar iyi problem çözersin. Artık GPT soruları da çözüp açıklamasını da yaptığı için bu beceriyi edinmek daha kolay; bundan sonra da olsa öğrenmek daha iyi olur bence

  • Buna gerçekten çok katılıyorum. Ben de yakın zamanda bir mülakatta ödevden en yüksek puanı aldım, mühendisler ve CEO da çok olumlu baktı ama CTO aniden canlı kodlama mülakatı yaptı ve sonunda elendim. 11 haftalık mülakat süreci boşa gitmiş oldu. Bu aptal sürecin hâlâ sürüyor olması sinir bozucu. Yaptığım demo/ödev: burada Monumental bağlantısı ve çıktı, GitHub kodu

  • Net soru soramamak aslında ölçmek istedikleri beceri değil mi diye düşünüyorum; adayın problem çözerken nasıl yaklaştığını görmek. Eğer insanları sadece kesin yargılarla yaklaşmaya zorlarsan, tüm yazılımlar daha karmaşık ve daha dağınık hale gelir. Asıl zor olan kod satırı yazmak değil, problemi çözme sürecidir

  • Benim mülakat yaptığım yerlerde bir iki LC sorusu verseler bile açıklama istenince hemen gerçek zamanlı konuşma ve kodlama formatına geçiliyordu. Bunun tek dezavantajı, canlı kodlamanın psikolojik baskısının daha yüksek olması

• Böyle mülakat soruları alınca, senden kısıt çözücü 'kullanmanı' değil, o sınırlı probleme uygun bir kısıt çözücüyü 'kendin yazmanı' istiyorlarmış gibi geliyor

  • Evet, bu yüzden bu mülakat yaklaşımının temelden sakil olduğunu düşünüyorum. Gerçek mühendislikte kahve içip makale okur, kütüphaneye bakar, yürüyüşe çıkıp düşünür ve mevcut araçlara (kısıt çözücü ya da LLM gibi) başvurarak problemi %100 çözebilirsin. Ama mülakat ortamında %0 bile çözemeyecekmişim gibi hissediyorum. Böyle mülakat yapan bir yere girmeyi hiç istemedim

  • Bence de öyle. NP problemlerinin çoğu kısıt problemine dönüştürülebilir. Gerçekte kısıt çözücünün doğru cevap olup olmayacağı uygulama alanına göre çok değişir ve mülakat ortamında neredeyse hiç doğru cevap değildir. Böyle çözücüler basit bir dinamik programlamadan çoğu zaman çok daha yavaş olur

  • Bazı şirket mülakatlarında bu doğru olabilir ama her yerde değil. Genel olarak LC'nin mülakatta kullanılmasının çoğu zaman tek bir nedeni vardı: verimsiz işe alım süreçleri. Sürecin içindekiler bile sistemin değişmesi gerektiğini biliyor ama ya güçleri yok ya da fazla dağınıklar. Büyük şirketlerde HR, 'standartlaştırma' adına aynı soruları farklı takımlara dolaştırıyor; küçük şirketlerde ise ekiplerin kendi sorularını hazırlayacak zamanı olmadığından internetten alıyorlar. Böyle yerlerde teknik mülakatçılar bile LC mülakatlarına eleştirel yaklaşıp gerçekten öne çıkan adayları bulmaya çalışıyor. Bu ortamda kısıt çözücülere ilgin ya da bilgin olduğunu göstermek bile çoğu zaman oldukça iyi puan getiriyor

  • Biri bir LC hard sorusunu kısıt çözücüyle çözmüşse ve sen o kişiyi işe almıyorsan, o durumda aptal olan mülakatçının kendisidir. Kısıt çözücünün ne olduğunu bilip problemi tanımlayarak kullanabilen insan zaten çok nadir. Ben de üçüncü sınıfta kullanmıştım ve sadece kısıt ifadelerini yazmak bile baş ağrıtacak kadar karmaşıktı

  • Bu kısmen doğru, kısmen yanlış. Mülakatta buna benzer sorular sordum; aday kısıt çözücüyü aklına getirdiyse yüksek puan veriyordum. Gerçek mühendislikte kısıt çözücüler hem küçümseniyor hem de birinin doğru cevabı hızlıca üretebildiğini göstermenin iyi bir işareti olabiliyor. Tabii ardından gerçek kodlama becerisini ölçmek için beyaz tahta tarzı devam soruları da sorardım. Ama cevap olarak kısıt çözücü önermek başlı başına kötü bir şey değil

• Güzel bir içgörü ama gerçek mülakatlara pek uymadığını düşünüyorum. Bu soruların özü, adayın 'kafa yorma' becerisini ölçmek. Sadece kısıt olarak çözmek, daha çok deneyim ve bilgi seviyesini gösterir; "gerçekten düşündü mü" kısmını pek göstermiyor

  • Mülakatçılar sık sık Leetcode 'Top Interview 150' içindeki "Array String" sorularını soruyor. Benim gibi backend Python geliştiricisi açısından bu sorular günlük işle pek alakalı gelmiyor. Çoğu, in-place array işlemleri algoritmaları istiyor; bunlar da genelde ancak C ya da Rust gibi performans odaklı dillerde anlamlı oluyor. Buna karşılık "Hashmap" tipi sorular, dile uygun araçları nasıl kullandığını göstermede daha faydalı. Ayrıca zorluk ayarı da çoğu zaman bozuk; örneğin "kolay" etiketi taşıyan bazı sorular (Majority Element gibi) aslında Boyer–Moore gibi tarihsel bir algoritmayı bilmeyi gerektiriyor ve pek de kolay sayılmaz

  • Meta'da yakın zamanda gördüğüm son tur, tamamen kendi özel soru tiplerini ne kadar tekrar edip ezberlediğini ölçmeye dönüktü. Bu yüzden ders kitabı cevabından farklı bir cevap verirsen aksine şaşırıyorlar. "Zekice düşünme"nin kendisi çok da önemli değilmiş gibi geliyor

  • Bottom-up DP algoritmaları belli ölçüde kafa çalıştırmayı gerektirir ama çoğu problem top-down yaklaşımla (özyineleme + memoization) çözülebilir. Örneğin coin change problemi A* aramayla daha iyi çözülebilir. Ama pratikte çoğu programcının bu algoritmaları gerçekten kullanması neredeyse hiç gerekmez. Asıl önemli olan, yanlışlıkla zaman karmaşıklığı O(n^2) olan kod yazdığını fark edebilmek. accidentallyquadratic.tumblr.com sitesine bakarsan, ünlü projelerdeki yetenekli insanlar bile bu hatayı sık yapıyor. Yani bir testte algoritma üretme becerisi, gerçek işte algoritmik hataları yakalama becerisinden ayrı bir şey

  • Ben mülakatta problem çözme becerisini değerlendirirken düşünce sürecine, iletişim tarzına ve problemi parçalara ayırmaya önem veriyorum. Zorluk seviyesi ayarlanabilir sorular hazırlayıp her adayın kendi yeteneğini gösterebilmesine fırsat vermek çok daha önemli. Birinin aklına gelen ilk cevabı anında söylemesi ya da uzun süre tıkanması, mülakatçı açısından aslında çok da fazla şey göstermez. Bu yüzden problem çözme odaklı mülakat soruları çok faydalı olabilir ama pratikte iyi kullanılmıyor olmaları üzücü

  • Bu sorular gerçekten de 'zekâ'yı değil, yaklaşık 12 kadar kalıplaşmış deseni ne kadar ezberlediğini ölçüyor. Neredeyse tüm adayların sonucu, yaratıcı problem çözmeden çok hazırlanmış ezber düzeyine bağlı oluyor. LeetCode soruları o kadar oyunlaştırıldı ki, artık daha çok hazırlanma isteğini ölçen bir araç gibi hissettiriyor

• Çoğu mülakat sanki 'eğer diyabet hastası evde kendi insülinini sentezleyemiyorsa hayat oyununda hile yapıyordur' varsayımıyla soru soruyor. Eşimin kan şekeri yükselince insülin kullanması gibi, bu bir kısıt problemi ise çözücü kullanmak gerekir. Şirket kısıt çözücü yazılımı üreten bir yer değilse, neden özellikle 'böyle bir yazılım yokmuş' varsayımıyla her şeyi sıfırdan yeniden yapmanı istediklerini anlamıyorum

  • Esas mesele, kriz anında insülin sentezleme becerisini değil; bir hafta içinde ders notlarını ezberleyip telefon mülakatında düzgünce tekrar edebilmeni ölçen bir ön eleme yetenek testi olması

  • Kısıt çözücüyle verimli çözüm bulabiliyorsan, iki tane for döngüsü ve yardımcı bir özyinelemeli fonksiyonla da oyuncak problemleri zaten rahatça çözersin

  • (anlamlı içerik yok)

  • Kodlama testlerini savunmak gerekirse, çoğu basit DP problemini bile çözemeyen kişiler gerçek işte de çoğunlukla yetersiz çıkıyordu. Elbette istisnalar vardır ama benim deneyimim bu yönde

• Kısıt programlama dilleri konuşulunca Håkan Kjellerstrand'dan mutlaka söz etmek gerekir. MiniZinc dahil çok sayıda örnek ve problem içeren harika bir site yürütüyor: hakank minizinc

  • Ve o sadece iyi bir web sitesi yapan biri değil, gerçekten son derece nazik bir insan

• Çok uzun zaman önce, üniversitede bilgisayar mühendisliği okurken kısıt çözücüleri henüz öğrenmemiş toy biriyken, bir arkadaşım benden spor kulübü için takvim planlayan bir uygulama yapmamı istemişti ve bu problemle orada karşılaştım. İlk başta kolay görünüyordu ama denemeye başlayınca aslında ne kadar büyük bir probleme girdiğimi fark etmemiş olduğumu anladım. Sonradan bu, kibirim için iyi bir ders oldu; o deneyim sayesinde bugün takvim/süre/beklenti konuşmalarında çok faydasını görüyorum

  • Acemi bir soru olabilir ama kısıt çözücü yerine 'doğrusal optimizasyon' ile daha kolay çözülemez miydi diye merak ediyorum. Kendi deneyimime göre doğrusal optimizasyonun avantajı, kurallar arasındaki çatışmaları ağırlıklarla ele alıp en az 'yan etki' oluşturan çözümü bulabilmesi

  • 25 yıl önce lise zamanında, TI-Basic ve VB6 öğrenmeye yeni başlamışken, hamburgercide yarı zamanlı çalışıyordum. Müdürün her hafta personel vardiyasını hazırlamanın ne kadar zor olduğundan yakındığını duyunca "Ben bilgisayardan anlıyorum, size bir vardiya programı yapayım!" demiştim. Sonra bir çizelgeleyici yazmanın ne kadar zor olduğunu anlayıp hemen vazgeçtim

• "Yazarın demek istediği şu: böyle bir soruyu mülakatta sorarsan ve aday 'bu algoritmanın çalışma zamanı karmaşıklığı nedir?' diye sorarsa elinde cevap kalmaz." Yani kısıt çözücü de yeterince hızlı çözmüyorsa Leetcode hard sorusunun çözümü sayılmaz. Çalışma zamanı gereksinimi rahatsa basit yöntemler de iş görebilir ama verimli çözümü bulmak zaten toplam meydan okumanın büyük kısmı

  • Gerçek hayatta her zaman 'en verimli çözüm'den çok, 'yeni gereksinimlere hızlı uyum sağlayan çözüm tasarlama' ihtiyacı öne çıkıyor. Bu yüzden gerçek dünyadan kopuk verimlilik ölçütleriyle yapılan mülakatların ne kadar anlamlı olduğu tartışılır; tabii role göre değişebilir. Yazarın, en verimli çözümün her zaman gerçek iş becerisini yansıtmadığı görüşüne katılıyorum. Leetcode eleştirisinin bir boyutu da bu. Aynı probleme 'yeni gereksinimlere ne kadar esnek uyum sağlıyorsun' açısından bakmak daha nesnel olabilir

• Kısıt çözücü mü? Güzel fikir, duydum da; ama mülakatta gerçekte istedikleri şey, bunu Python'da doğrudan implemente ederken düşünce akışını görmek. (Mülakatta kısıt çözücü kullanmayı kabul ettirmenin neredeyse imkânsız olduğunu düşünüyorum)

  • Bunu gerçekten bir mülakatçıya söyledin mi, yoksa sadece tahmin mi ediyorsun merak ettim

  • import z3

• DP (dinamik programlama) ile çözüp sonra da "şimdi bunu bir de kısıt çözücüyle yapayım" dersen anında işe alınırsın

  • +1

• Kısıt çözücülerin gerçek gücü, 'yeni gereksinimlere' ne kadar kolay uyum sağlayabildikleri. Ben de Google'da veri merkezi optimizasyonu yaparken, bu tür genelleştirilmiş çözücülerin gereksinim değişikliklerine esnek uyum sağlama avantajını büyük ölçüde yaşadım