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…

Nakon što vam neko iz MDCS javi da ste pozvani na intervju, stići će vam e-mail sa bitnim informacijama, i jednim savetom:

When interviewing, it is important to feel comfortable. Microsoft prizes intelligence and contribution over style. The people that you interview with will probably be dressed a lot like the people on your college campus.

Ne znam da li e-mail iste sadržine šalju i onima koji konkurišu za posao, ali verujem da to jeste slučaj — od programera se ionako ne očekuje da svaki dan na posao dolaze u odelu (posebno ne po ovim vrućinama). Dakle, možete da očekujete da intervju bude krajnje opušten i ležeran.

Samo trenutak. Da li sam rekao “intervju”? Hteo sam reći intervjui. Dakle, nije u pitanju jedan intervju, već četiri komada kod četiri različita zaposlena u MDCS, svaki od po oko sat vremena, odnosno četiri sata ukupno. Ova brojka možda izgleda zastrašujuće, ali baš zbog gore pomenute opuštene atmosfere ovaj vremenski period veoma brzo prođe, i ni ne izmori čoveka toliko. Intervjui se međusobno ni ne razlikuju previše: sastoje se od nekoliko minuta razgovora o stavkama CVa, uz povremeno skretanje sa teme, i rađenja jednog zadatka ostalih 40-50 minuta. U svakom slučaju se ne mogu smatrati “tipčnim intervjuima”. Naravno, sva komunikacija se obavlja na engleskom.

Pitanja iz prvog dela intervjua nema smisla prenositi, pošto se razlikuju od osobe do osobe, pa ću odmah preći na zadatke. Kao što ćete verovatno primetiti, oni uopšte nisu teški, i brzo se rešavaju. Zašto onda taj deo intervjua traje preko pola sata? Zato što se kreće od najosnovnije verzije zadatka, ali se nakon toga dodaju zahtevi, menjaju početni uslovi, zalazi u detalje itd. Takođe, uglavnom se od vas traži i da napišete 100% tačan kôd u jeziku po izboru. Pretpostavljam da im je ovde najbitnije da vide vaš tok misli i kako se prilagođavate sve kompleksnijim i kompleksnijim problemima. Evo šta je mene dočekalo:

1. Dat je niz od N stringova jednake dužine L. Potrebno je proveriti da li zadati string postoji u tom nizu. Na koje načine se ovo sve može obaviti? Koje su prekalkulacije potrebne? Koje su složenosti svakog od pristupa? Koji je najbolji? Osmisliti test primere za koje su ovi algoritmi najsporiji. Ono što sam ja uspeo da pređem za zadato vreme jeste:
   • Binarna pretraga uz prethodno sortiranje niza
   • Optimizovana binarna pretraga uz preskakanje karaktera na početku stringa koje ne moramo da proveravamo
   • Pretraga upotrebom heširanja
   • Upotreba trie-a
2. Na drugom intervjuu su me sačekala dva pitanja, a prvo je bilo pomalo neočekivano:
   1. Potrebno je osmisliti chat sistem za veliku kompaniju sa puno zaposlenih. Kako bi on bio organizovan? Šta bi se nalazilo sa serverske, a šta sa klijentske strane?
   2. Data je sortirana skip lista. Potrebno je proveriti da li sadrži zadati element. Nakon što sam se izborio sa ovim zadatkom, usledilo je još jedno dodatno pitanje: koje još strukture imaju 2n pokazivača (što je slučaj kod skip liste)? Naravno, u pitanju su dvostruko povezana lista i binarno stablo.
3. Za razliku od prethodna dva intervjua, treći se pomalo bavio i matematikom, i sastojao se od tri zadatka.
   1. Dato je K sortiranih nizova različitih dužina sa ukupno N elemenata. Potrebno je formirati jedan sortirani niz dužine N koji bi sadržao sve elemente. Trivijalno rešenje je prolaz kroz početke svih nizova za svaki element (složenost Θ(n*k)), dok se brži algoritam dobija upotrebom heap-a, gde je složenost Θ(n*logk).
   2. Data su dva realna intervala. Iz oba intervala se bira po jedan nasumičan broj, sa uniformnom raspodelom. Potrebno je odabrati jedan od ova dva intervala tako da je veći od ona dva nasumična broja češće baš iz tog intervala. Tačnije, potrebno je odrediti interval za koji je veća verovatnoća da je veći od dva broja generisan iz tog intervala. Konfuzno, znam. Postoje dva pristupa za rešavanje ovog problema. Prvi je da se ispišu verovatnoće za svaki od tri slučaja preklapanja intervala (nema preklapanja, delimično preklapanje, potpuno preklapanje), pa da se u kôdu na osnovu toga bira interval. Međutim, postoji daleko jednostavnije rešenje, a to je da se bira interval čija sredina ima veću vrednost — iako nije očigledno, grafičkim prikazom verovatnoće (jedan interval na X-osi, a drugi na Y-osi) se ovo lako dokazuje.
   3. U komunikaciji sa serverom klijent dobija neki niz objekata nepoznate dužine. Jedina metoda dostupna klijentu jeste dobavljanje sledećeg objekta, koja vraća null u slučaju dolaska do kraja niza. Nakon što se dođe do kraja niza, potrebno je da klijent nasumično vrati jedan od primljenih objekata, sa uniformnom raspodelom. Ne postoje resursi za čuvanje svih objekata. Rešenje se zasniva na tome da se u svakom trenutku čuva samo jedan objekat, koji se sa određenom verovatnoćom zamenjuje sledećim objektom. U ovom slučaju, ta verovatnoća je 1/brojPrimljenihObjekata.
4. Poslednji intervju je opet bio “čisto programerski”, sa dva pitanja.
   1. Dato je binarno stablo i dva pokazivača na elemente iz tog stabla. Potrebno je odrediti njihovog prvog zajedničkog pretka. Kako bi izgledao algoritam ako čvor osim pokazivača na svoju decu ima i pokazivač na roditelja?
   2. Dato je binarno stablo. Svaki čvor osim pokazivača na decu ima i pokazivač na sledeći čvor u tom nivou (prvi desno od njega), koji nije inicijalizovan. Potrebno je inicijalizovati ove pokazivače za sve čvorove. Problem se rešava in-order prolaskom kroz stablo i pamćenjem poslednjeg čvora koji smo obišli za svaki od nivoa.

Sve u svemu, intervju na kraju i nije bio toliko teži od testa. Nekima će možda razgovor u četiri oka predstavljati problem, i izazvati pad koncentracije, ali ja intervju ipak vidim kao prednost — poslodavac može da čuje kako razmišljate, a i uvek možete da ostavite utisak da nešto znate iako to nije slučaj. Samo treba da budete dovoljno dobri sa rečima.