Sızan ve yasaklanan bir Google röportaj sorusu, arkasındaki sır tamamen çözüldü
Yazar | Alex Golec
Çevirmen | Xue Ming Deng
Önüne yaz
Sorumluluk Reddi Beyanı: Google'da bir mühendis ve görüşmeci olarak, adaylarla görüşme yapmak görevlerimden biridir. Bu makale sadece benim kişisel deneyimimi ve görüşlerimi temsil ediyor. Lütfen yanlışlıkla Google, Alphabet veya diğer kişi veya kuruluşların herhangi bir resmi beyanıyla ilişkilendirmeyin.Bu, mülakat kariyerimde kullandığım ilk mülakat sorusu ve sızdırılan ve yasaklanan ilk mülakat sorusu. Bu röportaj sorusunu çok beğendim çünkü birçok ilginç yeri var:
- İfade etmesi ve anlaması kolaydır.
- Her biri farklı derecede algoritmalar ve veri yapıları bilgisi gerektiren birçok çözüme sahiptir.
- Her çözüm, nispeten az sayıda kod satırı ile uygulanabilir ve bu, yoğun zaman alan görüşme senaryoları için çok uygundur.
Öğrenciyseniz veya teknik bir işe başvuruyorsanız, mülakat sorularını daha iyi anlamak beklentisiyle bu makaleyi okuyabileceğinizi umuyorum. Görüşmeci iseniz, düşünme sürecimi ve görüşme yöntemlerimi paylaşmak, geri bildirim ve öneriler almak isterim.
Python'da kod yazacağım. Python'u seviyorum çünkü öğrenmesi kolay, kompakt ve geniş bir standart kitaplığa sahip. Adaylar da hoşuna gitti: Aslında dil kısıtlaması yapmadık, ancak görüştüğüm adayların% 90'ı Python kullanıyor. Ben de Python 3 kullanıyorum sonuçta 2018.
Görüşme soruları
Şövalyeyi telefon kadranına koyduğunuzu hayal edin. At büyük "L" şeklinde hareket eder: iki yatay adım, ardından bir dikey adım veya bir yatay adım, ardından iki dikey adım:
Şövalye ayak hareketine göre klavyedeki tuşlara bastığınızı varsayalım. At bir düğmenin üzerine düştüğünde, o düğmeye basıyoruz ve ardından bir sonraki atlamaya devam ediyoruz. Başlangıç pozisyonu basılmış olarak işaretlenir.
Belirli bir konumdan başlayarak, N atlama içinde kaç farklı numara aranabilir?
Tartışma
Röportajım temelde iki bölüme ayrılıyor: İlk olarak bir algoritma çözümü bulacağız ve ardından aday bunu uygulamak için kodu kullanacak. "Biz" dememin bir çözüm bulmasının nedeni, ağzım kapalı bir seyirci olmamam: en iyi durumda, 45 dakika içinde bir algoritma tasarlamak ve uygulamak çok uzun değil, henüz değil Röportajın baskısını hesaba katın. Adayların tartışmalarımıza liderlik etmesine, fikir üretmesine ve sorunları çözmesine izin veriyorum ve ayrıca onlara bazı ipuçları vermekten mutluluk duyuyorum. Aday ne kadar iyiyse, o kadar az ipucu veriyorum, ancak bahşişlerime hiç ihtiyaç duymayan bir aday görmedim.
Bir şeyi vurgulamalıyım çünkü bu çok önemli: Bir görüşmeci olarak oturup adayların başarısız olmalarını izlemiyorum. Adaylara mümkün olduğunca çok olumlu geri bildirim sağlamak istiyorum, sanki "Size küçük bir ipucu vereceğim, böylece bana sorunun geri kalanını anladığınızı göstermeye devam edebilirsiniz."
Mülakat sorularını dinledikten sonra ilk tepkiniz beyaz tahtaya gidip küçük ölçekli problemleri çözmeye başlamaktır. Acele kod yazmayın! Küçük ölçekli problemleri çözerek, kalıpları ve sınır koşullarını bulabilir ve zihninizde çözümler oluşturmanıza yardımcı olabilirsiniz. Örneğin, 6'da başladığınızı ve iki kez atlamanız gerektiğini varsayalım. Numara diziniz ...
- 618
- 616
- 672
- 676
- 604
- 606
Toplamda altı sekans var. Bu dizileri kalem ve kağıt kullanarak yazmaya çalışabilirsiniz. Makalede iyi ifade edilmemiş olabilir, ancak inanın bana, sadece ona bakmak veya sessizce düşünmek yerine sorunları elle çözerek daha fazla fikir edinebilirsiniz.
Her iki durumda da, aklınızda zaten bir çözüm olabilir. Ama ondan önce...
Seviye 0: Sonraki atlama
Bu mülakat sorusunu kullanmaya başladığımda, adayların belirli bir pozisyondan atlayabilecek anahtarları (yani komşular) nasıl sayacakları sorusuna sık sık takılıp kalmalarına şaşırdım. Benim önerim şu: Herhangi bir sorunuz varsa, önce boş bir yer tutucu koyabilir ve görüşmeciye daha sonra geri gelip çözemeyeceğinizi sorabilirsiniz. Bu sorunun karmaşıklığı komşuları saymakla ilgili değil, benim ilgilendiğim şey adayın tüm sayıları nasıl hesapladığı. Komşuları saymak aslında zaman kaybıdır.
"Tüm komşuları döndüren bir işlev olduğunu varsayalım" kabul edebilirim. Elbette, daha sonra uygulamak için geri gelmenizi isteyebilirim, ancak yalnızca zamanımız olursa. Bunun gibi boş bir işlev yazıp devam edebilirsiniz:
def komşular (pozisyon): ...İşlev saplamalarını kullanmak istersen, sorun değil, yani çok fazla puan kaybetmeyeceksin: Eğer sorunun karmaşıklığı başka bir yerde bulunuyorsa, buna izin vereceğim. Aksi takdirde, sizden onu uygulamanızı isteyeceğim. Adayların sorunun karmaşıklığının farkına varmamaları umurumda değil, çünkü başlangıçta sorunu tam olarak keşfetmemiş olabilirler.
Tüm komşuları döndüren işleve gelince, bunun asla değişmeyeceğini varsayıyoruz. Basitçe bir harita oluşturabilir ve uygun değeri döndürebilirsiniz:
NEIGHBORS_MAP = { 1: (6, 8), 2: (7, 9), 3: (4, 8), 4: (3, 9, 0), 5: tuple (), # 5 komşu yok 6: (1, 7, 0), 7: (2, 6), 8: (1, 3), 9: (2, 4), 0: (4, 6), } def komşular (pozisyon): NEIGHBORS_MAP'e dönSeviye 1: Yinelemeli olarak sayılar oluşturun
Şimdi çözüme geri dönelim. Fark etmiş olabileceğiniz gibi, bu sorun olası tüm sayıları sıralayarak ve bunları sayarak çözülebilir. Bu değerleri oluşturmak için özyinelemeyi kullanabilirsiniz:
def verim_sequences (başlangıç_konumu, num_hops, sıra = Yok): sıra Yok ise: sıra = num_hops == 0 ise: getiri dizisi dönüş komşulardaki komşular için (başlangıç_konumu): verim_dizilerinden elde edilen getiri ( komşu, num_hops-1, sıra +) def count_sequences (başlangıç_ konumu, sayı_sayısı): num_sequences = 0 verim_dizilerindeki dizi için (başlangıç_ konumu, sayı_sayısı): num_sequences + = 1 num_sequences döndürSorun değil ve adaylar bunu genellikle görüşmeler sırasında yapar. Ancak lütfen sayılar ürettiğimizi ancak kullanmadığımızı unutmayın. Bu soru, sayının kendisi değil, sayıların sayısını sorar. Sayıların sayısını hesapladıktan sonra bu sayıları bir daha asla kullanmayacağız. Tecrübeye dayanarak, çözümünüzün kullanılmayan şeyleri hesaplayıp hesaplamayacağına dikkat etmenizi öneririm. Genellikle daha iyi bir çözüm kullanabilirsiniz.
Seviye 2: Sayıyı saymadan sayıların sayısını alın
Telefon numarası oluşturmadan telefon numaralarını nasıl sayarız? Yapabiliriz, ancak ek algoritmalara ihtiyaç var. Belirli bir başlangıç pozisyonundan N sekme içinde üretilen sayıların sayısının hesaplanmasının, komşularının her birinin N-1 sekmelerinde üretilen sekmelerin sayısının toplamına eşit olduğuna lütfen dikkat edin. Bu yinelemeli ilişkiyi matematiksel olarak ifade etmek şuna benzer:
Yalnızca bir atlama dikkate alınırsa, bu sezgiseldir: 6'nın 3 komşusu vardır (1, 7 ve 0) Sıfır sıçramada, her komşu yalnızca bir haneye ulaşabilir, böylece yalnızca üç numarayı çevirebilirsiniz.
Bu aklınıza nasıl geldi diye sorabilirsiniz. Özyinelemeyi öğrendiyseniz, beyaz tahtaya bir resim çizerek anlayacaksınız. Özyinelemeyi anlayan birçok aday, bu sorunun daha küçük alt problemlere bölünebileceğini hemen bilir. Seninle röportaj yapıyorsam ve bunu düşünemiyorsan, genellikle aday düşünemeyene kadar ipuçları veriyorum.
Bu yöntemi düşündükten sonra sorunu çözmeye devam edebilirsiniz. Bu fikre dayalı birçok kod uygulaması var, ancak görüşmemde en yaygın olanla başlamak istiyorum - en temel yinelemeli yöntem:
komşulardan komşular ithal def count_sequences (başlangıç_ konumu, sayı_sayısı): num_hops == 0 ise: dönüş 1 num_sequences = 0 komşulardaki konum için (başlangıç_konumu): num_sequences + = count_sequences (konum, num_hops-1) num_sequences döndür __name__ == '__ main__' ise: baskı (sıra_sayısı (6, 2))Bu kodu komşuları hesaplama işlevi ile birleştirin ve uygulanabilir bir çözüme sahipsiniz! Şu anda, kendinize bir beğeni vermelisiniz. Daha derine inmeye devam ederseniz, hala çözmemiz gereken birçok sorun olduğunu göreceksiniz, ancak şimdi bir kilometre taşına ulaştığımız söylenebilir. Bu çözümü bulmak sizi şimdiden öne çıkarabilir.
Sonraki soru şudur: Bu çözümün Big-O karmaşıklığı nedir? Birisi Big-O'nun ne olduğunu bilmiyorsa, algoritmanın gerektirdiği hesaplama miktarının girdinin boyutuna göre değiştiği oranın (gayri resmi olarak) basit bir temsilidir. Bu mülakat sorusu için, girdinin boyutu atlama sayısıdır.
Yukarıdaki uygulama için, her count_sequences () çağrısı, her anahtarın en az iki komşusu olduğu için count_sequences () öğesini en az iki kez özyinelemeli olarak çağıracaktır. Yinelediğimiz zamanların sayısı gereken atlama sayısına eşit olduğundan ve count_sequences () öğesine yapılan çağrıların sayısı en az iki katına çıktığından, çalışma zamanı karmaşıklığı en azından üsseldir.
Böyle bir performans korkunç. Her ek atlama için, işletim karmaşıklığı en az ikiye katlanacaktır. 1'den 20'ye kadar az sayıdaki atlama için kabul edilebilir, ancak daha fazla sayıda atlama için işe yaramayacaktır. Örneğin, atlama sayısı 500 ise, maymun yılına kadar nasıl sayacağımı bilmiyorum.
Seviye 3: not alma
Daha iyisini yapabilir miyiz? Sadece yukarıdaki matematiksel ilişkiyi kullanmak mümkün değildir. Ancak bu mülakat sorusunu seviyorum çünkü daha etkili çözümlerle çözülebilir. Bir sonraki çözümü bulmak için önce fonksiyon çağrısı yapısını çiziyoruz. Önce count_sequences (6,4) durumunu ele alalım. İşlev adı için C kullandığımı unutmayın:
Tuhaf bir şey fark edebilirsiniz: C (6,2) üç kez çağrılır ve her seferinde aynı hesaplamayı yapıp aynı değeri döndürür. Dolayısıyla bu işlev çağrıları tekrarlanır ve her seferinde aynı değeri döndürür. Bir sonucu hesapladıktan sonra, onu yeniden hesaplamaya gerek kalmamalıdır.
Bunu nasıl düşüneceğinizi öğrenmek istiyorsanız, en kolay yol bir beyaz tahta kullanmaktır: soruna sadece bakmak iyidir, ancak adayları her zaman beyaz tahtaya örnek çözümler çizmeye teşvik ederim. Ağaç yapısını yukarıdaki gibi çizin ve içinde birden fazla C (6,2) olduğunu göreceksiniz, kesinlikle fark edeceksiniz. Bazen bu, adayların 1. ve 2. çözümleri tamamen atlamasına ve buraya atlamasına izin vermek için yeterlidir. 45 dakikalık bir röportajda, bu şüphesiz size çok değerli zaman kazandıracaktır.
Peki, bundan sonra bu sorunu nasıl çözeceğiz? Memoization (ezberleme değil) kullanabiliriz; bu, daha önce gördüğümüz işlev çağrılarının sonuçlarını kaydetmemiz ve sonuçları yeniden hesaplamak yerine bunları yeniden kullanmamız gerektiği anlamına gelir. Çağrı grafiğinde alt ağacın tamamını yeniden hesaplamaya gerek olmayan bir konumla karşılaştığımızda, hemen önceden hesaplanan sonucu döndürürüz. Bu bir uygulamadır:
def count_sequences (başlangıç_ konumu, sayı_sayısı): önbellek = {} def helper (konum, num_hops): önbellekte if (position, num_hops): önbelleği döndür num_hops == 0 ise: dönüş 1 Başka: num_sequences = 0 komşulardaki komşular için (pozisyon): num_sequences + = yardımcı (komşu, num_hops-1) cache = num_sequences num_sequences döndür res = helper (başlangıç_konumu, num_hops) dönüş resPeki mevcut çalışma zamanı karmaşıklığı (Big-O) nedir? Buna cevap vermek zor. Önceki uygulama için, çalışma zamanı karmaşıklığını hesaplamak, özyinelemeli işlevin kaç kez çağrıldığını hesaplamak kadar basittir ve her çağrı her zaman iki ila üç defa olur. Şimdi, hesaplamaların sayısı daha karmaşıktır, çünkü özyinelemeli çağrı koşullarla sınırlandırılmıştır. Yüzeyde, işlev çağrılarının sayısını saymanın net bir yolu yoktur.
Bu gizemi önbelleği kontrol ederek çözebiliriz. Her işlev çağrısının sonucu önbellekte saklanır ve yalnızca bir kez eklenir. Bu nedenle soru, "Önbellek boyutu girdi boyutuyla nasıl büyür?" Haline gelebilir. Önbellek düğme konumu ve atlama sayısından oluştuğundan ve tam olarak on düğme konumu olduğundan, önbellek büyümesinin talep edilen atlama sayısı ile orantılı olduğunu düşünebiliriz. Orantılı. Bu, güvercin deliği ilkesini izler: her anahtar konumu ve atlama sayımı kombinasyonu için, önbellekte karşılık gelen bir giriş varsa, tüm çağrılar işlevi yeniden çağırmak yerine önbelleği kullanır.
Bu doğrusal zamandır! Fena değil. Basit bir önbellek eklemek, algoritmanın karmaşıklığını üstelden doğrusalya değiştirir, ki bu gerçekten harika. Eski MacBook Air'imde, yinelemeli uygulamanın 20 atlamayı çalıştırması yaklaşık 45 saniye sürerken, yeni uygulama yaklaşık 50 milisaniyede 500 atlamayı işleyebilir. Hiç de fena değil.
Yani elimizden gelenin en iyisini yaptık mı? Henüz değil. Bu çözümün iki dezavantajı vardır. Biri, özyinelemeli olmasıdır. Çoğu dil çağrı yığınının boyutunu sınırlar, bu da her uygulamanın destekleyebileceği maksimum atlama sayısında bir üst sınır olduğu anlamına gelir. Makinemde yaklaşık 1000 atlamada başarısız oldu. Bununla birlikte, herhangi bir özyineleme yineleme olarak uygulanabilir, ancak zahmetlidir. Başka bir eksikliğe gelince, bir sonraki çözüme yol açacaktır ...
Seviye 4: Dinamik programlama
Önceki özyinelemeli ilişkiye bakarsanız, özyinelemeli bellek çözümünün eksikliklerinin bariz olduğunu göreceksiniz:
Lütfen N atlama sonucunun yalnızca N-1 atlama çağrılarının sayısına bağlı olduğunu unutmayın. Aynı zamanda, önbellek her (sıfır olmayan) atlama sayısını içerir. Bunun küçük bir sorun olduğunu düşünüyorum çünkü aslında herhangi bir gerçek soruna neden olmuyor çünkü önbellek yalnızca atlama sayısıyla doğrusal olarak büyüyor. Bununla birlikte, doğrusal uzay kullanımı dünyanın sonunu getirmese de, yine de en verimli olanı değildir.
Beyaz tahtaya fonksiyon çağrısı yapısını çizdiğinizde sonuç açıktır. Atlama sayısının en büyük özyinelemeden en küçüğe azaldığını unutmayın:
Tüm fonksiyon çağrısı grafiğini sanal bir ağaç olarak hayal ederseniz, derinlik öncelikli bir geçiş yaptığımızı göreceksiniz. Bu da uygun bir çözümdür, ancak yukarıda belirtilen sığ bağımlılıklardan yararlanmamaktadır.
Yukarıdan başlayarak ve N-1 sekme fonksiyonunu yalnızca N sekme fonksiyonunu çağırdıktan sonra çağırarak genişlik-ilk çaprazlamayı kullanmak mümkün müdür? Ne yazık ki hayır. Sıfır olmayan atlama sayısı işlevinin döndürdüğü değer, daha küçük atlama sayısının değerine bağlıdır, bu nedenle sıfır atlama sayısı düzeyine ulaşana kadar hiçbir sonuç alamazsınız.
Bununla birlikte, sırayı tersine çevirebilirsiniz: N sekme fonksiyonunu çağırmadan önce yalnızca N-1 sekme fonksiyonunu çağırın. Ayrık matematik eğitimi almış veya öğrenenler, tümevarım yöntemini bilmelidir: sıfır atlama fonksiyonunun değerinin her zaman 1 olduğunu biliyoruz. N-1 sekmelerinin değerini N sekmelerinin değeriyle birleştirmek için yinelemeli bir ilişkinin (tümevarımlı adım) nasıl kullanılacağını da biliyoruz. Sıfır atlama ile başlayabilir ve sıfırdan büyük tüm değerleri genelleyebiliriz. Bu bir uygulamadır:
def count_sequences (başlangıç_ konumu, sayı_sayısı): previous_case = * 10 current_case = * 10 current_num_hops = 1 while current_num_hops < = num_hops: current_case = * 10 geçerli_num_hops + = 1 (0, 10) aralığındaki konum için: komşulardaki komşular için (pozisyon): current_case + = previous_case previous_case = current_case current_case'i döndürÖyleyse bu sürüm özyinelemeli önce derinlik çözümünden daha mı iyi? Çok daha iyi olmayacak ama kesinlikle daha iyi olacak. Birincisi, yinelemeli değildir, yani çökmeden çok fazla sayıda atlamayı çalıştırabilir. İkinci olarak, hafızaya alma gibi önbelleğin sürekli büyümesi yerine yalnızca iki sabit boyutlu diziye ihtiyaç duyduğundan sabit bellek kullanır. Sonunda, hala doğrusal: 200.000 sıçramayı 20 saniyeden daha kısa bir sürede hesaplayabilirim.
Değerlendirme
Yani bitmeli, değil mi? neredeyse. Röportajda doğrusal zaman ve sabit uzay çözümleri tasarlamak ve uygulamak çok iyi bir sonuçtur. Dinamik programlama çözümleri sağlayabilen adaylara her zaman iyi bir değerlendirme veriyorum.
Peki ya diğer çözümler diye sorabilirsiniz. Söyleyebileceğim tek şey, soyut adayların bir değerlendirmesini yapamayacağım. Görüşme beklediğiniz gibi olmayacak Aday geç gelebilir ve gergin hissedebilirler.Genellikle daha sonraya kadar çözümler düşünürler ve kod yazmak için fazla zaman bırakmazlar. Ayrıca adayların fikirlerini nasıl ilettiklerine ve fikirleri geri bildirimlerle nasıl birleştirdiklerine de dikkat ediyorum. Adayı geçip geçmeyeceğimi önermeden önce bu faktörleri dikkate alacağım.
Algoritmaları ve veri yapılarını değerlendirirken şunu söyleyebilirim: "Aday bu sorunu araştırdı ve tüm sınır koşullarını çözebilecek bir çözüm önerdi ve eksiklikler ortaya çıktığında çözümü iyileştirdi. Sonunda, en iyisini buldular. s çözümü ". Ayrıca şunu da söyleyeceğim: "Aday, çözüm için uygun veri yapısını seçti ve çalışma zamanı karmaşıklığını ve alan karmaşıklığını doğru bir şekilde açıkladı."
Bir adayın kodlama becerisini değerlendirirken ideal ifadem şöyle olmalıdır: "Aday fikirlerini hızlı ve kısa bir şekilde koda çevirir. Kod standart bir dil yapısı kullanır ve yüksek derecede okunabilirdir. Tüm sınır koşulları dikkate alınır. , Aday, doğruluğundan emin olmak için kodu dikkatlice kontrol eder. " Giriş seviyesi pozisyonlar için, adaylar test senaryoları sağlarlarsa onlara ek ödül puanları vereceğim, ancak daha fazla deneyim gerektiren pozisyonlar için, ilgili test vakalarını listelemeyen adayları cezalandıracağım.
Mülakatın ilerleme hızıyla ilgili olarak şunu söylemek isterim: Aday problem çözme sürecini yönlendirir: kendi çözümlerini verirler ve eksiklikleri tespit edip benim yardımım olmadan iyileştirirler. Adayların sadece Birkaç ipucu problem çözme sürecini doğru yönde hareket ettirebilir. "
sonuç olarak
İşte bu röportaj sorusunda ele alınan becerilerin ve geliştirmeniz gereken alışkanlıkların bir listesi:
- Önce küçük ölçekli sorunları manuel olarak çözün. Bu röportaj sorusu için, işlev çağrısı yapısını elle canlandırdığınızda, yinelemeli ilişki ve tekrarlanan işlev çağrıları daha belirgin hale gelir.
- Sayıları oluşturmak için birincil çözüm gibi gerekli olmayan şeyleri hesaplamamaya dikkat edin, ancak bunlar gerçekte kullanılmıyor. Gereksiz hesaplamaları azaltmak genellikle daha basit bir çözüm sağlayabilir.
- Özyinelemeyi anlayın. Yineleme, çoğu üretim kodunda neredeyse işe yaramaz çünkü yığını patlatabilir, ancak çok güçlü bir algoritma tasarım stratejisidir. Özyinelemeli çözümler genellikle ayarlanabilir ve geliştirilebilir: üstel karmaşıklık çözümleri ile doğrusal optimum hafızalama çözümleri arasındaki fark aslında en küçüktür.
- Big-O'yu tanıyın! Görüşme sırasında, büyük olasılıkla bir noktada bu soru sorulacaktır.
- Her zaman hafızaya alma çözümleri bulmaya çalışın. İşleviniz belirleyiciyse ve aynı girişle birden çok kez çağrılacaksa, bir not alma çözümünden yararlanabilirsiniz.
- Özyinelemeli ilişkiyi bulun ve yazın. Bu mülakat sorusu için, yinelemeli ilişkiyi yazın ve N atlama sayısının yalnızca N-1 atlama sayısına bağlı olduğunu görebilirsiniz.
Ama bekleyin, henüz bitmedi!
Görünüşe göre bu meselenin sonu, ancak bu sorunun başka bir çözümü olduğu ortaya çıktı. Tüm röportajlarımda kimsenin bu çözümü önerdiğini görmedim. Bir meslektaşım şaşkınlıkla masasına dönene ve bize şimdiye kadarki en iyi aday olduğunu düşündüğü bir aday ile görüştüğünü söyleyene kadar bunun var olduğunu bile bilmiyordum.
Ama önce bu logaritmik karmaşıklık çözümünü okuyucuya bırakmak istiyorum ...
Orijinal İngilizce
https://medium.com/@alexgolec/google-interview-questions-deconstructed-the-knights-dialer-f780d516f029
