Faktury elektroniczne EBPP

Trystero

Kilka zagadek z rozmów kwalifikacyjnych Google

Opublikowane przez Trystero w kategorii Społeczeństwo dnia 07.11.2009 | Komentarze (48) »

Silicon Alley Insider opublikował 15 przykładowych pytań (oraz odpowiedzi na nie) zadawanych na rozmowach kwalifikacyjnych w Google. Jeśli zadawanie tego typu pytań jest integralną częścią procedury rekrutacyjnej Google to moje przekonanie, że GOOG to najbardziej innowacyjna organizacja w historii ludzkości zdobędzie kolejne potwierdzenie.

Pytania z rozmów kwalifikacyjnych są bardzo stymulujące intelektualnie – myślę więc, że mogą urozmaicić ten deszczowy weekend. Zaczynamy:

Ile piłeczek golfowych zmieści się w autobusie szkolnym?

Moja odpowiedź: jakiego koloru jest autobus?

A na poważnie, to nie używałem tutaj wzorów, posłużyłem się wizualizacją. Wyobraziłem sobie autobus 15 metrów długi, 2 metry szeroki i 2 metry wysoki oraz piłeczkę golfową o średnicy 5 centymetrów. Na ‘tylnej’ ścianie zmieści się 40 x 40 piłeczek. Trzeba to pomnożyć przez 15 x 20. Mamy więc 1600 x 20 czyli 32 000 x 15 czyli 480 000. Odjąłbym od tego jakieś 10% – 20% ponieważ nie cała przestrzeń w autobusie jest pusta. W każdym razie ‘obszedłem’ kombinowania z wpisywaniem kuli w sześcian, wzorem na objętość kuli i takimi tam.

Masz 8 piłek. Jedna z nich jest lżejsza niż pozostałe. Jak za pomocą dwóch ważeń na wadze szalkowej ustalić, która to piłka?

Proste ale nie będę psuł zabawy.

Jeśli w jakimś państwie wszystkie rodziny kontynuują płodzenie dzieci dopóki nie ‘stworzą’ chłopca a potem zaprzestają to jaki będzie stosunek chłopców do dziewczynek w tym państwie?

Świetna zagadka.

Ile potrzeba stroicieli pianin na świecie?

Słabe. To klasyczny problem Fermiego.

Masz dwa jajka i dostęp do 100 piętrowego budynku. Masz sprawdzić, jakie jest najwyższe piętro, z którego jajka przetrwają upadek za pomocą jak najmniejszej liczby prób. Ile razy będziesz musiał zrzucić jajka w najbardziej pracochłonnym przypadku?

To jest podchwytliwe. Trzeba pamiętać, że ma się tylko dwa jajka.

Miłej zabawy a jeśli komuś się nie znudziło to tutaj ma 140 pytań z rozmów kwalifikacyjnych w Google.

Podziel się z innymi:
  • Wykop
  • Google Bookmarks
  • Facebook
  • BLIP - Bardzo Lubię Informować Przyjaciół
  • Co-Robie.pl | Co teraz robisz?
  • Wrzuć to na Flakera - powiadom swoich Znajomych
  • grono.net - internetowa społeczność przyjaciół
  • Dodaj link - Linkr.pl - tylko ciekawe linki
  • Polec.pl - Pozytywnie Odjazdowo Lajtowo Elokwentny Content
  • Dodaj wyczajenie
  • Spis.pl - najciekawsze w sieci
  • pinger.pl - Nie taki zwykły blog.

