Nenad Božidarević
Programiranje

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

Setting up a “Pay What You Want” download with PayPal

Almost seven years ago, in 2007, Radiohead decided to give away their new album, “In Rainbows”, for free – well, sort of. It wasn’t free per se, but they did give the fans the choice to pay what they wanted, and that’s how the “Pay What You Want” pricing strategy came to prominence. But why am I mentioning this?

If you are a developer of any kind, or even an artist, it has probably occurred to you that you could sell something online. Unfortunately, this is easier said than done, since there usually exist only two major options:

  1. Register at a web site that specialises in selling such products (e.g. ThemeForest, if you are creating web templates). The problem with this is that there is a high quality bar that needs to be met if you want to actually sell anything, and even in that case the fees are hefty, so you end up getting only a percentage of the price.
  2. Create your own web site and use an e-commerce system to sell the product. Such systems aren’t cheap, and you still end up having to promote your content in order to attract visitors. Writing your own code for integration with PayPal is also a challenge, because of all the security that you would need to put in place.

Obviously, for someone who would just like to earn a bit on the side, neither of these are a viable option. However, if you are ready to compromise and give your stuff away for free, you can actually earn money by using the “Pay What You Want” system. The logic is simple – if you are willing to put your product up for download, why not give the users the option to pay for it? Surprisingly enough, unlike a “Donate Now” button which nobody clicks, this approach leads to a lot of people paying something, which in the end amounts to a considerable profit.

Pročitaj ostatak teksta

Nordeus Hackathon 2013

Otkako sam prvi put iskusio hakaton, u okviru prošlogodišnje Start konferencije, postao sam veliki zagovornik ovakvog tipa takmičenja (odnosno događaja – Facebook hakatoni, na primer, nisu takmičarskog tipa). Verovatno glavni razlog za to je što tokom dvadeset i četiri sata radite na nekom proizvodu, od nule pa do razvoja funkcionalnog prototipa, i samim tim tokom ovog perioda možete da se susretnete sa najraznovrsnijim izazovima.

Algoritamska takmičenja, s druge strane, su prilično “predvidiva” – uglavnom se zna koje oblasti dolaze, kao i kakvi tipovi zadataka, pa je pripreme lako isplanirati (doduše, nije lako spremiti se). Naravno, ona su i dalje najbolja priprema za intervjue u velikim softverskim kompanijama, ali ipak treba obratiti pažnju i na hakatone, jer pružaju drugačiji skup iskustava koja su značajna kada taj intervju prođete i zapravo dobijete posao.

Ukoliko ste zaintrigirani, sada je pravi trenutak da se upustite u ovu avanturu, jer Nordeus u decembru, već treću godinu za redom, organizuje hakaton u razvoju igara. Ukoliko niste, čitajte dalje…

Pročitaj ostatak teksta

Facebook, eh?

Noćas opet snijeg. Opet prošla grtalica i zatrpala kapiju. Ovdje je prekrasno.

Ukoliko vam citat iznad ne zvuči poznato, to znači da niste čitali takozvani “Dnevnik jednog Bosanca”, priču o Balkancu koji odlučuje da napusti domovinu i okuša svoju sreću u predivnoj Kanadi.

Igrom slučaja, ja sam se našao upravo u takvoj situaciji… Setićete se, krajem prošle godine sam objavio tekst Facebook – tamo i nazad: III deo u kojem sam pisao o svojoj praksi u Facebooku iz koje je izrodila ponuda za posao, a samim tim i plan za preseljenje u Kaliforniju. Iako je čitav administrativni proces odmah počeo, godinu dana pre nego što je trebalo da odem, stvari ipak nisu u potpunosti išle svojim tokom – svu dokumentaciju sam slao na vreme i diplomirao u najkraćem mogućem roku, ali američka radna viza je čudna rabota.

Long story short, američku vizu nisam dobio, ali zato kanadsku jesam, i evo me sad u Vankuveru. Ukoliko vas zanima šta se to sve izdešavalo između, odnosno kako izgleda jurnjava za radnom dozvolom u SAD i Kanadi, te informacije će uslediti u nekom od sledećih tekstova. Ovaj je, pak, najviše posvećen samoj Kanadi.

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

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

Tekst u Ilustrovanoj Politici povodom takmičenja AI Olympics

Četvorica studenata Računarskog fakulteta iz Beograda osvojila su prva tri mesta na nedavno održanoj olimpijadi u razvoju veštačke inteligencije u Bukureštu svojim originalnim programima testiranim u jednoj strateškoj igri.

Ovako je započet tekst objavljen u prošlonedeljnoj Ilustrovanoj Politici. Kako oni, nažalost, nemaju online arhivu tekstova, odlučio sam se da ga okačim, kako biste mogli da pročitate ovu priču ispričanu od strane nekoga ko nije programer, već zaista novinar.

Autor teksta je Jelena Bošković, a fotoreporter Vladimir Marković.

Pročitaj ostatak teksta

Od srednje škole do Silicijumske doline

