Bugün erken saatlerde size yazılım mühendisleri için klasik bir röportaj sorusu olan aşağıdaki bulmacayı hazırladım. Gerçekten hayal gücünüzü yakalamış gibi görünüyor: şu ana kadar orijinal makaleye neredeyse 500 çizgi altı yorum yapıldı. Birçoğu sorunu yanal olarak ele alıyor ve çoğunlukla da esprili. Birçoğu, fantezi ortamında veri yapılarıyla ilgili teknik bir soruyu ifade ederken ortaya çıkan belirsizlikler üzerine yapılan meditasyonlardır. Bazıları neyin spoiler olduğuna dair öfkeli gönderiler, bazıları ise en sevdiğiniz yazılım mühendislerini kutlamak.
Yeter artık, işte bulmaca, çözümüyle birlikte.
Döngüsel labirent
Karanlık bir yeraltı tünelinde mahsur kaldınız. Dairesel bir yolda sonsuz bir şekilde kıvrıldığını biliyorsunuz ama ne kadar uzun olduğunu bilmiyorsunuz. Tünelin duvarları boyunca eşit ve düzenli aralıklarla yerleştirilmiş anahtarlar iki konum arasında değiştirilebilir: yukarı veya aşağı. Bunun dışında tünelde başka hiçbir nesne yoktur ve tünel boyunca yürüdüğünüzde dairesel yolun eğrilik oranı hakkında hiçbir sonuç çıkaramazsınız. Ancak bir kaleminiz, kağıdınız ve bir okuma ışığınız var, böylece sayıları not edebilirsiniz.
Tüneldeki anahtarların sayısını nasıl sayarsınız?
Açıklama: Giysilerinizi veya eşyalarınızı yere düşürmenize izin verilmez.
Çözüm
Yol daireselse, tünel bir daire çizer ve dolayısıyla uzunluğu sonlu olmalıdır. Sonunda başladığınız yere geri döneceksiniz. Sorun, bir döngüyü tamamladığınızda nasıl çalışacağınızdır, çünkü tünelin her bölümü aslında bir sonrakinden ayırt edilemez.
Bölümleri saymanıza yardımcı olabilecek şeyler duvarlardaki anahtarlardır. Bir fikir, hepsi “aşağı” olana kadar tüm anahtarları “aşağı” konuma getirerek yürümek ve ardından onları “yukarı” çevirmeye başlamak ve “yukarı” çevrilmiş olana geri dönene kadar saymak olabilir. Eğer hepsinin “aşağı” olduğundan emin olursanız bu işe yarayacaktır. Ancak asla başlangıca döndüğünüzden emin olamazsınız. Bildiğiniz gibi daire çok büyük; 1000 düğmeyi “aşağı” konumuna çevirebilir ve daha sonra 1000 “aşağı” düğmesinin yanından geçebilirdiniz. İki döngü yapmışsınız gibi görünebilir, ancak belki de tünelde 2001 anahtar vardır.
İlk “aha” anı, yaptığınız tek şey ilerlemekse bu bulmacayı çözemeyeceğinizi fark etmenizdir. Geri adım atmalısınız.
Stratejilerden biri şudur: Başlatma anahtarını “yukarı” konuma getirin ve ardından saymaya devam edin ve düğmelerin “aşağı” olduğundan emin olun, ancak “yukarı” olan bir düğmeye bastığınız anda geriye doğru gitmeniz ve bunu yaptığınızdan emin olmanız gerekir. başlangıca geri dönmedim. Bunu yapmak için, yakın zamanda karşılaşılan “yukarı” anahtarını “aşağı” konumuna getirin ve başlangıca geri dönün. Sayımı tutuyorsunuz, dolayısıyla başlatma düğmesine geri dönmek için ne kadar geriye gitmeniz gerektiğini biliyorsunuz. Hala “yukarı” ise, bir daire içine girmemişsinizdir ve şimdi aynı işleme yeniden başlayabilirsiniz. Ancak “aşağı” ise, başlatma anahtarı az önce değiştirdiğiniz anahtar olmalıdır ve bir daire çizdiğinizden emin olabilirsiniz. Bu aşamaya geldiğinizde tüm anahtarları saydınız.
Sayesinde Brian RabernEdinburgh Üniversitesi Felsefe Okuyucusu, “Bulmacalar ve Paradokslar” dersinde kullandığı bu bulmacayı önerdiği için.
Eğer soruyu bir kodlama problemi olarak sorsaydı, şöyle bir şey olacağını söyledi:
Her biri bir Boole değişkenine sahip olan nesneleri içeren dairesel bağlantılı bir liste düşünün. Göreviniz dairedeki toplam nesne sayısını belirlemektir. İşin püf noktası, geçerli nesnenin Boolean değişkenini yalnızca True veya False olarak değiştirebilmeniz ve listedeki sonraki veya önceki nesneye geçebilmenizdir. Boolean değerini değiştirmenin ötesinde hiçbir referansa, işaretlemeye veya değişikliğe izin verilmez. Ayrıca nesneleri saymanıza ve boolean alanlarının değerlerini hatırlamanıza da izin verilir. Listedeki boole değişkenlerinin başlangıç değerleri isteğe bağlıdır. Bu kısıtlamalar altında dairesel bağlantılı listedeki nesnelerin sayısını verimli bir şekilde nasıl sayarsınız?
Meslekten olmayan okuyucu için bir bulmaca olarak ayarlandığında belirsizliklerin nasıl ortaya çıktığını görebilirsiniz!
Umarım bugünkü bulmacayı beğenmişsinizdir. İki hafta sonra döneceğim.
2015’ten bu yana dönüşümlü olarak Pazartesi günleri burada bulmaca hazırlıyorum. Her zaman harika bulmacalar arayışındayım. Bir tane önermek isterseniz bana e-posta gönderin.
