Jednom sam se javio na konkurs firme Omni Explorer. Jedan od zadataka je bio
Napisati C++ klasu za skladištenje stringova, koja ima samo dve metode: insert i exists tako da
1. Bude što efikasnija. Pretpostaviti da je tipična veličina stringa 40 bajtova.
2. Da bude sposobna da primi do 200,000,000 stringova.
3. Na raspolaganju je tačno 2GB memorije. Ne sme da koristi ni bajt više.
4. Ne sme da koristi nikakav vid kompresije.
Test mi je stigao elektronskom poštom, tako da su mogli umesto mene da ga rade i Pera i Mika i Žika, što ne bi trebalo da bude moj problem. Moje rešenje je bilo sledeće.
Ako treba da smestim, bez kompresije 200,000,000 stringova u 2GB, onda svakako ne smem da trošim više od 85 bitova po stringu, uključujući i organizaciju. Dakle, do 10 bajtova po stringu. Samim tim, budući da kompresija nije dozvoljena, tipična dužina od 40 bajtova se može odnositi samo na zahtev 1 (efikasnost), a ne i na tačku 2. Znači, moja klasa mora biti optimizovana za rad sa stringovima dužine 40 bajtova, ali sposobna da primi bar 200,000,000 različitih stringova (kakve god dužine) u 2GB. Stringova dužine <=3 bajta nema ni blizu 200,000,000, ali zato stringova dužine 4 bajta ima više od 200,000,000.
No, potrebno je na neki način rešiti i problem identifikacije kraja stringa. Pošto string može imati proizvoljnu dužinu (40 bajtova je samo tipična dužine, ali nema nikakvog ograničenja), odabrao sam C-ovski pristup sa završnim nula bajtom. Znači, treba da bar 200,000,000 stringova sa 4 bajta mesa i još jednim bajtom za identifikaciju kraja strpam u 2GB. OK, takvi goli stringovi bez organizacije zauzimaju 40 bitova po stringu.
Ukoliko upotrebim bilo koju vrstu binarnog drveta, trebaće mi još 8 bajtova za levi i desni pokazivač po čvoru, a pošto takvo stablo pamti samo po jedan string u čvoru, već smo probili budžet od 8 bajtova. Pretraga svakako treba da bude binarna ili nešto nalik na nju, tako da mi od stuktura ostaju B-stabla, koja imaju minimalni stepen grananja veći od 2.
Ako je stepen grananja nekog čvora jednak n+1, odnosno on pamti n stringova, biće mi potrebno za taj čvor 40n+32(n+1)=72n+32 bitova. Osim toga, trebaće mi m bitova za pamćenje stepena grananja. Ako je maksimalan stepen grananja jednak 2n+1, imam n+1 mogućnosti za stepen grananja (od n+1 do 2n+1), pa mora biti 2
m>=n+1. Uz to, čvor me "košta" m+32+72n bitova, a pošto čvor pamti n stringova, budžet za taj čvor mi iznosi 80n bitova. Dakle, mora biti m+32+72n<=80n, tj. 8n>=32+m. Za n=5 i m=3 su zadovoljene obe nejednakosti. Ukoliko neki čvor ima veći stepen grananja od minimalnog, odnos broja potrošenih bitova i broja stringova koje pamti biće još povoljniji.
Pošto imam samo zauzimanje, a ne i oslobađanje (klasa ima samo insert i exists metode, a ne i remove), mogu da imam sopstveni alokator memorije koji samo zauzima memoriju prema vrhu bafera, da ne bih trošio memoriju i na organizaciju toga.
Napisao sam program koji ispravno radi i za mesec dana, kada sam pitao šta je bilo sa konkursom, rekli su mi da "Nisu zadovoljni mojim odgovorom i da će, možda, razmotriti moju prijavu ako budu snižavali kriterijume".
Dobro de, bilo je još zadataka. Valjda me nisu primili, pa čak ni pozvali na intervju, zato što nisam naveo dovoljan broj sličnosti između podmornice i crne rupe, što je takođe bilo jedno od pitanja.
O "ozbiljnosti" testa govori i zadatak "Napisati funkciju koja za datu matricu tačaka kodovima boja i funkciju koja određuje da li je boja datog koda moguća boja neba sa 100% pouzdanosti utvrđuje da li se na toj slici vidi nebo.". Da li u svetu postoji 100% pouzdan program za to?
Sve u svemu niako nisam imao sreće kod tih firmi koje "traže" (sudeći po tekstu konkursa) "suštinu i razmišljanje", a bilo ih je još.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Re: Legalizacija - jeste li razmišljali?