Nenad Božidarević
Matematika

Parsiranje Bulovih izraza

Da, veoma dugo nisam pisao, ali me ovaj zadatak kopka već neko vreme, tako da sam najzad seo i bacio se na njegovo rešavanje.

U svom sada već skoro četiri godine starom tekstu Utisci sa testa za praksu u Microsoftu naveo sam zadatke sa kojima sam se tada susreo, ali nisam zalazio u to kako se oni rešavaju. Međutim, za ovo je očigledno bilo zainteresovanih ljudi, pa je jedan komentar na tekst bio pitanje kako se rešava zadatak sa parsiranjem Bulovog izraza. Prisetimo se kako je on glasio:

Dat je pravilno formiran logički izraz koji se sastoji od karaktera T, F, &, |, !, (, ) i razmaka. Potrebno je odrediti njegovu vrednost u linearnom vremenu. Pritom je & (AND) većeg prioriteta od | (OR).

Nažalost, na sâmom testu ovaj zadatak nisam uspeo da rešim sa zadatom (linearnom) složenošću, a nakon toga mu se nisam vraćao. Sada sam, međutim, došao u situaciju gde se već neko vreme nisam bavio algoritmima, i ovo je bila savršena prilika da se podsetim nekih najosnovnijih stvari, uključujući i C++a (jer na poslu radim frontend u PHPu i Javascriptu). Dakle, bacimo se na posao.

Pročitaj ostatak teksta

Zadaci sa Google intervjua za praksu

Iako sam u svojim tekstovima obrađivao razne teme, primetio sam da su ljudima uglavnom najkorisniji tekstovi u kojima sam opisivao zadatke sa testova i intervjua, što mi je veoma drago. Iz tog razloga ovu tradiciju nastavljam, prelazeći na sledeću veliku IT kompaniju – Google.

Google predstavlja svojevrsni Sveti Gral za mnoge programere, pa sam i ja odlučio da okušam svoju sreću sa njihovim procesom zapošljavanja. Međutim, sâm intervju se odigrao u relativno lošem trenutku – prijavu sam obavio još pre završetka prakse u Facebooku, ali mi je razgovor zakazan tek nakon što sam prihvatio ponudu da se tamo i vratim. Samim tim, intervjuu za Google nisam pristupio dovoljno ozbiljno, pa me je baratanje grafovima (treći zadatak) na kraju dotuklo. Svejedno, mislim da su ova dva intervjua bila dobra kako iz istraživačkog, tako i iz poznavanje-svojih-slabosti ugla.

Slede tri zadatka i njihova rešenja, kao rezultat tog “istraživanja”.

Pročitaj ostatak teksta

Splitwise – aplikacija za deljenje troškova

Dok sam bio u Kaliforniji, došao sam u dodir sa jednom aplikacijom koja me je oduševila svojom kombinacijom jednostavnosti i praktičnosti – u pitanju je Splitwise, aplikacija za deljenje grupnih troškova. Iako je ideja daleko od revolucionarne, ovaj servis se probio i dobro pozicionirao kako na mobilnim platformama (postoje Android i iOS aplikacije), tako i na webu, ali do nas iz nekog razloga nikada nije došao. Zbog toga sam počeo uporno da dosađujem ljudima da ga koriste, jer znatno olakšava bilo kakva putovanja ili grupne finansijske konstrukcije, pa ovim tekstom pokušavam da doprem i do šire javnosti. This message has been brought to you by the Splitwise Advertising Department.

Pročitaj ostatak teksta

Generisanje nasumičnih brojeva

Kao posledica bavljenja svojim diplomskim radom, došao sam do dela gde su mi bili potrebni nasumični brojevi (tema je određena primena genetskih algoritama, više o tome drugi put), pa sam odlučio malo ozbiljnije da ispitam razne mogućnosti za njihovo generisanje. Ispostavilo se da je u pitanju jedna veoma zanimljiva tema, čak i daleko opširnija nego što bi neko rekao na prvi pogled. Naravno, ono što je čini toliko zanimljivom jeste upravo njen naziv koji lako ume da nas zavara — nisu u pitanju nasumični brojevi, već “nasumični” (pseudonasumični) brojevi. O čemu se ovde zapravo radi?

