Două marmură și o clădire cu 100 de etaje

Una dintre aceste întrebări clasice de interviu de programare ...

Vi se dau două marmură și le-a spus că se vor rupe când vor cădea de la o anumită înălțime (și probabil nu vor suferi daune dacă ar scăpa de sub această înălțime). Tu te duci apoi la o clădire de 100 de etaje (probabil mai mare decât înălțimea certă) și ai cerut să găsești cel mai înalt nivel pe care-ți poți lăsa o marmură fără să o spargi cât mai eficient posibil.

Informații suplimentare

  • Trebuie să găsiți podeaua corectă (nu este un interval posibil)
  • Marmura este garantată că se rupe la același etaj
  • Să presupunem că este nevoie de zero timp pentru ca dvs. să schimbați podelele - numai numărul de picături de marmură contează
  • Să presupunem că etajul corect este distribuit aleatoriu în clădire
0
fr hi bn
Aveți nevoie de un algoritm pentru găsirea eficientă a podelei (ceea ce ar trebui să vă ducă atât la numărul maxim de picături necesare pentru abordarea dvs., cât și la un set de pași pentru a face acest lucru).
adăugat autor Matt Sheppard, sursa
@ Brad Wilson: acest lucru depinde în întregime de interviu ... este o mare întrebare pentru a verifica gândirea logică și abilitățile de rezolvare a matematicii.
adăugat autor Karoly Horvath, sursa
Este probabil mai bine să nu presupunem că podeaua corectă este repartizată aleatoriu și, în schimb, trebuie doar să vină cu o soluție pentru a minimiza cel mai rău caz.
adăugat autor Dave L., sursa
Acest lucru are un destul de mare "aha!" factor pentru cineva care nu a studiat matematica. Întrebări cu "aha!" factori sunt excepțional de rele pentru interviuri.
adăugat autor Brad Wilson, sursa
Titlul întrebării nu indică în mod clar: trebuie să găsim podeaua maximă din care să putem lăsa marmura fără să o rupem sau, după cum sugerează răspunsul, numărul minim de încercări de a ajunge la etajul respectiv ...? !
adăugat autor KeyBrd Basher, sursa

9 răspunsuri

Eu personal nu sunt un fan mare de astfel de întrebări puzzle, eu prefer exerciții de programare real în interviuri.

Acestea fiind spuse, mai intai ar depinde daca pot sa spun daca sunt rupte sau nu de pe podea la care le las. Voi presupune că pot.

M-aș duce la etajul al doilea, aruncând prima marmură. Dacă ar fi rupt, aș încerca primul etaj. Dacă ar fi rupt, aș ști că nu era etaj.

Dacă prima nu sa rupt, m-aș duce la etajul al patrulea și să scap de acolo. Dacă s-ar rupe, m-aș întoarce în jos și voi lua cealaltă marmură, apoi voi cădea la etajul 3, rupând sau nu, știam care este limita.

Dacă nici unul nu a rupt, aș merge să am și amândouă și să fac același proces, de data aceasta începând de la etajul 6.

În acest fel, pot sări peste fiecare alt etaj până când voi obține o marmură care se rupe.

Acest lucru ar fi optimizat dacă marmura se va rupe mai devreme ... Presupun că există probabil o cantitate optimă de pardoseală pe care aș putea să o sărind pentru a obține cele mai multe pentru fiecare săritură ... dar atunci, dacă o pauză, ar trebui să verific fiecare podea individual de la primul etaj de deasupra ultimei etaje cunoscute ... care, bineînțeles, ar fi o durere dacă am sări peste prea multe etaje (îmi pare rău, nu voi găsi soluția optimă chiar acum).

În mod ideal, aș vrea un sac întreg de marmură, aș putea să folosesc un algoritm de căutare binară și să împart numărul de etaje la jumătate cu fiecare picătură ... dar apoi nu era întrebarea, nu-i așa?

0
adăugat
Ai auzit vreodată de Abordarea Forței Brute Mike ........
adăugat autor KeyBrd Basher, sursa

Fiecare dintre ei se sparg cand coboara din aceeasi inaltime, sau sunt diferiti?