Komentarze (48) do "Kilka zagadek z rozmów kwalifikacyjnych Google"

  1. HeS powiedział(a):

    @Autor:

    Większośc tych pytań w zasadzie sprawdza znajomości “wzorców kulturowych”.

    Na pytanie: “Ile piłeczek golfowych zmieści się w autobusie szkolnym?” nie mógłbym odpowiedzieć, bo nie znam ani wymiarów piłeczki golfowej (nie miałem w ręce) ani wymiarów autobusu (jest przegubowy?).

  2. kujawianin powiedział(a):

    Zagadka z dziewczynkami i chłopcami daje wynik, który jest nieco zaskakujący.

  3. netka powiedział(a):

    To są pytania z serii: Dlaczego sułtan turecki nosił zielone szelki?
    Odp. żeby mu gacie nie opadły.
    Żenada

  4. Trystero powiedział(a):

    @ netka

    Alez skad. To sa bardzo logiczne zagadki, ktorych rozwiazywanie rozgrzewa umysl a zdolnosc rozwiazywania wskazuje na potencjal do kreatywnego myslenia.

  5. adremja powiedział(a):

    Pytań jest 140 a nie 160 :)

  6. GarbeeQ powiedział(a):

    W autobusie szkolnym miesci sie wiecej niz zero pileczek golfowych

  7. equinox powiedział(a):

    Trystero, takie Fermi Questions to kandydatom do pracy zaczal zadawac Microsoft. Cieszylo sie to nawet swoistym rozglosem na przelomie lat 80/90. No ale wtedy w Polsce to niewielu ludzi interesowalo sie msft. A pan pewnie za mlody. Wiec goog wcale nie pierwszy. Pozdro.

  8. pf powiedział(a):

    @ile piłeczek golfowych…
    Przy rozwiązaniu tego zadania jednak od znajomości matematyki nie da się uciec. Objętość kuli (4/3*pi*r^3) to tylko 0.52 objętości opisanego na niej sześcianu. Biorąc pod uwagę puste przestrzenie pomiędzy kulami w danej objętości da się upakować ok. 30% więcej kul niż sześcianów o boku równym długości jej średnicy.

  9. poszi powiedział(a):

    Prawidłowa odpowiedź z piłeczkami to:
    [(objętość dostępna dla piłeczek)/(objętość piłeczki)]*pi/(3*sqrt(2))

    http://en.wikipedia.org/wiki/Close-packing_of_spheres

    (nie pamietałem dokładnie tego czynnika, ale może na rozmowach u Google można googlować :)

    Innymi słowy, puste miejsca między piłeczkami to 1-pi/(3*sqrt(2)), czyli ok. 26% objętości.

    @pf,

    W danej objetości zmieści się dokładnie sqrt(2) razy piłeczek kulistych, co sześcianów o takiej samej średnicy i to jest ponad 41%, a nie 30%:

    (1/6)*pi*D^3 objętość piłeczki o średnicy D
    D^3 objętość sześcianu
    pi/(3*sqrt(2)) to zajęta objętość przez kule.
    [(D^3)*pi/(3*sqrt(2))]/[(1/6)*pi*D^3] = 2/sqrt(2)=sqrt(2)

    Należy pamiętac jednak, żeby autobusem dobrze potrząść po wypełnieniu :), bowiem powyższe to jest optymalne wypełnienie:

    http://en.wikipedia.org/wiki/Random_close_pack

  10. Trystero powiedział(a):

    @ poszi i pf

    Dzieki za uwagi.

  11. Adam powiedział(a):

    Ile potrzeba stroicieli pianin na świecie?

    czym to pytanie różni się od – ile potrzeba spawaczy na świecie? albo ekonomistów?

  12. Widmo powiedział(a):

    @Adam
    Ekonomistów? Wiesz czym się różnią ekonomiści od astronomów? Astronomowie zdają sobie sprawę z tego jaki mają wpływ na trajektorie gwiazd.

    @Trystero
    Mam wrażenie iż zagadka z jajkami jest błędnie rozwiązana na linkowanej stronie. Mi z jakichś rachunków wychodzi 15…

    pozdrawiam

  13. pf powiedział(a):

    @poszi
    W rzędzie może nam się zmieścić całkowita ilość piłeczek; przesunięcie o pół modułu kolejnych rzędów sprawia że zyskując na upakowaniu wewnątrz tracimy trochę objętości na ‘efekt brzegowy’. W danej objętości zmieściłoby się dokładnie (sqrt 2) x więcej piłeczek o średnicy d niż sześcianów boku d w przypadku gdybyśmy dysponowali “ułamkowymi piłeczkami” które można zastosować na brzegu sterty. Ponieważ ich nie mamy z każdego boku wystąpi stracona objętość której wielkość oszacowałem na (pole obwodu * 0.4 * promień piłeczki). Przy piłeczkach o średnicy 5cm w sześcianie o boku 0.5m tracimy na efekt brzegowy 12% objętości, czyli upakujemy tylko (41-12) = 29% więcej piłeczek niż sześcianów.

  14. kunta-kinte powiedział(a):

    Jakimi Państwo się bzdurami zajmują aż przykro czytać!Przecież jeżeli jesteście mądrzy,spostrzegawczy,kreatywnie myślący to odnieśliście sukces i macie dobra,w kierunku których zmierzaliście?Czyżby jednak otaczający rynek ocenił Państwa intelekt inaczej?A może życie to nie tylko wykształcenie,wiedza i mądrość?

  15. kujawianin powiedział(a):

    @kunta-kinte:

    Bez przesady, nawet w weekend bzdurami się nie można zajmować? :D

  16. kunta-kinte powiedział(a):

    Jest rynek od 23!

  17. Trystero powiedział(a):

    @ kunta-kinte

    Wiesz, z boku wyglada troche jakbys mial symptomy uzaleznienia :)

  18. mall powiedział(a):

    Te jajka są ciekawe. Należałoby zapytać jeszcze: a na co będą upadać?
    Ale ja i tak skłaniam się do takiego rozwiązania: 2 próby. Nie ma takiego wieżowca, w którym wysokość piętra dałaby choćby cień szansy na niestłuczenie jajka. Zwłaszcza, że najprawdopodobniej spadałoby ono na twardą powierzchnię jak chodnik czy asfalt.

  19. Trystero powiedział(a):

    @ mall

    To jest zagadka. Wyobraz sobie, ze jajka sa zmutowane i naprawde moga przetrwac upadek z wielu pieter.

  20. Ziemna powiedział(a):

    @ Trystero

    Nic z tego: Zagadka mówi wyraźnie “masz dwa jajka”. Nie: “masz dwa zmutowane jajka”… Zagadki, zwłaszcza te podchwytliwe, musimy czytać “as it is”.

  21. Trystero powiedział(a):

    @ Ziemna

    Ok, masz dwa jajka ale nie dwa niezmutowane jajka. Masz wymyslec takie rozwiazanie by wyznaczyc optymalny sposob ustalenia jakie jest najwyzsze pietro, z ktorego mozna zrzucic jajka. Koniec kropka.

  22. podtworca powiedział(a):

    Witam. Masz 2 jajka i pytanie jest ile razy w najbardziej pracowitym przypadku bedziesz musial je zrzucic. Odpowiedz na zadanie: 2 :)

  23. tadzio powiedział(a):

    JAJKA:
    1. Absolwent Uniwersytetu: zajmie się liczeniem = ? (bo ja z pkt 2 i dla mnie istnieje tylko odp z pkt 2)

    2. Absolwent Politechniki: zajmie się “liczeniem” jajek = 2

  24. kunta-kinte powiedział(a):

    @Trystero
    To chyba oczywiste niestety…

  25. ignorant powiedział(a):

    Przyjemne zadania :)

    Z tym upakowaniem piłeczek już Ci podpowiedzieli.

    A to z tym “jawnym dyskryminowaniem dziewczynek” też niezłe – już wyobrażam sobie jakąś nawiedzoną feministkę, która będzie gardłować, że to “samcze podejście do sprawy” bo te “szowinistyczne świnie” chcą sobie wyhodować harem dla każdego :D

    To z jajkami też niezłe – mnie wyszło 19.

    Pozdrawiam

  26. pf powiedział(a):

    @ignorant

    W zadaniu z jajkiem odkładasz do góry pewną ilość pięter. Jeśli spadające z tego piętra jajko rozbije się drugim jajkiem sprawdzasz od dołu wszystkie niższe piętra. Jeśli nie rozbije się odkładasz znowu do góry ilość pięter pomniejszoną o 1.
    Masz więc równanie:
    n + (n-1) +….+ 2 + 1 >= 100
    możesz je uprościć grupując ze sobą kolejne 2 elementy brane od końca i od początku, których suma zawsze jest równa (n+1)
    po uproszczeniu dostajesz:
    (n+1)(n/2)>=100 => n^2+n >=200
    Najniższą liczbą która spełnia ten warunek jest 14 którą możesz sprawdzić maksymalnie 105 pięter.

  27. x.y.z powiedział(a):

    @pf

    Wg Twojego rozumowania np. dla n=14 mamy:
    1. puszczamy 1 jajko z 86 piętra (100-14). (1 próba)
    2. jajko się rozbija. (1 próba)
    3. bierzesz 2 jajko i puszczasz z 1 piętra (2 próba). Jajko się nie rozbija.
    3. puszczasz 2 jajko z 2 piętra i jajko się nie rozbija (3 próba).

    85. puszczasz 2 jajko z 84 piętra i jajko się nie rozbija (85 próba).
    86. puszczasz jajko z 85 piętra i jajko się rozbija/nie rozbija i dopiero teraz jesteś pewien, że granicznym piętrem było 85/86 piętro (86 próba).

    Coś wydaje mi się, że ignorant był lepszy, jemu wystarcza tylko 19 prób.
    A dlaczego? Trzeba by się spytać ignorant lub dalej samemu pokombinować.

    Pozdrawiam z.y.z

  28. Trystero powiedział(a):

    @ x.y.z

    PF dobrze kombinowal. Sprawe mozna zalatwic w 16 ruchach. Zaczynasz od 16 pietra i gdy sie jajko nie rozbije dokladasz kolejno 15,14,13,12,11,10 i 9 pieter. Gdy gdzies sie jajko rozbije to zrzuczasz od poprzedniego pietra w gore.

    W ten sposob mozesz uzyskac minimalna liczbe ruchow. To chyba tez najbardziej optymalny sposob przy zalozeniu ze prawdopodobienstwo tego, ze dane pietro jest tym ‘wybranym’ jest takie same dla kazdego pietra.

  29. x.y.z powiedział(a):

    @pf & @trystero

    Chylę czoła! Pięknie!.
    Nie zrozumiałem tekstu pf (myślałem, że N góry). Pf ma rację. Wychodzi na to, że 14 prób wystarczy aby zawsze mieć pewność. (Prawdopodobieństwo jest nie istotne, zakładamy zawsze, że może być najgorszy przypadek).

    Sorry.

  30. Trystero powiedział(a):

    @ x.y.z

    Ok, PF ma racje :)

    14 prob!

    Kolejny raz okazuje sie, ze wzory sa wygodniejsze.

  31. x.y.z powiedział(a):

    @trystero

    Nie trzeba odkurzać. Wszystko (prawie wszystko) napisał PF. Oczywiście PF napisał również, że blok może mieć więcej pięter, np. dla 14 prób, pięter może być nawet 105 (> 100).

  32. x.y.z powiedział(a):

    @trystero

    Jakie wzory!
    Przecież PF na miejscu wyprowadził wzór na sumę liczb ciągu arytmetycznego.
    Myślenie jest wygodniejsze.

    Pozdrawiam, bezmyślny. (jeszcze raz muszę się pokajać nad chwilą bezmyślnego czytania PF)

  33. hm powiedział(a):

    @jajka

    czy to sie nie sprowadza do zastosowania algorytmu dziel i rządź ?

  34. kkk powiedział(a):

    zadanie z chlopcami

    rozwiazanie jest suma szeregu hipergeometrycznego
    Suma[1/(2^i)*1/i], gdzie i = 1 … nieskonczonosc

    suma ta wynosi Ln(2), czyli 0.6931

  35. kkk powiedział(a):

    chociaz … tak naprawde przeciez nikt nie bedzie rodzil w nieskoczonosc :), ale ten szereg jest szybko zbiezny, wiec wynik jest w zasadzie ten sam

  36. wlos powiedział(a):

    kkk: suma tego zbieżnego ciągu to był mój pierwszy pomysł, prawidłowe rozwiązanie jednak jest inne

  37. kkk powiedział(a):

    @wlos : a jakie niby ?

    zeby dopelnic formalnosci, stosunek chlopcy/dziewczynki to

    0.6931/(1-0.6931) = 2,25839

  38. pf powiedział(a):

    @kkk

    Każde zdarzenie płodzenia dzieci jest niezależne, więc fakt że jedni płodzą a inni nie płodzą nie ma żadnego znaczenia – proporcja będzie ok. 51/49 na korzyść chłopców, czyli taka jak w każdej innej populacji.
    Jeśli prawdziwa jest teoria o wpływie diety (czy uwarunkowań genetycznych) na płeć potomka, być może zwyczaj zaprzestawania płodzenia dzieci po stworzeniu chłopca spowoduje wzrost liczby dziewczynek (pary ukierunkowane na chłopców stworzą tylko jednego potomka, ukierunkowane na dziewczynki będą mogły ich mieć ile chcą). Ale innych uwarunkowań do rozbieżności tu nie widzę.

    Temat można zwizualizować rozkładając karty do gry w kilku rzędach. Następnie jeśli w danym rzędzie karta jest czerwona kładziesz na niej kolejną kartę. Jeśli jest czarna – nie dokładasz. Na końcu na wierzchu każdego rzędu masz czarną kartę. Ale suma wyłożonych kart czarnych i czerwonych jest statystycznie taka sama.

  39. ignorant powiedział(a):

    @pf

    Dzięki. Robiłem “to samo” tylko założyłem stałą odległość. Znaczy się dzieliłem 100 na n równych kawałków czyli sprawdzeń miałbym “pi razy drzwi” 100/n+n a to ma swoje minimum dla 10-ciu wiec pozostaje jeszcze przelecieć 9 pozycji wewnątrz przedziału.

    PS. Nie trzeba mnie uczyć sumowania ciągu arytmetycznego :)

    @kkk
    Z prawdopodobieństwem 1/2 będzie chłopak i będzie 1 dziecko,
    1/4 za drugim razem będzie chłopak i będzie 2 dzieci
    1/8 za trzecim i będzie 3

    Zatem wartością oczekiwaną jest \sum_{n=1}^{\infinity} n/2^n
    czyli wychodzi, że średnio rodzina ma 2 dzieci. Skoro w każdej rodzinie jest chłopak to znaczy że stosunek będzie 1:1.

    Uproszczenia – m.in. że czas stosunku i ciąży to 0.0 sekund :D, zatem dana rodzina ma możliwości (i chęci) próbować ile wlezie.

    PS. Tak przy okazji polecam tym co nie znają wolframalpha.com gdzie za free można się bawić takimi szeregami. W tym konkretnym przypadku:
    http://www.wolframalpha.com/input?i=sum+n%2F2%5En%2C+n%3D1%2Cinfinity

  40. ralf powiedział(a):

    Ciekawsze z ważeniem piłeczek jest jak zidentyfikować najlżejszą mając 9 piłeczek i tylko 2 ważenia na wadze szalkowej :)

  41. pf powiedział(a):

    @ralf
    wskazówka: do znalezienia lżejszej piłeczki spośród 243 potrzeba 5 ważeń.

  42. Abraxas powiedział(a):

    @ralf

    9 i 8 identyfikuje się identycznie.

  43. mdht powiedział(a):

    ile pilek zmiesci sie w autobusie?

    moja odpowiedz : 2 bo… przeciez 2 sie zmieszcza :P pytanie chyba nie brzmi, ile maksymalnie pilek zmiesci sie w autobusie;)

    pileczki – to za proste i rzeczywiscie 8 i 9 to wlasciwie to samo : P

    reszta rozwiazan w sumie mnie nie przekonala

  44. Jozef_socjopata powiedział(a):

    A gówno prawda z tymi jajkami. Potrzeba 0 prób. Już z parteru się rozbije.
    (właśnie mi wypadło z ręki przy wyciąganiu z lodówki)
    :)

  45. aa powiedział(a):

    A tu jest rozwiązanie zadania z patykiem
    http://www.zadania.info/4138624

  46. GK powiedział(a):

    Hej… :) Fajne te zagadki!

  47. informatyk powiedział(a):

    Według mnie każdy informatyk powinien umieć odpowiedzieć na pytania typu:
    1. Ile metrów sześciennych przepływa przez Odrę we Wrocławiu w ciągu doby?
    2. Ile waży powietrze w twoim pokoju?
    3. Ile waży drzewo?
    itp.
    Bo jeśli na takie pytania będzie umiał odpowiedzieć (to są tak zwane “obliczenia na odwrocie koperty”) to będzie umiał oszacować ile zapytań/dobę obsłuży jego serwer.

  48. prestig powiedział(a):

    Chyba tylko mi się zdaje że nie znacie odpowiedzi na pytanie z jajkami :) Odp. W najbardziej prachochłonnym wydaniu stracimy jedno jajko :)

Przepraszamy, możliwość dodawania komentarzy jest obecnie wyłączona.

Trystero

niezależny blog finansowy

Autor bloga jest inwestorem giełdowym i doktorantem na czołowym polskim uniwersytecie. Publikowane na blogu teksty dotyczą rynku kapitałowego, ekonomii, gospodarki i życia społecznego– w takiej mniej więcej kolejności więcej »

Content on this page requires a newer version of Adobe Flash Player.

Get Adobe Flash player