Stvar je veoma jednostavna: nasumičnost ne postoji, a posebno ne u računarima. Čoveka možete priupitati da vam kaže proizvoljan broj, ali verovatnoća da taj čovek (ili žena) kao iz topa kaže devetmilionadvestapedesetišesthiljadatridesetisedam je daleko manja od verovatnoće da vam jednostavno kaže “osam”. Ukoliko se pogleda iz tog ugla, računari su zapravo mnogo bolji generatori nasumičnih brojeva, ali i dalje nisu savršeni.

Problem leži u tome što je u računarima sve determinističko, pa algoritam do nasumičnog broja mora da dođe na određen način koji je sve samo ne nasumičan. Jedan od jednostavnijih metoda je generisanje sekvence brojeva na sledeći način:

X_{n+1} = (aX_n + b)\ mod\ m

Očigledno, svaki od brojeva će biti iz intervala [0, m), gde će nasumičnost sekvence zavisiti od početne vrednosti koja se naziva seed (iliti seme), a neka vrednost će se u najboljem slučaju ponoviti nakon m generisanja (na osnovu trpanja golubova u rupe). Da bismo ovaj proces učinili “kvalitetnijim”, za seed se često koristi trenutno vreme (odnosno UNIX timestamp), pa drugo pokretanje programa nakon samo jedne sekunde može dati potpuno drugačije vrednosti. Mana ovog konkretnog pristupa je što se nakon prvog ponavljanja neke vrednosti cela sekvenca ponavlja; neki drugi pristupi nakon prvog ponavljanja vrednosti ipak daju drugačiju sekvencu, odnosno imaju mnogo veću periodu, jer i drugi parametri utiču na generisanje vrednosti. Složićete se, ipak, da ovakvo generisanje zapravo nije uopšte nasumično, ali je za potrebne mnogih i više nego dovoljno, dok za potrebe ostalih C++ nudi random_device generator koji se oslanja na adekvatan hardver, ukoliko je isti dostupan. Međutim, čak i ako imate dobar generator, to vas neće sprečiti da ga upropastite ukoliko ga uzmete zdravo za gotovo. Demonstrirajmo to na tri jednostavna primera.

Pročitaj ostatak teksta

Zadaci sa Facebook intervjua

Ukoliko želite da saznate kako izgleda sâm proces prijavljivanja za praksu, strpite se, pošto će tekst o tome uslediti kasnije. pratite ovaj link.

Kao što sam pre nekoliko meseci pisao o zadacima sa intervjua za praksu u MDCS-u (Microsoft Development Center Serbia), tako ću sada sa vama podeliti i zadatke sa intervjua za praksu u Facebook-u. Iako bi se možda moglo očekivati da zadaci budu teški, s obzirom da pričamo o veoma jakoj kompaniji, primetićete da su slični onima za MDCS koji je ipak samo regionalni centar.

Koliko sam uspeo da primetim, za software engineer pozicije u većini kompanija uglavnom zadaci i jesu ovog tipa, pa verujem da će tekst koristiti svima koji razmišljaju o prijavljivanju za takav posao.

Zadatke sam podelio u dve kategorije — programerske i matematičke. Međutim, nemojte da vas to zavara, pošto je sve trebalo isprogramirati – za druge je samo bilo potrebno i određeno znanje matematike. Sva rešenja su napisana u C++u.

Pročitaj ostatak teksta

Rešavanje rekurentnih jednačina

Nakon nešto duže pauze uglavnom prouzrokovane ispitnim rokom, vraćamo se programiranju i matematici…

Rekurentne formule predstavljaju poseban oblik zapisivanja vrednosti nekog niza. Jedna od najpoznatijih ovakvih relacija je svakako Fibonačijev niz, u kome vrednost nekog člana niza zavisi od vrednosti prethodna dva.

F_n = F_{n-1} + F_{n-2}, ~ F_0 = 0, ~ F_1 = 1

Ukoliko u programu želimo da izračunamo neki član ovog (ili bilo kog drugog) niza, potrebno je da krenemo od vrednosti koje su nam date i iterativno dođemo do željenog člana, pritom prolazeći kroz sve njegove prethodnike. Naravno, moguće je i rešavanje relacije tako da formula zavisi samo od datih vrednosti i N, ali to bi bilo previše komplikovano za implementaciju.

