Dwie kulki i 100 piętrowy budynek

Problem ten jest omówiony w problemie 6.5 Z Książki "Cracking the Coding Interview (5th) ", z rozwiązaniami podsumowanymi następująco:

Obserwacja:

Niezależnie od tego, jak zrzucimy Marble1, Marble2 musi wykonać wyszukiwanie liniowe. Np. jeśli Marble1 przerwy między piętrem 10 i 15, musimy sprawdzić każde piętro pomiędzy Z marble2

Podejście:

Pierwsza próba: Załóżmy, że zrzucimy marmur z 10. piętra, a następnie 20., …

• w pierwszych pęknięciach marmuru przy pierwszej kropli (Piętro 10), wtedy mamy co najwyżej 10 kropli w sumie.
• Jeśli pierwszy Marmur pęknie na ostatniej kropli (piętro 100), to mamy co najwyżej 19 kropli w sumie (piętra od 1 do 100, potem 91 do 99).
To całkiem niezłe, ale rozważamy tylko najgorszy przypadek. Powinniśmy wykonaj "równoważenie obciążenia", aby te dwa przypadki były bardziej równomierne.

Cel: stworzyć system do upuszczania Marble1 tak, że większość wymaganych kropli jest spójna, niezależnie od tego, czy marble1 łamie się przy pierwszym spadku, czy ostatnim spadku.

1. idealnie wyważony układ byłby taki, w którym krople Marble1 + krople Marble2 jest zawsze taki sam, niezależnie od tego, gdzie marble1 pękł.
2. aby tak było, ponieważ każda kropla Marble1 wymaga jeszcze jednego kroku, marble2 jest dozwolone jeden krok mniej.
3. musimy zatem zmniejszyć liczbę kroków potencjalnie wymaganych przez Marble2 by one rzucaj za każdym razem. Na przykład, jeśli Marble1 zostanie upuszczone na piętro 20, a następnie piętro 30, Marble2 jest potencjalnie wymagane do podjęcia 9 kroków. Kiedy ponownie opuszczamy Marble1, musimy zredukować potencjalne kroki Marble2 do tylko 8. np. musimy zrzucić Marble1 na piętro 39.
4. wiemy więc, że Marble1 musi zaczynać od piętra X, potem iść w górę o piętra x-1, Potem X-2, …, dopóki nie osiągnie 100.
5. Rozwiąż dla X+(X-1)+(X-2)+...+1 = 100. X (X+1)/2 = 100 -> X = 14

Idziemy do Piętro 14, potem 27, potem 39, ... To zajmuje maksymalnie 14 kroków.

Kod & Rozszerzenie:

• Aby zaimplementować Kod, możesz sprawdzić tutaj .

• Aby rozszerzyć N marmury, Mpodłogi, sprawdź Rozdział 12: puzzle jaj i podłóg.

Każdy z nich pęka, gdy spada z tej samej wysokości, czy są inne?

Jeśli są takie same, idę na 50 piętro i upuszczam pierwszy marmur. Jeśli się nie zepsuje, idę na 75 piętro i robię to samo, dopóki się nie psuje, idę w górę o 50% tego, co zostało. Kiedy się zepsuje, wracam o jeden wyższy niż wcześniej (więc jeśli zepsuje się na 75. piętrze, wracam na 51. piętro), rzucam drugi marmur i wspinam się na podłogę na raz, aż się zepsuje. breaks, w którym to momencie znam najwyższe piętro, z którego mogę spaść bez pękania marmuru.

Prawdopodobnie nie najlepsza odpowiedź, jestem ciekaw, jak inni odpowiedzą.

Ja osobiście nie przepadam za takimi zagadkami logicznymi, wolę rzeczywiste ćwiczenia programistyczne w wywiadach.

To powiedziawszy, najpierw zależy od tego, czy mogę stwierdzić, czy są zepsute, czy nie z podłogi, na którą je upuszczam. Zakładam, że mogę.

Poszedłbym na drugie piętro, zrzucił pierwszy marmur. Gdyby się zepsuł, spróbowałbym na pierwszym piętrze. Gdyby się zepsuł, wiedziałbym, że to nie podłoga.

Gdyby pierwsza nie pękła, poszedłbym na 4 piętro i spadł stamtąd. Gdyby się zepsuł, wróciłbym po drugi marmur, a następnie spadł na 3 piętro, łamiąc czy nie, wiedziałbym, który jest limit.

Jeśli żadne z nich nie jest zepsute, pójdę po oba i zrobię ten sam proces, tym razem zaczynając od szóstego piętra.

W ten sposób, mogę pominąć każde inne piętro, dopóki nie dostanę marmuru, który pęknie.

Zostanie to zoptymalizowane, jeśli marmur pęknie wcześnie... Przypuszczam, że jest prawdopodobnie optymalna ilość podłóg, którą mógłbym pominąć, aby uzyskać Większość dla każdego skipa... ale jeśli ktoś się zepsuje, musiałbym sprawdzić każde piętro indywidualnie z pierwszego piętra nad ostatnim znanym piętrem... co oczywiście byłoby bólem, gdybym pominął zbyt wiele pięter(przepraszam, nie zamierzam teraz znaleźć optymalnego rozwiązania).