Dacă sunt la fel, mă duc la etajul 50 și arunc prima marmură. Dacă nu se rupe, mă duc la etajul 75 și fac același lucru, atâta timp cât nu mă rupe, continuă să mă ridic cu 50% din ceea ce a mai rămas. Când se sparge, m-am întors la unul mai sus decât în ​​cazul în care eram înainte (așa că, dacă s-ar rupe la etajul 75, mă întorc la etajul 51) și arunc a doua marmură și mă mișc într-un moment până când se rupe, moment în care știu cel mai înalt etaj din care pot cădea fără ruperea marmurei.

Probabil că nu este cel mai bun răspuns, sunt curios să văd cum răspund ceilalți.

0
adăugat

Aruncați prima marmură de la etajul 3. Dacă se sparge, știi că este etajul 1 sau 2, așa că renunță la celălalt marmură de la etajul 2. Dacă nu se rupe, ai descoperit că etajul 2 e cel mai înalt. Dacă se sparge, ați descoperit că etajul 1 este cel mai înalt. 2 picături.

Dacă scăpând de la etajul 3 nu rupe marmura, picătură de pe podea 6. Dacă se rupe, știți că etajul 4 sau 5 este cel mai înalt. Aruncați a doua marmură de la etajul 5. Dacă nu se rupe, ați descoperit că 5 este cea mai înaltă. Dacă da, etajul 4 este cel mai înalt. 4 picături.

Continua.

3 etaje - maxim 2 picături

6 etaje - maxim 4 picături

9 etaje - maxim 6 picături

12 etaje - maximum 8 picături

etc.

Podea 3x - maxim 2 picături

Deci, pentru o cladire de 99 etaj ai maxim 66 de picaturi. Și asta este maximul. Probabil că ai mai puține picături decât asta. Oh, iar 66 este maximul pentru o clădire cu 100 de etaje. Aveți nevoie doar de 66 de picături dacă pardoseala a fost etajul 98 sau 97. Dacă pardoseala a fost de 100, ați folosi 34 de picături.

Chiar dacă ați spus că nu contează, acest lucru ar necesita, probabil, cea mai mică cantitate de mers pe jos și nu trebuie să știți cât de înaltă este clădirea.

Part of the problem is how you define efficiency. Is it more "efficient" to always have a solution in less than x drops, or is it it more efficient to have a good chance at having a solution in y drops where y < x with the caveat that you could have more than x drops?

0
adăugat

Așezați prima marmură la podeaua 10, 20, 30 etc., până când se rupe, apoi săriți înapoi pe ultima etajată bună și începeți să aruncați marmură de acolo într-un singur etaj. Cel mai grav caz este 99 fiind Etajul Magic și îl puteți găsi întotdeauna în 19 picături sau mai puțin.

0
adăugat

Această problemă este acoperită în Problema 6.5 de la Cartea " Ștergerea interviului de codificare (a 5-a) " , cu soluții rezumate după cum urmează:

Observare:

Indiferent de modul în care lăsăm Marble1, Marble2 trebuie să facă o căutare liniară. De exemplu, dacă marmura1 pauze între etajele 10 și 15, trebuie să verificăm fiecare etaj între Marmură2


Apropierea:

A First Try: Suppose we drop an Marble from the 10th floor, then the 20th, ?

  • În primele pauze de marmură la prima picătură (Etajul 10), atunci avem cel mult 10 picături în total.
  • Dacă primul Marmură se rupe la ultima picătură (Etajul 100), atunci avem cel mult 19 picături totale (etajele 1 până la 100, apoi 91 până la 99).
  • E destul de bun, dar tot ceea ce noi considerăm este cel mai rău caz absolut. Noi ar trebui să face unele? încărcare de echilibrare? pentru a face aceste două cazuri mai echilibrate.

Goal: Create a system for dropping Marble1 so that the most drops required is consistent, whether Marble1 breaks on the first drop or the last drop.

  1. A perfectly load balanced system would be one in which Drops of Marble1 + Drops of Marble2 is always the same, regardless of where Marble1 broke.
  2. For that to be the case, since each drop of Marble1 takes one more step, Marble2 is allowed one fewer step.
  3. We must, therefore, reduce the number of steps potentially required by Marble2 by one drop each time. For example, if Marble1 is dropped on Floor 20 and then Floor 30, Marble2 is potentially required to take 9 steps. When we drop Marble1 again, we must reduce potential Marble2 steps to only 8. eg, we must drop Marble1 at floor 39.
  4. We know, therefore, Marble1 must start at Floor X, then go up by X-1 floors, then X-2, ?, until it gets to 100.
  5. Solve for X+(X-1)+(X-2)+?+1 = 100. X(X+1)/2 = 100 -> X = 14