Juče sam na Računarskom fakultetu, u okviru seminara RAF IT Days, održao predavanje pod nazivom “Od srednje škole do Silicijumske doline”, i veoma mi je drago da se to desilo, pošto je u pitanju tema o kojoj želim da pišem već neko vreme. Tačnije, želim to da uradim preko godinu dana, još otkad je izašao tekst “From college to Silicon Valley”, ali sam to stalno odlagao zbog obilja informacija koje bih u takav tekst mogao da uključim.

U okviru Start konferencije sam takođe držao slično predavanje, ali pod nazivom “Od fakulteta do Silicijumske doline”, i ono je bilo svojevrsan podskup ovog teksta — ipak, složićete se da nije imalo smisla da studentima pričam o tome šta treba raditi tokom srednje škole. Zbog toga je ovo predavanje na RAFu bila odlična prilika da te informacije i savete skupim i organizujem, i najzad prezentujem u ovom tekstu.

Pročitaj ostatak teksta

AI Olympics – dođosmo, videsmo, pobedismo

AI Winter OlympicsZahvaljujući entuzijastičnim i mladim studentima, na Računarskom fakultetu je početkom ove školske godine osnovana sekcija pod nazivom “Competitive programming”, a sa ciljem da studentima dodatno približi baš ona takmičenja u kojima su RAFovci najbolji — algoritamska takmičenja. Slučajno ili ne, sa nastankom ove sekcije se poklopila i povećana zainteresovanost mojih kolega i mene za razna takmičenja, pa smo tako učestvovali na dva hackathona (Start Conference i Nordeus Hackathon), gde smo i pokupili većinu nagrada.

Ova dva zbivanja kao da se nisu mogla dogoditi u boljem trenutku, jer je baš tokom decembra objavljeno da će se ove godine, nakon jedne preskočene, ponovo održati takmičenje AI Olympics, o kojem sam nakon učešća 2011. godine i pisao. Podstaknuti pređašnjim uspesima, sa velikim brojem zainteresovanih ljudi, doneli smo odluku…

RAF ide u Rumuniju da pobedi.

Pročitaj ostatak teksta

Start Conference i razvoj Metro aplikacija

Kao fotograf, osećam dužnost da prvo pomenem Vukašina Jeremića koji je bio fotograf na ovom događaju, i čije sam fotografije upotrebio u tekstu.

Start Conference, događaj koji je prethodnih nekoliko nedelja grandiozno najavljivan, najzad je održan ovog vikenda na Fakultetu organizacionih nauka. Za neupućene, konferencija se zapravo sastojala iz tri dela — radionica, sâme konferencije (predavanja) i takmičenja — i verujem da su sve njene komponente zadovoljile očekivanja organizatora i učesnika, pritom opravdavši gore pomenuto grandiozno najavljivanje. S obzirom da je konferencija organizovana po prvi put, i da je trajala (bukvalno) dva dana bez prestanka, za organizatore koji su verovatno spavali i manje od takmičara imam samo reči hvale.

Kao što sam već napomenuo u prethodnom tekstu, studenti iz organizacije FONIS, koji su idejni tvorci i organizatori ovog događaja, i koje poznajem već neko vreme zahvaljujući događijama “Blogeri studentima” i “Kompanije studentima”, su me pozvali da održim predavanje/prezentaciju o svojoj praksi u Facebooku i iskustvima sa praksama uopšte. Ovo je došlo kao veoma zgodna tema, pošto već nekoliko meseci planiram da napišem tekst pod nazivom “Od srednje škole do Silicijumske doline” — u ovom slučaju sam doduše pričao na temu “Od fakulteta do Silicijumske doline”, pošto zaista nije bilo smisla da govorim ljudima šta je trebalo da rade u srednjoj školi :) Dakle, svojevrsni transkript predavanja će usledeti kada se zaista nakanim da napišem taj tekst.

Drugi deo konferencije u kojem sam odlučio da uzmem učešće, i koji je glavni razlog za pisanje ovog teksta, jeste takmičenje u razvoju Windows 8 Metro aplikacija. Sa dvojicom kolega sa fakulteta napravio sam tim koji ranije nije imao nikakvog iskustva u razvoju Windows 8 aplikacija, ali smo zato imali raznovrsno iskustvo za koje smo mislili da će nam biti dovoljno.

Ispostavilo se da to i jeste bio slučaj. Iako smo dosta vremena proveli pokušavajući da razumemo razne aspekte Windows 8 Metro aplikacija, tokom druge polovine takmičenja smo se zahuktali, i napravili aplikaciju kojom smo bili (tj. i dalje jesmo) veoma zadovoljni. Obraćajući pažnju na stvari koje se boduju, ispunili smo većinu uslova, i tako smo u konkurenciji od 8 timova osvojili drugo mesto. Borba za top 3 je bila veoma tesna (195, 198 i 205 poena), ali je prva nagrada u svakom slučaju otišla u dobre ruke — Lenovo tablet su osvojili naši dobri prijatelji Vladimir Dimić, Vlado Pajić (administrator sajta dubstep.rs koji su i inkorporirali u svoju aplikaciju) i Boris Perović.

Da bih ispoštovao prvenstveno tehničku prirodu ovog bloga, ostatak teksta ću posvetiti razvoju Metro aplikacija i našim iskustvima koja smo stekli tokom dvadeset i četiri sata, koliko je trajalo takmičenje.

Pročitaj ostatak teksta