Idealnie, chciałbym całą torbę kulek, wtedy mógłbym użyć binarnego algorytmu wyszukiwania i podzielić liczbę pięter na pół z każdej kropli... ale to nie było pytanie, prawda?

Myślę, że Prawdziwe pytanie jest jak dokładne chcesz odpowiedzi. Bo od tego zależy Twoja skuteczność.

Zgodzę się z Justinem, jeśli chcesz 100% dokładności na marmurkach, to gdy pierwszy marmur pęknie, będziesz musiał przejść 1 piętro na raz od ostatniego znanego" dobrego " piętra, dopóki nie dowiesz się, które piętro jest "zwycięzcą"."Może nawet dorzuć trochę statystyk i zacznij od 25. piętra zamiast 50. piętra, aby być najgorszym scenariusz byłby 24 zamiast 49.

Jeśli odpowiedź może być plus lub minus piętro lub dwa, to może być kilka optymalizacji.

Po drugie, czy chodzenie po schodach liczy się z Twoją skutecznością? W takim przypadku zawsze upuść obie kulki i podnieś obie kulki na każdej podróży w górę / w dół.

Upuść pierwszy marmur na podłodze 10, 20, 30 itd. dopóki nie pęknie, wskakuj z powrotem na ostatnią znaną dobrą podłogę i zacznij spadać z niej po jednym piętrze na raz. W najgorszym przypadku 99 jest magiczną podłogą i zawsze można ją znaleźć w 19 kroplach lub mniej.

Zrzuć pierwszy marmur z trzeciego piętra. Jeśli się zepsuje, wiesz, że jest Piętro 1 lub 2, więc rzuć drugi marmur z piętra 2. Jeśli się nie złamie, odkryjesz, że piętro 2 jest najwyższe. Jeśli się zepsuje, odkryjesz, że Piętro 1 jest najwyższe. 2 krople.

Jeśli upuszczenie z 3 piętra nie złamie marmuru, upuść z 6 piętra. Jeśli się zepsuje, wiesz, że Piętro 4 lub 5 jest najwyższe. Wyrzuć drugi marmur z piętra 5. Jeśli się nie zepsuje to stwierdziłeś, że 5 jest najwyższe. Jeśli tak, Piętro 4 jest najwyższe. 4 krople.

Kontynuuj.

3 piętra-maksymalnie 2 krople

6 pięter-maksymalnie 4 krople

9 pięter-maksymalnie 6 kropli

12 pięter-maksymalnie 8 kropli

Itd.

3x podłogi-maksymalnie 2x krople

Więc dla budynku na 99 piętrze masz maksymalnie 66 kropli. I to jest maksimum. Pewnie masz mniej kropli. A 66 to maksimum dla 100-piętrowego budynku. Potrzebowałbyś tylko 66 kropli, gdyby rozbite piętro było 98 lub 97. Gdyby było 100, użyłbyś 34 kropli.

Mimo, że powiedziałeś, że to nie ma znaczenia, prawdopodobnie wymagałoby to najmniejszej ilości chodzenia i nie musisz wiedzieć, jak wysoki jest budynek.

Problem polega na tym, jak definiujesz efektywność. Czy jest to bardziej "wydajne", aby zawsze mieć rozwiązanie w mniej niż X kropli, czy jest to bardziej wydajne, aby mieć duże szanse na rozwiązanie w y kropli gdzie Y

Można to zrobić lepiej za pomocą zaledwie 7 kulek.

Więc po głosowanej odpowiedzi powiedzmy, że marmur pęknie na co najmniej 49 piętrze.

1. 50 piętro - > przerwy (odpowiedź jest od 1 do 50 włącznie)
2. 25 piętro - > nie pęka (od 26 do 50)
3. 37 piętro - > nie pęka (38 do 50)
4. 43 piętro - > nie pęka (44 do 50)
5. 46 piętro - > nie pęka (47 do 50)
6. 48 piętro -> nie pęka (49 lub 50)
7. 49th floor -> breaks (49th, ten krok jest rzeczywiście potrzebny, ponieważ może to być minimalna Podłoga dla marmuru do złamania jest na 50th)

Można to sobie wyobrazić jako wyszukiwanie binarne w posortowanym zbiorze dla pewnego k, gdzie przy każdej próbie mamy połowę przestrzeni rozwiązania. Dla 100 pięter potrzebujemy log2 100 = 6.644 (7 prób). Z 7 marmurów możemy być pewni, która jest minimalna podłoga, że marmur rozbije się do 128 kondygnacji.

Pierwszą rzeczą, którą chciałbym zrobić, to użyć martwego prostego algorytmu, który zaczyna się od podłogi 1, upuszcza marmur na jedno piętro na raz, aż osiągnie 100 lub marmur pęknie.

Wtedy zapytałbym, dlaczego mam poświęcać czas na optymalizację go, dopóki somone nie pokaże, że będzie to problem. Zbyt wiele razy ludzie się zawiesić na znalezienie idealnego skomplikowanego algorytmu, gdy znacznie prostszy rozwiąże problem. Innymi słowy, nie Optymalizuj rzeczy, dopóki nie będzie to potrzebne.

This might be trick pytanie, czy jesteś jednym z tych ludzi, którzy mogą zrobić górę z wzgórza Kreta.