Najlepszy sposób wyszukiwania wartości nasycenia na posortowanej liście

Question

Pytanie od Math Battle. To konkretne pytanie zadano mi również w jednym z moich rozmów kwalifikacyjnych.

"Małpa ma dwa kokosy. Jest wygłupiać rzucając kokos dół z balkonów M-piętrowego budynku. Małpa chce wiedzieć najniższą podłogę kiedy kokosowy jest zepsuty. Jaka jest minimalna liczba prób potrzebne do ustalenia tego faktu? "

Warunki: jeśli orzech kokosowy jest uszkodzony, nie można go użyć ponownie. Pozostaje ci tylko z drugiej kokosa

możliwych podejść/strategie mogę myśleć są

• binarne rozpad & po znalezieniu podłoga, na której pęka kokosowych wykorzystania zliczania w gór' od ostatniego znaleziono Binary przerwę niższy indeks.
• Okno/Plastry mniejszych zestawów podłóg & użycie binarnego rozkładają się w oknie/Plaster (ale na dół strony wymagałoby to algorytm Odcinanie na jego rękę.)

Zastanawiasz się, czy są jakieś inne sposoby na zrobienie tego.

Answer 1

Wyszukiwanie binarne nie jest odpowiedzią, ponieważ masz tylko jedną szansę na przeszacowanie. Wyszukiwanie binarne wymaga maksymalnych przecenień.

Jest to podejście dwufazowe. Pierwsza polega na iteracji po piętrach ze stosunkowo dużymi krokami. Po pierwszym pęknięciu kokosa, drugą fazą jest wypróbowanie każdego piętra, począwszy od ostatniej bezpiecznej podłogi.

Duże kroki to w przybliżeniu sqrt(m), ale są większe wcześniej, a mniejsze później, ponieważ jeśli pierwszy kokos pęknie wcześniej, możesz pozwolić sobie na więcej powtórzeń w drugiej fazie.

StepSize = (minimum s such that s * (s + 1)/2 >= m) 
CurrentFloor = 0 

While no coconuts broken { 
    CurrentFloor += StepSize 
    StepSize -= 1 

    Drop coconut from CurrentFloor 
} 

CurrentFloor -= StepSize + 1 

While one remains coconut unbroken { 
    CurrentFloor += 1 
    Drop remaining coconut from CurrentFloor 
} 

// CurrentFloor is now set to the lowest floor that will break the coconut, 
// using no more total drops than the original value of StepSize 

Answer 2

Najlepszym rozwiązaniem, jakie znam, jest 2 * sqrt (n). Upuść pierwszy kokos z sqrt (n), 2 * sqrt (n), ... aż do n (lub dopóki się nie zepsuje). Następnie upuść drugi z ostatniego znanego "bezpiecznego" punktu, w jednym kroku, aż pęknie. Oba etapy przyjmują co najwyżej rzuty sqrt (n).

Edytuj: Możesz poprawić stałą w O (sqrt (n)), patrz komentarz przez rekurencję. Myślę, że pierwszy krok powinien wynosić około sqrt (2 * n) i zmniejszyć o 1 przy każdym rzucie, tak, że ostatni krok (jeśli wysokość zerwania wynosi faktycznie n) wynosi dokładnie 1. Szczegóły do ​​ustalenia przez czytelników :)

Answer 3

Takie pytania na temat wywiadu mają na celu sprawdzenie, jak myślisz. Tak więc prawdopodobnie wspomnę o rozwiązaniu O (N^0,5) jak powyżej, ale także podaję następującą dyskusję ...

Ponieważ kokosy mogą mieć pęknięcia wewnętrzne w czasie, wyniki mogą nie być tak spójne z Roztwór O (N^0,5). Chociaż rozwiązanie O (N^0,5) jest wydajne, nie jest ono całkowicie niezawodne.

Polecam liniowe rozwiązanie O (N) z pierwszym kokosem, a następnie sprawdź wynik z drugim kokosem. Gdzie N jest liczbą pięter w budynku. Więc na pierwszy kokos wypróbujesz pierwsze piętro, potem drugie, trzecie ...

Zakładając, że oba kokosy są zbudowane dokładnie tak samo i spadają pod tym samym kątem, można wyrzucić drugi kokos bezpośrednio na podłogę, z której pękł pierwszy. Nazwij tę łamliwą podłogę kokosa B.

Dla kokosa # 2, nie musisz testować na 1.B-1, ponieważ wiesz już, że pierwszy kokounut nie pękł na podłodze B-1, B- 2, ... 1. Więc wystarczy wypróbować na B.

Jeśli drugi kokos pęknie na B, to wiesz, że B to podłoga, o której mowa. Jeśli się nie złamie, możesz wywnioskować, że nastąpiło wewnętrzne pękanie i degradacja kokosa w czasie i że test jest wadliwy na samym początku. Potrzebujesz więcej orzechów kokosowych.

Biorąc pod uwagę, że rozmiary budynków są dość ograniczone, dodatkowe zaufanie do rozwiązania jest warte rozwiązania O (N).

As @ Rafał Dowgird wspomniał, że rozwiązanie zależy również od tego, czy dana małpa jest afrykańską małpą, czy europejską małpą. Powszechnie wiadomo, że afrykańskie małpy rzucają z dużo większą siłą. W związku z tym wykonanie podłogi łamanej B jest dokładne tylko przy wariancji +/- 2 kondygnacji.

Aby zagwarantować, że małpa nie zmęczy się ze wszystkich schodów, wskazane jest również przymocowanie sznurka do pierwszego kokosa. W ten sposób nie musisz wykonywać 1 + 2 + .. + B = B * (B + 1)/2 schodów na pierwszy kokos. Trzeba by tylko wykonać dokładnie te schody.

Może się wydawać, że liczba lotów schodów nie ma związku z tym problemem, ale jeśli małpa jest zmęczona w pierwszej kolejności, możemy nigdy nie dojść do rozwiązania. To daje nowe powody dla halting problem.

Przyjmujemy również założenie, że budynek znajduje się na ziemi, a grawitacja jest ustawiona na 9,8 m/s^2. Przyjmiemy również, że nie istnieją fale grawitacyjne.

Answer 4

Ponieważ jest to pytanie wywiad, uważają

1. Drogie operacja jest małpa idzie w górę iw dół po schodach, nie rzucając kokosa. Myśląc o tym w ten sposób, podejście "liniowe" jest w rzeczywistości N .

2. Energia przekazywana kokosowi przez upadek jest w przybliżeniu proporcjonalna do wysokości kropli. Jeśli powłoka zostanie uszkodzona po pochłonięciu pewnej ilości energii we WSZYSTKICH jej upadkach ...

Answer 5

Trudne pytanie z wywiadu. Zajęło mi to kilka dni.

Uważam, że liczba prób wynosi 1,5 razy SQRT z # pięter. (Dla 100 pięter i 2 coco jest to 15)

Chcemy zminimalizować rozmiar każdej próby i liczbę prób, wykorzystując obie razem do pokrycia wszystkich możliwych pięter. W takich przypadkach sqroot okazuje się dobrym punktem wyjścia, ale zmienimy rozmiar każdej próby i średnią wokół sqroot. W ten sposób mamy to, co najlepsze z obu światów: posiadanie rozmiaru każdej próby równomiernie rozmieszczonej wokół sqroot daje nam najlepsze wyniki. Dla 100 i 2 jest to 15,14,13,12,11,10,9,8,7,6 To działa do 1,5 razy 10.