Google'ın klasik mülakat sorularının analizi
Yazar, bu makalede geçmişte Google röportajlarında kullandığı mülakat sorularını tanıtacak ancak soruların sızdırılması nedeniyle artık röportajlarda kullanılması yasaklanmıştır. Ancak bu sorular sızdırıldığı için yazar, soruların özünü görmeyi ve herkesin yararına olmasını umarak Google röportajının dikkate değer ayrıntılarını paylaşmayı umuyor.
Yazar | Alex Golec
Tercüman | Hilal Ay
Editör | Tu Min
Üretildi | CSDN (ID: CSDNnews)
Soruya dalmadan önce heyecan verici bir haber var: Google'dan ayrıldım! Reddit'e katıldığımı ve New York'ta proje yöneticisi olarak görev yaptığımı duyurmaktan heyecan duyuyorum!
Sorumluluk Reddi: Adaylarla röportaj yapmak benim görevim olsa da, bu makale sadece kişisel gözlemlerimi, anekdotlarımı ve görüşlerimi temsil ediyor. Lütfen bu makaleyi Google, Alphabet, Reddit veya diğer kişi veya kuruluşlardan gelen resmi bir açıklama olarak değerlendirmeyin.
sorun
Popüler bir arama motoru çalıştırdığınızı ve günlükte "Obama'nın onay derecesi" ve "Obama'nın popülerliği" gibi iki sorgu gördüğünüzü hayal edin. (Doğru hatırlıyorsam, bunlar aslında veritabanı görüşmelerinde kullanılan örneklerdir, ancak bu sorunun tarihi biraz eski olsa da ...) Bu iki sorgu farklı dizelerdir, ancak bence (kabul edeceğinize inanıyorum) Temel olarak, aynı şeyi arıyorlar ve bu iki sorgu, sorguları sayma ve sonuçları görüntüleme açısından eşdeğer olarak kabul edilebilir. Öyleyse, iki sorgunun eşanlamlı olduğunu nasıl bilebiliriz?
Resmi bir dille anlatalım. İki girişiniz olduğunu varsayalım. İlki, her öğenin bir çift iki dizeden oluştuğu ve eşanlamlı oldukları bir listedir. İkincisi ayrıca bir listedir, her öğe iki sorguyu temsil eden bir çift dizedir.
Spesifik olmak gerekirse, aşağıdaki örnek girdiyle açıklayacağım:
SENONİMLER = SORULAR =Göreviniz, her biri karşılık gelen sorgu çiftinin eşanlamlı olup olmadığını gösteren bir dizi Boolean değeri çıkarmaktır.
Soru
Yüzeysel olarak, bu çok basit bir soru. Ancak, ne kadar çok düşünürseniz, o kadar karmaşık hale gelir. Birincisi, bu sorunun tanımının mükemmel olmadığı açıktır. Her kelimenin birden fazla eş anlamlısı olabilir mi? Kelimelerin sırası önemli mi? Eşanlamlı ilişki geçişli midir, yani, eğer A ve B eşanlamlıysa ve B ve C eşanlamlıysa, bu A ve C'nin de eşanlamlı olduğu anlamına mı gelir? Kelimeler aynı zamanda eşanlamlı birden fazla kelimeden mi oluşur? Örneğin, "ABD" ve "Amerika Birleşik Devletleri" veya "Birleşik Devletler" eş anlamlı mı?
İyi adaylar, bu belirsizliği anında kendilerini farklılaştırmak için bir fırsat olarak kullanacaklardır. İyi bir adayın yapacağı ilk şey, bu tür belirsizlikleri bulmak ve bunları çözmeye çalışmaktır. Bunun nasıl yapılacağı kişiden kişiye değişir: Bazı insanlar beyaz tahtaya gider ve belirli sorunları manuel olarak çözmeye çalışır; bazı insanlar bir bakışta hileyi hemen görür. Her durumda, bu sorunları olabildiğince erken yakalamak hayati önem taşır.
Bu sorunun "soruyu anlama" aşamasına büyük önem veriyorum. Yazılım mühendisliğini fraktal bir konu olarak adlandırmayı seviyorum, bu da onun fraktal ile benzerlikleri olduğu anlamına gelir, yani problemi büyütmek ek karmaşıklık gösterebilir. Tam da belirli bir sorunu anladığınızı düşündüğünüzde, daha yakından baktığınızda, bir incelik ya da geliştirilebilecek uygulama ayrıntılarını gözden kaçırdığınızı ya da daha fazla ayrıntı hakkında fikir edinmek için soruna yeni bir bakış yolu bulduğunuzu görürsünüz. .
Mühendislerin yetenekleri büyük ölçüde problemi anlamalarına bağlıdır. Belirsiz bir problem ifadesini bir dizi ayrıntılı gerekliliğe dönüştürmek bu sürecin ilk adımıdır.Sorunu bilinçli olarak tanımlamak, adayın yeni durumlarla başa çıkma kabiliyetini değerlendirmemin temelidir.
Bu arada "vakanın dikkate alınıp alınmayacağı" gibi bazı önemsiz konular da var, bu sorunlar aday bilmese bile temel algoritma sorunlarını etkilemeyecek. Bu sorular için normal şartlar altında en basit cevabı vereceğim (bu örnek için "her şeyin küçük harfe dönüştürüldüğünü varsayarak" diyeceğim).
Bölüm 1: (Değil) Basit Örnek
Adaylar bu sorularla karşılaştıklarında bana her zaman cevabı sorarlar ve ben her zaman en basit durumdan başlarım: bir kelimenin birden fazla eş anlamlısı olabilir, sıra önemlidir, eş anlamlılar aktarılamaz ve eşanlamlılar yalnızca Bir kelime diğeriyle eşleşir. Bu nedenle, bir arama motoruna yerleştirildiğinde çok sınırlı işlevleri vardır, ancak incelikleri görüşmeler için birçok soruna neden olacaktır.
Bu sorunun çözümü son derece özetlenebilir: sorguyu kelimelere ayırın (boşluklarla ayırın) ve aynı veya eşanlamlı olup olmadıklarını görmek için karşılık gelen kelime çiftlerini karşılaştırın. Aşağıda gösterildiği gibi:
Uygulama kabaca şu şekildedir:
def synonym_queries (eşanlamlı sözcükler, sorgular): '' ' eşanlamlı sözcükler: eşanlamlı sözcükleri temsil eden yinelenebilir dizi çiftleri sorgular: test edilecek sorguları temsil eden yinelenebilir dize çiftleri eşanlamlılık '' ' output = sorgularda q1, q2 için: q1, q2 = q1.split (), q2.split () eğer len (q1)! = len (q2): output.append (False) devam et sonuç = Doğru aralıktaki i için (len (q1)): w1, w2 = q1 , q2 w1 == w2 ise: devam et elif words_are_synonym (w1, w2): devam et sonuç = Yanlış kırmak output.append (sonuç) dönüş çıkışıLütfen dikkat: Burada kasıtlı olarak words_are_synonym'ı tanımlamadım
Çok basit, değil mi? Algoritmik olarak konuşursak, bu çok basit. Dinamik programlama yok, özyineleme yok, karmaşık veri yapıları yok, vb. Bu sadece çok basit bir standart kütüphane işlemi ve doğrusal zaman algoritması, değil mi?
Öyle düşünebilirsiniz, ancak ilk bakışta gördüğünüzden daha inceliklidir. Şimdiye kadar, bu basit algoritmanın en zor kısmı eş anlamlı karşılaştırmasıdır. Anlaması ve tarif etmesi kolay olsa da eş anlamlıların karşılaştırılmasında birçok hata olabilir. Gördüğüm bazı yaygın sorunları tanıtmama izin verin.
Öncelikle bence adayların bu hatalardan dolayı mülakatta başarısız olmayacakları, adayın uygulaması yanlışsa işaret edeceğim ve çözümlerini ayarlayacakları, ardından mülakatın devam edeceği belirtiliyor. Ancak görüşme, saniyede bir sayılan bir süreçtir. Hata yapmak, hata bulmak, hataları düzeltmek, bu davranışların hepsi beklenir, ancak sonuç olarak boşa harcanan zaman, daha iyi çözümler bulmak gibi başka şeyler için de kullanılabilir. Hata yapmayan az sayıda aday vardır, ancak daha az hata yapan adaylar, hatalarını temizlemek için daha az zaman harcadıkları için daha iyisini yapabilirler.
Bu yüzden bu konuyu seviyorum: önceki makaledeki konu, ışık yanıp söndüğünde bir algoritma bulmalı ve sonra basit bir uygulama bulmalı. Bu soru farklı, doğru yönde adım adım ilerlemesi gerekiyor. Her adım, adayın zarafetle üstünden atlayabileceği veya takılıp tekrar ayağa kalkabileceği küçük bir engeli temsil eder. İyi adaylar, bu küçük tuzaklardan kaçınmak ve daha ayrıntılı ve doğru çözümler bulmak için deneyimlerini ve sezgilerini kullanırken, zayıf olanlar hatalarla başa çıkmak için zaman ve enerji harcar ve genellikle sadece sonunda hataları bırakır. Koddan bıktım.
Her röportaj yaptığımda, birinin çürük ve şişmiş bir yüzü varken, birinin zarafetle üstünden atladığını göreceğim, ancak burada birkaç yaygın hatayı göstermek için birkaç örnek vermek istiyorum.
Beklenmeyen çalışma zamanı katili
İlk olarak, bazı adaylar sadece eşanlamlılar listesini geçerek eşanlamlı tespiti gerçekleştirecekler:
... elif (w1, w2) eşanlamlı sözcüklerde: devam et ...Görünüşte bu makul görünüyor. Ama yakından bakarsanız, bunun çok çok kötü bir fikir olduğunu göreceksiniz. Python'u bilmeyenlere açıklamak istiyorum: in anahtar kelimesi içerir yöntemi için sözdizimsel şekerdir ve tüm standart Python konteynerleri için geçerlidir. Buradaki sorun, synonym_words'ün, anahtar kelimeyi doğrusal arama yoluyla uygulayan bir liste olmasıdır. Python kullanıcıları bu tür bir hataya özellikle duyarlıdır çünkü dil türleri gizler, ancak C ++ ve Java kullanıcıları bazen aynı hatayı yapar.
Tüm kariyerim boyunca, bu tür doğrusal arama kodunu birkaç kez yazdım ve ilgili liste her seferinde yirmiden fazla öğeyi geçmeyecek. Yine de, okuyucuya nedenini anlatmak için büyük bir yorum yazacağım. Bu görünüşte daha az ideal olan yöntemi seçtim. Bazı adayların Python standart kitaplığı hakkında yeterince bilgi sahibi olmadıkları ve anahtar kelimeyi listede nasıl uygulayacaklarını bilmedikleri için burada doğrusal aramayı kullandığından şüpheleniyorum. Bu, yapması çok kolay bir hata, ölümcül olmasa da, seçtiğiniz dilde yetkin değilsiniz gibi görünüyor.
Gerçek önerilere gelince, bu tür hatalardan kaçınmak aslında çok kolay. Öncelikle, python gibi türlenmemiş bir dil kullandığınızda, nesnenin türünü asla unutmayın! İkinci olarak, liste için içindeki anahtar kelimeyi kullanırsanız, doğrusal bir arama oluşturacağını lütfen unutmayın. Bu listenin her zaman çok küçük olduğunu garanti edemezseniz, bir performans katili haline gelecektir.
Genellikle, adaylara giriş yapısının tepki vermelerini sağlayacak bir liste olduğunu hatırlatın. İpucunu verdikten sonra güzel bir gösteri oldu. İyi adaylar hemen eş anlamlıları bir şekilde önceden işlemeyi düşünürler ki bu iyi bir başlangıçtır. Ancak, bu yöntem tuzaklardan yoksun değildir ...
Doğru veri yapısını kullanın
Yukarıdaki koddan da görülebileceği gibi, bu algoritmayı doğrusal zamanda uygulamak için, sabit zaman eşanlamlı aramasına ihtiyacımız var. Ve her sabit zamanlı aramadan sonra bir hashmap veya hashset olmalıdır.
Bu iki adayın hangisini seçeceği ile ilgilenmiyorum, ne saklayacaklarını merak ediyorum. (Bu arada, True veya False döndüren bir dict / hashmap kullanmayın. Buna küme denir.) Çoğu aday bir tür dict / hashmap seçecektir. Gördüğüm en yaygın hata, her kelimenin en fazla bir eşanlamlıya sahip olduğuna dair bilinçaltı bir varsayımdır:
... eş anlamlılar = {} w1, w2 için eşanlamlı sözcüklerde: eş anlamlılar = w2 ... elif eşanlamlıları == w2: devam etBu hatadan dolayı adayları cezalandırmayacağım. Bu örneğin girdisi, insanları bir kelimenin birden fazla eşanlamlıya sahip olabileceği düşünülemez hale getirmek için kasıtlı olarak tasarlanmıştır ve bazı adaylar bu sınır durumunu düşünmez. Bu hatayı belirttikten sonra, çoğu insan bunu çabucak düzeltecektir. İyi adaylar, bu sorundan kaçınmak için bu sorunu erken fark edeceklerdir, ancak bu genellikle çok zaman geçmesine neden olmaz.
Biraz daha ciddi bir sorun, eşanlamlı ilişkilerin iki yönlü olduğunu fark etmemenizdir. Yukarıdaki kodun bunu yaptığını fark edebilirsiniz. Ancak bu sorunu düzeltmek yanlış olabilir. Bu mülke ulaşmak için lütfen aşağıdaki yolları göz önünde bulundurun:
... eşanlamlılar = defaultdict (set) w1, w2 için eşanlamlı sözcüklerde: eşanlamlılar.append (w2) eşanlamlılar.append (w1) ... eşanlamlılar.get (w1, tuple ()) içindeki elif w2: devam etEk bellek tüketmeden iki kontrol gerçekleştirebiliyorsanız, hafızayı iki katına çıkarmak için neden iki ek kullanasınız?
... eşanlamlılar = defaultdict (set) w1, w2 için eşanlamlı sözcüklerde: eşanlamlılar.append (w2) ... elif (eşanlamlılar.get'te w2 (w1, tuple ()) veya eşanlamlılar.get (w2, tuple ())) içindeki w1: devam etİpucu: İş yükünü azaltıp azaltamayacağınızı her zaman kendinize sorun! Geriye dönüp bakıldığında, aramanın düzenlenmesi açıkça zaman kazandıran bir yöntemdir, ancak optimal olmayan bir uygulama kullanmak, adayın optimize edilmiş bir yöntem bulmayı düşünmediğini gösterir. Tekrarlamak gerekirse, bir ipucu verebilirim, ama bana ihtiyaç duymamak daha iyi olmaz mı?
Çeşit?
Bazı çok akıllı adaylar, eş anlamlılar listesini sıralayabileceğinizi ve ardından iki kelimenin eşanlamlı olup olmadığını kontrol etmek için ikili arama yöntemini kullanabileceğinizi düşünüyor. Aslında, bu yöntemin temel avantajı, giriş eşanlamlıları listesi dışında herhangi bir ek yer kaplamamasıdır (giriş listesinin değiştirilebileceği varsayılarak).
Ne yazık ki, zaman karmaşıklığı çok büyük değil: eş anlamlılar listesini sıralamak için gereken süre Nlog (N) ve her bir eş anlamlı çiftini bulma zamanı log (N) ve yukarıdaki ön işleme çözümü doğrusal. Sonraki, arama için sabit zamandır. Ayrıca, adayların beyaz tahtada sıralama ve ikili arama uygulamalarını istemiyorum çünkü (1) sıralama algoritması iyi biliniyor, bu yüzden adayın sadece mekanik tekrar yapabileceğini biliyorum; ve (2) doğru algoritmayı yazmak istiyorsanız, bu algoritmalar aslında Bu çok zor.Genellikle en iyi adaylar bile ara sıra hata yaparlar Programlama becerilerinde bir sorun olduğunu söyleyebilir misiniz?
Ne zaman bir aday böyle bir çözüm sunsa, çalışma zamanının karmaşıklığını soracağım ve onlara daha iyi bir yol olup olmadığını soracağım. Bu arada: görüşmeci size daha iyi bir yol olup olmadığını sorarsa, çoğu durumda cevap "evet" olur. Size bu soruyu sorduysam, cevap "evet" olmalıdır.
Son çözüm
Umarım adayın doğru ve en iyi sonucu vermiştir. Aşağıdaki, bu konu için doğrusal zaman doğrusal uzayının gerçekleştirilmesidir:
def synonym_queries (eşanlamlı sözcükler, sorgular): '' ' eşanlamlı sözcükler: eşanlamlı sözcükleri temsil eden yinelenebilir dizi çiftleri sorgular: test edilecek sorguları temsil eden yinelenebilir dize çiftleri eşanlamlılık '' ' eşanlamlılar = defaultdict (set) w1, w2 için eşanlamlı sözcüklerde: eşanlamlılar.add (w2) output = sorgularda q1, q2 için: q1, q2 = q1.split (), q2.split () eğer len (q1)! = len (q2): output.append (False) devam et sonuç = Doğru aralıktaki i için (len (q1)): w1, w2 = q1 , q2 w1 == w2 ise: devam et elif ((eş anlamlılarda w1 ve eş anlamlılarda w2) veya (eş anlamlılarda w2 ve eş anlamlılarda w1)): devam et sonuç = Yanlış kırmak output.append (sonuç) dönüş çıkışıİşte bazı kısa talimatlar:
- Dict.get () kullanımına dikkat edin. "Anahtarın alınmadan önce diktede olup olmadığını kontrol et" uygulamasını kullanabilirsiniz, ancak daha sonra standart kitaplık hakkındaki bilginizi gösterme fırsatını kaybedersiniz.
- Şahsen, çok fazla devam eden kodu sevmiyorum ve bazı programlama stili kılavuzları bunu yasaklıyor veya önermiyor. Aslında, orijinal kodumda bir hata var - sorgu uzunluğu kontrolünden sonra devam atlandı. Bu böcek korkunç değil ama hata yapmak çok kolay.
Bölüm 2: Zorluğu artırın!
İyi adaylarla mülakat yaparken, genellikle sonunda 10-15 dakika kaldığını görüyorum. Neyse ki, pek çok takip sorusu sorabilirim, ancak bu süre içinde çok fazla kod yazmamız pek olası değil. Günün sonunda bunu yapmam gerektiğini düşünmüyorum, ancak adayların yeteneklerini iki açıdan anlamak istiyorum: Algoritma tasarlayabilirler mi? Ve kod yazabilirler mi? Son yazımdaki soru önce algoritma tasarımı problemine cevap veriyor, sonra kodu kontrol edebiliyorsunuz ancak bu yazıda bu soruya verilen cevapların cevaplanma sırası tam tersi.
Adaylar problemin ilk kısmını tamamladıktan sonra (çok zor) programlama problemini çözmüşlerdir. Şu anda rahatlıkla söyleyebilirim ki temel algoritmalar tasarlama becerisine sahipler, fikirlerini koda da çevirebiliyorlar ve ayrıca en sevdikleri dil ve standart kitaplığı çok iyi biliyorlar. O zaman bu soru daha ilginç hale geliyor, çünkü programlama gereksinimleri zaten mevcut, algoritma kısmına girebiliriz.
Bu amaçla, ilk bölümün temel varsayımına dönelim: kelimelerin sırası önemlidir, eş anlamlılar arasındaki ilişki geçişli değildir ve eşanlamlılar birden fazla kelime içeremez. Görüşme ilerledikçe, bu kısıtlamaları değiştireceğim ve bu programlama sonrası aşamada, aday ve ben yalnızca saf algoritmaları tartışabiliriz. Söylediklerimi açıklamak için bazı kod örnekleri kullanacağım, ancak gerçek röportajda tartışma için saf algoritmik terimler kullanacağım.
Daha ileri gitmeden önce, aşağıdaki görüşmelerin beklentilerimden temelde "artı puan" olduğunu söylemek isterim. Bu soruna kişisel yaklaşımım, denetimin ilk bölümünde tam "nitelikli" adayları seçmek ve ardından denetimin bir sonraki aşamasına kadar "nitelikli" adaylar arasından "güçlü" adayları seçmektir. "Kalifiye" adaylar zaten çok iyi, "Bu kişinin işi iyi yapabileceğine inanıyorum" ifadesini temsil ederken, "güçlü" adaylar "Bu kişinin çok iyi olduğuna ve onları işe almanın şirkete fayda sağlayacağına inanıyorum. Büyük fayda. "
Geçişlilik: saf yaklaşım
Tartışmak istediğim ilk soru geçişlilik hakkındadır, yani eğer A ve B kelimeleri eşanlamlıysa ve B ve C sözcükleri eşanlamlıysa, o zaman A ve C sözcükleri de eşanlamlıdır. Duyarlı adaylar yakında bu sorunu çözmek için önceki çözümü ayarlayabileceklerini anlayacaklar çünkü hala basit bir çift kelimenin eş anlamlıları için kontrol edilmesi gerektiğini düşünürken, bazıları önceki algoritmanın temel mantığının Faydasız.
Yani ne yapmalıyız? Yaygın bir yöntem, aktarım ilişkisine göre her kelime için tam bir eş anlamlılar kümesi sağlamaktır. Eşanlamlılar kümesine bir sözcük eklediğimizde, onu aynı zamanda kümedeki tüm geçerli sözcüklerin karşılık gelen kümesine de ekleriz:
eşanlamlılar = defaultdict (set) w1, w2 için eşanlamlı sözcüklerde: eş anlamlı w için: eşanlamlılar.add (w2) eşanlamlılar.add (w2) eş anlamlı w için: eşanlamlılar.add (w1) eşanlamlılar.add (w1)Yukarıdaki kodla, adayların seçmesine izin verdiğim bu çözüme zaten dalmış olduğumuzu lütfen unutmayın.
Bu çözüm etkilidir, ancak en iyi çözüm olmaktan uzaktır. Neden bilmek ister misin? Bu çözümün uzay karmaşıklığını ele alalım. Bir eşanlamlı kelime eklendiğinde, sadece başlangıç sözcükleri kümesine değil, aynı zamanda sözcüğün tüm eşanlamlıları kümesine de eklemeliyiz. Kelimenin eşanlamlısı varsa, bir veri parçası eklemeniz gerekir. Kelimenin 50 eşanlamlısı varsa, 50 veri eklemem gerekir. Aşağıda gösterildiği gibi:
3 anahtar ve 6 veri öğesinden 4 anahtar ve 12 veri öğesine genişlettiğimizi unutmayın. Bir kelimenin 50 eşanlamlısı varsa, 50 anahtar ve yaklaşık 2500 veri öğesine ihtiyaç vardır. Bir kelimeyi temsil etmek için gereken alan ve onun sentetinin boyutu ikinci dereceden büyüyor ki bu büyük bir israftır.
Başka çözümler de var, ancak sınırlı alanı göz önünde bulundurarak, onları burada tekrar etmeyeceğim. En ilginç yöntemlerden biri, eş anlamlıların veri yapısını yönlendirilmiş bir grafik oluşturmak için kullanmak ve ardından iki kelime arasında bir yol olup olmadığını bulmak için önce geniş aramayı kullanmaktır. Bu iyi bir çözümdür, ancak arama kelime sentetinin boyutunda doğrusal hale gelir. Her sorgu için birden fazla arama yapmamız gerektiğinden, bu yöntem en uygun çözüm değildir.
Geçişlilik: ayrık kümeler kullanın
Eşanlamlı ilişkileri "ayrık küme" adı verilen bir veri yapısı kullanarak sabit zamanda bulabileceğimiz ortaya çıktı. Bu yapı koleksiyon olarak adlandırılır, ancak sağladığı işlev çoğu insanın hayal ettiği "koleksiyon" kelimesinden farklıdır.
Ortak bir koleksiyon yapısı (hashset, treeet), bir koleksiyonun bir nesne içerip içermediğini hızla bulmanızı sağlayan bir kapsayıcıdır. Ayrık küme (ayrık küme) farklı bir sorunu çözer: belirli bir kümenin kendisinin belirli bir öğeyi içerip içermediğini önemsemez, ancak iki öğenin aynı kümeye ait olup olmadığını kontrol etmenize olanak tanır. Daha da önemlisi, bu işlemi tamamlamak için geçen süre çok kısadır, sadece O (a (n)), burada a (n) Ackerman'ın işlevinin tersidir. Gelişmiş algoritmalarla ilgili bir kurs almadıysanız, bu özelliği bilmeseniz bile kendinizi suçlamanıza gerek yoktur. Tüm makul girdiler için, bu aslında sabit bir zamanda yapılabilir.
Bu algoritmanın işleyişi kabaca aşağıdaki gibidir. Ağaç, her biri bir ebeveyni olan bir koleksiyonu temsil eder. Her ağacın bir kökü olduğu için (yani bir öğenin ebeveyninin kendisi olduğu anlamına gelir), her öğenin kök öğesi bulunana kadar ebeveynine bakarak iki öğenin aynı koleksiyona ait olup olmadığını belirleyebiliriz. İki öğe aynı kök öğeye sahipse, aynı kümeye ait olmaları gerekir. Bu kümeleri bağlamak da kolaydır: sadece kök öğeyi bulmamız ve birini diğer öğenin kökü olarak kullanmamız gerekir.
Şimdiye kadar her şey yolunda gidiyor, ancak performansta hala bir ilerleme yok. Bu yapının dehası "sıkıştırma" adı verilen bir süreçte yatmaktadır. Aşağıdaki ağacın olduğunu varsayalım:
"Hızlı" ile "aceleci" nin eşanlamlı olup olmadığını bilmek istediğinizi varsayalım. Her düğümden, aynı kök düğüme "hızlı" sahip olduklarını bulana kadar ana ilişkiyi geçin, bu nedenle eşanlamlı olmaları gerekir. Şimdi "hızlı" ile "hızlı" nın eşanlamlı olup olmadığını bilmek istediğinizi varsayalım. "Hızlı" bulana kadar her bir düğümü tek seferde geçeceksiniz, ancak bu sefer "hızlı" geçişi tekrarladığınızı fark edeceksiniz. Bu işin tekrarını önleyebilir misin?
Yapabileceğin ortaya çıktı. Bir dereceye kadar, bu ağaçtaki her öğenin kaderi "hızlı" bir düğüm bulacaktır. Ağacı birden çok kez geçmek yerine, neden her bir öğenin ana öğesini "hızlı" olarak değiştirmiyoruz, bu iş yükünü azaltmaz mı? Bu işleme "sıkıştırma" adı verilir ve ayrık kümelerde "sıkıştırma" inşası, kökü bulma işlemidir. Örneğin, "hızlı" ve "aceleci" nin eşanlamlı olduğunu belirledikten sonra, yukarıdaki ağaç şu olur:
"Hızlı" ve "hızlı" arasındaki her sözcüğün üst düğümü güncellendi ve "aceleci" nin üst düğümü de "hızlı" olarak güncellendi.
Bu şekilde, sonraki tüm ziyaretler sabit zamanda tamamlanabilir, çünkü bu ağaçtaki her bir düğüm "hızlı" ı işaret eder. Bu yapının zaman karmaşıklığını analiz etmek çok önemlidir: ağacın derinliğine bağlı olduğu için gerçekten sabit değildir, ancak sabitten daha kötü değildir, çünkü hızla sabit zamanda amorti edilebilir. Analizimiz için tembelce sabit zaman diyoruz.
Bu kavramı göz önünde bulundurarak, bu sorunu çözmek için ihtiyaç duyduğumuz işlevleri sağlayan ayrık kümelerin uygulanmasına bakalım:
class DisjointSet (nesne): def __init __ (öz): self.parents = {} def get_root (self, w): words_traversed = self.parents! = w iken: words_traversed.append (w) w = self.parents Words_traversed'deki kelime için: self.parents = w w dönüş def add_synonym (öz, w1, w2): w1 self.parents içinde değilse: self.parents = w1 w2 self.parents içinde değilse: self.parents = w2 w1_root = self.get_root (w1) w2_root = self.get_root (w2) eğer w1_root < w2_root: w1_root, w2_root = w2_root, w1_root self.parents = w1_root def are_synonymous (öz, w1, w2): return self.get_root (w1) == self.get_root (w2)Bu yapı ile eşanlamlıları önceden işleyebilir ve bu problemi doğrusal zamanda çözebiliriz.
Değerlendirme ve açıklama
Bu noktada 40-45 dakikalık bir görüşme süresi içerisinde yapılabilecek her şeyin sınırına ulaştık. Testin ilk bölümünde "nitelikli" adayları seçtim ve ayrık setlere (uygulama dahil değil) çözümleri anlatarak "güçlü" adayları seçtim ve sonunda bana soru sormalarına izin verdim. Bu kadar ileri gidebilecek bir adayla hiç tanışmadım ve bana hala soru sormak için zamanım var.
Hala yapılması gereken bazı takip çalışmaları var: Bu sorunun bir versiyonu, kelimelerin sırasının önemli olmadığı ve eş anlamlıların birden fazla kelime olabileceğidir. Her sorunun çözümü zorlayıcı ve heyecan vericidir, ancak alan sınırlamaları nedeniyle sonraki makalelerde tartışacağım.
Bu soru çok pratiktir çünkü adayların hata yapmasına izin verir. Günlük yazılım mühendisliği çalışması, sonsuz analiz, yürütme ve iyileştirmeyi içerir. Bu soru, adaylara uygulamalarını her aşamada gösterme fırsatı sunar. Bu soruyla "güçlü" bir aday olmak istiyorsanız, aşağıdaki teknik becerilere ihtiyacınız var:
- Sorunun tanımını analiz edin, belirsiz ve belirsiz yerleri bulun, gerekli yerleri netleştirin ve net bir sorun tanımı oluşturun. Bu uygulamaya devam edin ve çözüm bulmaya ve yeni sorunlarla karşılaşmaya devam edin. Verimliliği en üst düzeye çıkarmak için, bu aşamada bu yaklaşıma olabildiğince erken başlayın, çünkü iş ilerledikçe hataları düzeltme maliyeti artacaktır.
- Sorunu, erişilmesi ve çözülmesi kolay bir şekilde yeniden yapılandırın. Sorumuzda en önemli nokta, sorguda karşılık gelen kelimeleri sıralayabileceğinizi gözlemlemektir.
- Çözümünüzü uygulayın. Bu, en iyi veri yapısını ve algoritmayı seçmeyi ve gelecekte okunabilir ve değiştirmesi kolay mantığı tasarlamayı içerir.
- Geri dönüp hataları ve hataları bulmaya çalışmak. Kodda, yukarıdaki "devam" ifadesini eklemeyi unuttuğum gibi bazı gerçek hatalar veya yanlış veri yapılarının kullanımından kaynaklanan performans sorunları olabilir.
- Sorun tanımı değiştiğinde, lütfen yukarıdaki işlemi tekrarlayın ve uygun olduğunda çözümünüzü ayarlayın. Geçerli değilse, atmanız gerekir. İster bir röportajda ister gerçek dünyada, zamanlama kilit bir beceridir.
- Çok sayıda veri yapısı ve algoritma bilgisi öğrenin. Ayrık kümelerin veri yapısı sıradan bir yapı değildir, ancak çok nadir veya mükemmel değildir. İş yerindeki araçları anladığınızdan emin olmanın tek yolu, mümkün olduğunca çok şey öğrenmektir.
Bu tekniklerin hiçbiri ders kitaplarından öğrenilemez (veri yapıları ve algoritmalar hariç). Bu teknolojileri elde etmenin tek yolu, şirketin ümidiyle tutarlı olan sürekli ve kapsamlı uygulamalardır: adaylar teknik becerilerinde uzmanlaşmıştır ve bu teknolojileri etkin bir şekilde kullanmak için çok sayıda pratik deneyime sahiptir. Bu tür yetenekleri bulmak röportajın asıl amacı ve bu konuyu uzun süredir kullanıyorum.
dört gözle beklemek
Bu makaleyi okuyarak, bu konunun da sızdırıldığını görmüş olabilirsiniz. O zamandan beri birkaç soru kullandım, ruh halime ve ilk adayların sorduğu sorulara göre bir tane seçtim (bir soru sormaya devam etmek sıkıcıdır). Bu soruların bazıları hala kullanımda, bu yüzden sır olarak saklayacağım, ancak bazıları artık kullanılmıyor! Yani, bu konuları ilerideki makalelerde görmeyi bekleyebilirsiniz.
Orijinal: https://medium.com/@alexgolec/google-interview-problems-synonymous-queries-36425145387c
Yazar: Alex Golec, Mühendislik Müdürü @ Reddit NYC, eski Google çalışanları.
Bu makale bir CSDN çevirisidir. Yeniden yazdırmanız gerekirse, lütfen kaynağı belirtin.