Mergem la Etajul 14, apoi la 27, apoi la 39,? Aceasta durează maximum 14 pași.


Code & Extension:

0
adăugat
vă rog să comentați rațiunea din spatele ecuației din pasul 5 de mai sus?
adăugat autor Geek, sursa
@Geek Trebuie doar să acoperiți toată gama de 100 cu intervale descendente. Am vrut să o facem echilibrată, astfel încât sarele să fie în etaje: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95. De fiecare dată când este crescut un etaj mai puțin. În acest fel, chiar dacă renunțăm la prima oară de 10 ori, avem nevoie doar de 4 picături. 10 +4 = 14, ca și cum s-ar rupe la primul etaj.
adăugat autor borjab, sursa
@Dinaiz Totaldrops = Marmură1Dropuri + Marmură2Dropuri. Dacă doriți ca valoarea TotalDrops să rămână aceeași (cel mai rău caz), atunci când Marble1Drops crește, Marble2Drops trebuie să scadă. de exemplu. Să presupunem TotalDrops = 10. Dacă Marble1Drops = 1 atunci Marble2Drops = 9. Dacă Marble1Drops = 2, apoi Marble2Drops = 8 și așa mai departe.
adăugat autor Davos, sursa
@Geek Puteți începe prin asumarea celor mai grave x = 100 , adică veți face 100 de picături. Nu poate fi mai rău decât 100, pentru că există doar 100 de etaje de testat. Următorul pas este să încercați să împărțiți spațiul pe jumătate. adică drop unul la aproximativ jumătate. Deci, este ca 2x = 100 , dar nu destul. Este cu adevărat x + (x-1) = 100 , al doilea segment este x-1 deoarece etajele sunt două segmente care vor fi testate de jos în sus. În cazul în care marmura este neîntreruptă pentru primul segment, ați utilizat 1 picătură, astfel încât să a
adăugat autor Davos, sursa
"Ca să fie așa, din moment ce fiecare picătură de marmură1 face un pas, Marble2 are un pas mai mic." . Nu înțeleg această parte. Ați putea să vă explicați?
adăugat autor Dinaiz, sursa

Primul lucru pe care aș face-o este să folosesc algoritmul simplu mort care începe la etajul 1, care cade marmura la un etaj la un moment dat până când ajunge la 100 sau la pauzele de marmură.

Apoi, aș întreba de ce ar trebui să-mi petrec timpul optimizând până când somone poate arăta că va fi o problemă. De prea multe ori, oamenii se conectează la găsirea algoritmului perfect complicat atunci când o soluție mult mai simplă va rezolva problema. Cu alte cuvinte, nu optimizați lucrurile până nu este nevoie.

Acest lucru ar putea fi o întrebare truc pentru a vedea dacă sunteți unul dintre acei oameni care pot face un munte dintr-un deal molare.

0
adăugat
Chiar dacă doriți să utilizați un algoritm mort simplu, cel puțin să utilizați toate informațiile din întrebare. Aveți 2 marmură, dar încă mai folosiți doar 1. Nu lăsa cealaltă marmură să stea și să plângă "Am venit în această lume pentru a face o diferență și îmi pierzi existența: ("
adăugat autor Vikram Singh, sursa

The interesting thing here is how you can do it in the least amount of drops possible. Going to the 50th floor and dropping the first would be disastrous if the breaking floor is the 49th, resulting in us having to do 50 drops. We should drop the first marble at floor n, where n is the max amount of drops required. If the marble breaks at floor n, we may have to make n-1 drops after that. If the marble doesn't break we go up to floor 2n-1 and if it breaks here we have to drop the second marble n-2 times in the worst case. We continue like this up to the 100th floor and try to break it at 3n-2, 4n-3....
and n+(n-1)+(n-2)+...1 <=100
n=14 Is the maximum drops required

