Tak, często zanim padnie jakiekolwiek pytanie o projektowanie czy dowolny język programowania, to najpierw dostaje się do rozwiązania zagadkę. Nie wiem w jakim stopniu sprawdza to umiejętności programistyczne i czy rozwiązywanie łamigłówek w pełni przekłada się na kod dobrej jakości ;) Ale po prostu tak jest, więc lepiej się przygotować :)
Więc co oprócz standardowej zagadki o wilku, kozie i kapuście może nas czekać? Pozbierałem 8 ciekawych zagadek dostępnych na serwisach z "interview questions". Nie wybrałem tych najdziwniejszych albo najbardziej niemożliwych do rozwiązania, tylko te najbardziej ludzkie ;)
1. Masz 3 koszyki - w jednym są tylko jabłka, w drugim tylko pomarańcze, a w trzecim mieszanka tych owoców. Etykiety na koszykach zawsze wprowadzają w błąd co do zawartości. Ile razy trzeba sięgać do koszyków, aby dobrze oznaczyć je wszystkie? Jaki jest algorytm?
2. Masz identycznych z wyglądu 8 kul. Jedna z nich jest wydrążona w środku i waży mniej niż pozostałe 7. Masz też do dyspozycji wagę szalkową. Ile minimalnie ważeń potrzeba aby znaleźć tą lżejszą? Jak to zrobić?
3. Dlaczego pokrywa od studzienki kanalizacyjnej powinna (i najczęściej jest) okrągła?
4. Jesteś nad jeziorem i masz do dyspozycji tylko 2 zbiorniki - jeden 3-litrowy, drugi 5-litrowy. Jak odmierzyć dokładnie 4 litry wody? Zbiorniki oczywiście nie mają podziałek.
5. Na imprezie jest tort w kształcie prostokąta. Jednakże ktoś już wyciął z niego prostokątny fragment. Położenie i rozmiar wyciętego fragmentu może być dowolne. Jak wykonać cięcie nożem wzdłuż jednej prostej linii, aby podzielić pozostałą część tortu na dwie równe części?
6. Masz 5 dużych słoików z identycznymi z wyglądu pigułkami. Cztery z tych słoików zawierają nieszkodliwe pigułki, które ważą 1 gram/sztuka. Jeden słoik zawiera jednak truciznę - jedna taka pigułka waży 0,9 grama. Masz do dyspozycji dokładną wagę (dokładność 0,1 grama). Jak dowiedzieć się, który słoik zawiera zatrute pigułki? Ile potrzebujesz do tego ważeń na wadze?
7. Masz szufladę pełną pomieszanych skarpetek - czarnych, białych i niebieskich. Ile musisz wyciągnąć skarpetek z szuflady, aby mieć w ręce co najmniej 2 skarpetki w tym samym kolorze? Wyciągasz oczywiście z zamkniętymi oczami, otwierasz je dopiero kiedy skończysz wyciąganie.
8. Pracownik pracuje dla Ciebie przez 7 dni. Jest cennym pracownikiem, więc płacisz mu w złocie - za cały tydzień dostanie całą sztabkę. Masz już tę sztabkę, jest na niej nawet zaznaczony podział na 7 równych części.
Problem jest taki: pracownik może zechcieć zaliczki na zakończenie dowolnego dnia. I tak np. po pierwszym dniu może chcieć dostać 1/7 sztabki. Zaliczkę może dostać tylko jedną, więc jeżeli np. po drugim dniu weźmie 2/7 sztabki, to resztę dostanie dopiero po siódmym dniu.
Ty musisz już dzisiaj podzielić sztabkę tak, aby być przygotowanym na każdą ewentualność: zaliczkę po dowolnym z 6 dni lub jej brak - wtedy po 7 dniu dajesz pracownikowi całość zapłaty. Podziału sztabki chcesz dokonać wykonując tylko dwa cięcia, tylko po liniach już zaznaczonych na sztabce. Jak to zrobisz?
Ad.1. Wystarczy sięgnąć tylko raz :) Sięgamy do koszyka podpisanego jako mix owoców.
OdpowiedzUsuńEtykiety zawsze kłamią, więc są tam tylko jabłka lub pomarańcze :) Powiedzmy, że wyciągamy jabłko, więc to jest koszyk z samymi jabłkami. Koszyk pełen pomarańczy na pewno nie będzie tym opisanym etykietą "pomarańcze", a więc musi być tym opisanym "jabłka" :). Mix jest w koszyku opisanym "pomarańcze" :)
Ad.2. Pewnie to nie jest takie proste i da się poniżej 3 ważeń, ale nie wymyśliłem :)
OdpowiedzUsuńJa bym po prostu zważył najpierw po 4 kule na każdej szalce, odrzucił tą cięższą czwórkę, podzielił lżejszą na pary i porównał ich wagi, odrzucił cięższą parę i porównał wagi pozostałych dwóch :)
Typowy problem o złożoności logarytmicznej :) I tutaj pewnie natrafiam na problem szablonowości swojego myślenia :)
Widzę, że przygotowania do rozmów kwalifikacyjnych pełną parą :)
OdpowiedzUsuńFajne zagadki, ja jakoś nigdy szukając pracy nie trafiałem na rozmowę kwalifikacyjną z zagadkami :(
No może prawie nigdy, bo pół roku temu miałem powiedzieć, jak w systemie zapisującym datę w postaci DDMMRRXX, gdzie XX to suma kontrolna, można wprowadzić rozróżnienie pomiędzy rokiem 1900 a 2000, ale to bardziej informatyczna zagadka niż logiczna.
Z tymi studzienkami (3) to mnie zagiąłeś, ja bym powiedział, że dlatego, że rury mają okrągły przekrój ze względu na to, że powierzchnia koła w stosunku do obwodu jest największa spośród wszystkich figur. Ale możliwe, że są okrągłe, żeby człowiek mógł się zmieścić jak tam wchodzi lub, żeby nie wpadła do środka (kwadratową studzienkę można by było wepchnąć po przekątnej, ale np. z trójkąta równobocznego by się też nie dało wepchać)
Co do pytania o torcie (5), zadam pytania pomocnicze, bo nie bardzo rozumiem treść :D
- Czy dowolne położenie wyciętego fragmentu oznacza, że może on być wycięty ze środka (czyli wycięty kawałek nie styka się z krawędziami tortu)?
- Czy jesteśmy w stanie ustalić, gdzie jest środek (lub np. 1/3) krawędzi tortu?
Co do 7, to przypominają mi się stare dobre czasy meczy matematycznych w LO i zasada szufladkowa Dirichleta :D ah, te stare dobre czasy :P
Pokuszę się o udzielenie odpowiedzi na pytania:
1)1 - istotne jest to, że wiemy, iż teraz żaden podpis nie jest na swoim miejscu, więc zaczynamy od koszyka podpisanego jako mieszanka
2)2 ważenia - kładziemy z jednej strony 3 kule, z drugiej 3, jeśli jest równowaga, to znaczy, że musimy zważyć pozostałe 2 kule, jeśli nie, kładziemy po 1 kuli na szalce z tych, co znajdowały się na lżejszej szalce, jeśli są w równowadze, trzecia kula jest lżejsza, jeśli nie są w równowadze, wiemy, która jest lżejsza
3)patrz wyżej
4)z takim samym zadaniem musiał się zmierzyć Bruce Willis w Szklanej Pułapce 3. Dobrze, że pomógł mu Samuel L Jackson, bo koleś wyleciałby w powietrze :). Wlewamy do 5 litrowego wodę, przelewamy do 3 litrowego, w ten sposób mamy 2 litry. Opróżniamy 3 litrowy, wlewamy do niego 2 litry z 5-litrowego, więc mamy w nim 1 litr zapasu. Wlewamy z jeziora wodę do 5-litrowego i przelewamy z niego wodę do 3-litrowego, gdzie jest miejsce tylko na 1 litr
6)3 ważenia - ważę 3 słoiki, w pesymistycznym przypadku wsród nich jest lżejszy. Ważę 2 z ich. Pesymistycznie 1 z nich jest lżejszy, ważę ostatni raz 1 z nich i już wiem.
7) 4
8) 1, 2, 4 bo 1=1, 2=2, 3=1+2, 4=4, 5=1+4, 6=2+4, 7=1+2+4
Ad.3. Jedyny pomysł na jaki wpadłem (być może głupi :)) - gdy jest okrągła, to nie ma takiej możliwości, by wpadła do środka :) Ale inne figury (jak np. trójkąt równoboczny) też mają takie "właściwości" :)
OdpowiedzUsuńAd.4. Klasyka:)
Zbiornik 5l do pełna.
Wodą ze zbiornika 5l napełniamy mniejszy zbiornik.
W dużym zbiorniku zostają 2l wody.
Opróżniamy mały zbiornik i przelewamy otrzymane 2l z dużego do małego.
Znowu napełniamy zbiornik 5l. Wodą z niego dopełniamy zbiornik 3l (zostało tam tylko 1l wolnego objętości). 5l-1l=4l w dużym zbiorniku :)
Ad.5. Tniemy w płaszczyźnie równoległej do blatu stołu na połowie wysokości tortu :)
Ad.6. Wystarczy jedno ważenie. Oznaczamy słoiki liczbami od 1 do 5. Wyciągamy z danego słoika tyle pigułek ile wynosi numer danego słoika, czyli razem 15 pigułek. Ważymy je wszystkie razem. Od liczby 1 odejmujemy część dziesiętną otrzymanej wagi i mamy numer słoika z trucizną :)
Ad.7. Na żadne fajne rozwiązanie nie wpadłem :)
Ad.8. W miarę proste. 2 cięciami możemy podzielić na 3 części: 1/7, 2/7 i 4/7.
Po 1 dniu dostaje 1/7
Po 2 dniach dostaje 2/7
Po 3 dostaje 1/7 + 2/7
Po 4 dostaje 4/7
Po 5 dostaje 4/7 + 1/7
Po 6 dostaje 4/7 + 2/7
Po 7 dostaje wszystko.
Niby prawie wszystkie rozwiązałem (nie wiem czy dobrze). Ale chyba tylko 4 (bo znałem wcześniej) i 8 rozwiązałem na tyle łatwo i szybko, że zdołałbym to zrobić na rozmowie kwalifikacyjnej, gdzie jednak jest trochę stresu. Z resztą byłoby dużo gorzej :)
@Mateusz: Kurde, to pytanie ze skarpetkami to był taki banał i nie wpadłem :)
OdpowiedzUsuńNo, ja tak samo -- nie wszystkie od razu. Tort wpadł mi do głowy dobrych kilka godzin po tym, jak przeczytałem listę zadań. Kłania się logika i nakładanie ograniczeń "z życia", które wcale nie są takie oczywiste w zagadkach... I jeśli ograniczeń nie podano, to przyjąć że ich nie ma... To samo z kulami zrobiłem. Nie wiedzieć dlaczego założyłem, że można zmieścić tylko po jednej kuli na szalkę. :>
OdpowiedzUsuńNo, z tortem to hardkor był i nie wpadłbym sam na rozwiązanie. Co do słoika z pigułkami, nie wpadłem na to, że można wyciągać dowolną ilość pigułek ze słoika, więc też zdupiłem. A studzienka kanalizacyjna - do tej pory nie wiem, jaka jest prawidłowa odpowiedź :)
OdpowiedzUsuń@bitrut:
OdpowiedzUsuń"Ad.4. Klasyka:)
Zbiornik 5l do pełna.
Wodą ze zbiornika 5l napełniamy mniejszy zbiornik.
W dużym zbiorniku zostają 2l wody.
Opróżniamy mały zbiornik i przelewamy otrzymane 2l z dużego do małego.
Znowu napełniamy zbiornik 5l. Wodą z niego dopełniamy zbiornik 3l (zostało tam tylko 1l wolnego objętości). 5l-1l=4l w dużym zbiorniku :)"
Ad.4 Jest jeszcze jedno rozwiązanie.
Napełniasz 3l przelewasz do 5l.
Napełniasz znowu 3l przelewasz ile wejdzie do 5l.
W 3l zostaje 1l wody.
Wylewasz z 5l, przelewasz z 3l (1l) do 5l.
Napełniasz 3l i dolewasz do 5l(1l): 1l + 3l = 4l
Ad.3 Studzienki są okrągłe, żeby pokrywa nie wpadła a jednocześnie to taki kształt w którym środek jest odległy dokładnie tak samo od każdej krawędzi co może się przekładać na obciążenia na obwodzie ;)
Ad.5 Wykonać cięcie poziomo ;)
Ad.6 Zagadka jest nieprecyzyjna, nie wiadomo czy w słoikach znajduje się taka sama ilość pigułek (sztuk).
Ad.7 Podobnie jak 6, przydałoby się doprecyzować czy każdego koloru jest taka sama ilość?
@maddox:
OdpowiedzUsuńTwoje wątpliwości przy zadaniu 6 nie mają znaczenia przy moim rozwiązaniu.
To samo w zadaniu 7, gdy brać pod uwagę rozwiązanie Mateusza :)
To ja przyznaję teraz nagrody* :P Kolejność skomentowania się liczy ;)
OdpowiedzUsuńAd. 1 - bitrut, wystarczy wyciągnąć raz :)
Ad. 2 - Mateusz, dwa ważenia.
Ad. 3 - bitrut, bo pierwszy przy odpowiedzi "żeby nie wpadła do środka" nie napisał "może" ;) Ale to jest zagadka na kreatywność i ciężko powiedzieć czy w ogóle ma rozwiązanie ;) Ale... trójkąt równoboczny też nie wpadnie do środka - więc dlaczego wybrano właśnie koło? :)
Ad. 4 - Samuel L. Jackson :)
Ad. 5 - bitrut, to jest jedno z prawidłowych rozwiązań i to najbardziej kreatywne :) Istnieje rozwiązanie, gdzie cięcie wykona się prostopadle do stołu, a parametry cięcia można ustalić tylko z użyciem linijki bez podziałki ;) I tak, usunięty kawałek może być na brzegu tortu albo w ogóle się z brzegiem nie stykać.
Ad. 6 - bitrut, jedno ważenie.
Ad. 7 - Mateusz, 4 skarpetki.
Ad. 8 - Mateusz, podział na 1, 2 i 4 (dwa cięcia).
* - nagrody są abstrakcyjne i nie mają implementacji
Żeby nie było - w przypadku zagadki numer 5 wcale nie jestem taki mądry, po prostu materiał źródłowy zawierał również odpowiedź (i to tą mniej kreatywną) ;) Dlatego też nie dałem linka z serii "Więcej" ;)
No z tym cięciem tortu poziomo to trochę lipa jest :) Ktoś dostanie sam biszkopt, a inny samą galaretkę z kremem :)
OdpowiedzUsuńW sumie racja :) W takim razie zagadka nr 5 w dalszym ciągu czeka na rozwiązanie :) W poszukiwaniach niech pomoże wskazówka, że to ma coś wspólnego ze środkiem ciężkości wybrakowanego tortu ;)
OdpowiedzUsuńCo do zagadki 5 to linia cięcia powinna przechodzić przez środek całego tortu (przecięcie się przekątnych) jak i przez środek wyciętego kawałka (również przecięcie przekątnych, ale wyciętego kawałka). Dzięki temu nie jest istotne w którym miejscu tortu znajduje się wycięty kawałek.
OdpowiedzUsuńCo do przecięcia w płaszczyźnie poziomej to szacun za pomysł.
Co do rozwiązań zagadek nr 2 i 6 to dzięki za pokazanie dobrych, nieszablonowych rozwiązań.
Miałam przyjemność zetknąć się na rozmowie z pytaniem o studzienkę. Odpowiedź jest banalna. Tu nie chodzi o to czy pokrywa wpadnie do studzienki, czy żeby łatwiej było wejść.
OdpowiedzUsuńStudzienka i jej pokrywa są okrągłe bo w ten sposób można je łatwiej przemieścić na miejsce docelowe - przetoczyć. Taka studzienka to nie jest lekka rzecz, więc gdyby była kwadratowa to kilku chłopa musiałoby ją zataszczyć na miejsce albo użyć jakiegoś typu podnośnika, a tak wystarczy studzienkę pzekipnąć na bok i jeden chłopina potoczy ją w dowolne miejsce.