Iako je ovaj pristup krajnje jednostavan, u nekim slučajevima nije moguće primeniti ga usled problema sa efikasnošću. Linearne homogene rekurentne formule, koje ću obraditi u ovom tekstu, mogu biti vremenski zahtevne ukoliko se traži član se velikim indeksom. Ukoliko svaki član zavisi od 10 prethodnih, a njegov indeks je 100.000.000, ukupno će biti potrebno milijardu sabiranja, što je apsolutno nepotrebno. Postoji i komplikovaniji, ali daleko brži pristup.

Pročitaj ostatak teksta

Utisci sa intervjua za praksu u Microsoftu

Ukoliko bacite pogled na prošli tekst koji sam ovde objavio, primetićete da se bavi testom za praksu u Microsoftu, odnosno u Microsoft Development Center Serbia. Dve nedelje nakon objavljivanja tog teksta, odnosno održavanja testa, pozvan sam na intervju kao jedan od N kandidata; vrednost broja N je, naravno, nepoznata.

Kao što je bio slučaj i kod testa, konkretne informacije je veoma teško naći na Internetu, pa bi bilo i više nego prikladno da ja sa vama podelim šta vas čeka na intervjuu, ako neke od sledećih godina odlučite da se prijavite za praksu.

Here be dragons…

Pročitaj ostatak teksta

Utisci sa testa za praksu u Microsoftu

Pre oko dva meseca pisao sam o konkursu koji je Microsoft Development Center Serbia raspisao radi dovođenja novih ljudi u razvojni tim. Otvoreno je deset mesta za zapošljenje i deset mesta za praksu, give or take — više nego prošlih godina.

Kako sam bio zainteresovan za praksu, počeo sam da se raspitujem kod nekolicine ljudi koji su ranije konkurisali, a neki i prošli, kako izgleda ceo taj proces i kakva se znanja traže. Oni su bili od velike pomoći, te im se ovom prilikom zahvaljujem. Međutim, informacije na sâmom Internetu je nešto teže naći, iako bi ovo trebalo da je doba informacija. Čovek bi pomislio da je za ovo zaslužan neki non-disclosure agreement, ali on se sve do samog zapošljenja ni ne pojavljuje. Zbog toga sam odlučio da napišem svojevrsni rezime onoga sa čime sam se ja (do sada) susreo tokom ovog procesa, i budalasto pomognem konkurenciji. (Za one koje zanimaju samo zadaci — na dnu strane su)

Pročitaj ostatak teksta

Računanje broja Pi Monte Karlo metodom

Pre nekoliko dana na predavanju iz Verovatnoće i statistike dotakli smo jednu zanimljivu temu – problem Bifonove igle (Buffon’s needle).

U ravni je dat skup paralelnih pravih, pri čemu je rastojanje između susednih pravih a, a > 0. Na ravan se baca igla dužine l, l < a. Odrediti verovatnoću da igla seče neku od pravih. ("Verovatnoća i statistika za inženjere i studente tehnike", Milan Merkle)

Bacanje igle kod Bifonovog problemaU pitanju je običan zadatak iz verovatnoće, ali ono što ga čini posebno zanimljivim jeste činjenica da se na osnovu baš ovakvog bacanja igle može odrediti broj π. Naime, zbog različitih uglova pod kojima igla može da se nađe u odnosu na pravu (kao na slici), u formuli za verovatnoću figuriše broj π. Ako znamo njegovu vrednost, možemo odrediti verovatnoću — ali ako je ne znamo, možemo baciti iglu veliki broj puta da bismo dobili verovatnoću, a onda preko nje izračunati π.

Naravno, jasno je da “veliki broj bacanja” uopšte nije lako izvesti. Ako želimo iole preciznije rezultate, nekoliko hiljada teško da će biti dovoljno, pa se mora stremiti ka daleko većim brojevima. Italijanski matematičar Mario Lazzarini je početkom 20. veka izveo ovaj eksperiment sa 3408 bacanja i dobio vrednost 355/113, što je 3.14159292. Za poređenje, vrednost broja π je 3.14159265, odnosno razlikuju se tek na sedmoj decimali. Članak na Wikipedii objašanjava zašto je dobijena ovako precizna vrednost sa malim brojem bacanja, ali nas to trenutno interesuje. Zanemarićemo njegove rezultate, i pokušati lično da izračunamo π uz pomoć kompjuterske simulacije koja nam omogućava da izvršimo milione “bacanja” u samo jednoj sekundi.

Pročitaj ostatak teksta