0
adăugat
puteți explica motivul pentru ecuația n + (n-1) + (n-2) + ... 1 <= 100 ?
adăugat autor Geek, sursa
@Geek spune n este cel mai rău rezultat permis. Deci, încercați să faceți cea mai gravă situație cea mai gravă pentru fiecare din mai multe segmente. Pentru a menține cel mai rău caz maxim pentru fiecare segment testat, trebuie să utilizați 1 picătură mai mică pentru fiecare segment testat. Testați primul segment la acea valoare a lui n, în cazul în care vă rupe apoi testul de la 1 până la n-1. Deci, picăturile maxime finale sunt 1 + (n-1) = n. Dacă nu s-a rupt la n, dar la 2n, atunci ați făcut deja o picătură la n, deci pentru a rămâne la cel mai rău caz de n picături, ați rămas doar n-1. La
adăugat autor Davos, sursa
În mod logic, marmura atinge mai mult teren, cu atât creșteți mai sus, astfel încât să începeți să vă deplasați și să vă deplasați. Deci segmentele încep să scadă și se ridică și ele. Cele mai multe segmente pe care le testați, cu cât mai puține picături rămân, astfel încât segmentele superioare sunt forțate să fie mai mici și mai mici. Segmentul de jos este cel mai mare, egal cu n. Fiecare pas în sus este unul mai puțin, pentru că vă lucrați în sus.
adăugat autor Davos, sursa
Scopul este de a minimiza n. Puteți parcurge acest lucru manual, urmărind rezultatele fiecăruia dintre acestea: n = 100 , n + (n-1) = 100 ) + (n-2) = 100 , n + (n-1) + (n-2) la n = 100 , n = 101/2 . Continuă, valoarea lui n va deveni mai mică, până când va ajunge la un nivel minim, iar apoi va merge mai mare după aceea. Această soluție minimă este optimă. Soluția este de 13.64, dar nu există niciun etaj 13.64, deci 14. Numărul de segmente necesare este același cu numărul de termeni pentru a găsi minimul, de ex. n +
adăugat autor Davos, sursa
Nu pot edita primul comentariu. Această parte este greșită: "dacă nu sa rupt la n, dar la 2n". Ne pare rău 2n nu este corect, ar trebui să fie "dar la n + (n-1)"
adăugat autor Davos, sursa

Cred că întrebarea reală este cât de precis doriți răspunsul. Pentru că eficiența ta va depinde într-adevăr de asta.

Am de gând să fie de acord cu Justin, dacă doriți precizie de 100% pe plăcile de marmură, apoi o dată prima marmura rupe dvs. de gând să trebuie să meargă până la 1 etaj la un moment dat de la ultimul etaj cunoscut „bun“ până când afla ce etaj este câștigătorul." Poate arunca chiar și în unele statistici și să înceapă de la etajul 25 în loc de la etajul 50, astfel încât tu ești cel mai rău scenariu caz, ar fi de 24 în loc de 49.

Dacă vă răspundeți poate fi plus sau minus un etaj sau două, atunci ar putea exista unele optimizări.

În al doilea rând, mersul pe jos / în jos pe scări conta împotriva eficienței dumneavoastră? În acest caz, aruncați întotdeauna ambele marmură și ridicați ambele marmură în fiecare călătorie sus / jos.

0
adăugat

Acest lucru se poate face mai bine cu doar 7 marmură.

Deci, urmând răspunsul votat, spuneți că pardoseala de marmură se află la cel puțin etajul 49.

  1. 50th floor -> breaks (answer is between 1 to 50 inclusive)
  2. 25th floor -> doesn't break (26 to 50)
  3. 37th floor -> doesn't break (38 to 50)
  4. 43rd floor -> doesn't break (44 to 50)
  5. 46th floor -> doesn't break (47 to 50)
  6. 48th floor -> doesn't break (49 or 50)
  7. 49th floor -> breaks (49th, this step is actually needed because it might have been the min floor for marble to break is at 50th)

Acest lucru poate fi imaginat ca făcând o căutare binară într-un set sortat pentru unele k, unde am jumătate din spațiul soluției cu fiecare încercare. Pentru 100 etaje, avem nevoie de log2 100 = 6.644 (7 încercări). Cu 7 marmură putem fi siguri care este etajul minim pe care marmura îl va rupe până la 128 de etaje.

0
adăugat
Asta ar fi o problemă foarte diferită.
adăugat autor borjab, sursa
Problema cu răspunsul dvs. este că NU va garanta că dacă oul se va rupe de la etajul 43, atunci nu veți ști dacă pragul de prag a fost 38, 39 ... 42. De asemenea, vedeți acest lucru
adăugat autor ABcDexter, sursa