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)
Prvi korak, nakon objavljivanja konkursa u kome je on jasno i naveden, jeste slanje prijave. Na konkurs se prijavljujete tako što pošaljete svoj CV i prateće pismo (cover letter). Onima koji se nikada nisu nigde prijavljivali ovo će biti prvi kamen spoticanja, jer će shvatiti da ni jedno ni drugo nije lako napisati; i CV i pismo treba da budu koncizni, jasni, da pružaju dovoljno informacija, i da vas, naravno, predstavljaju u što boljem svetlu. Jednom kada se ova prepreka prevaziđe, svako sledeće konkurisanje je lakše, jer već imate maltene sve spremno.
Ukoliko posmatramo ovogodišnju satnicu, sledeći korak je čekanje mesec dana. Ne poznajem ni jednu osobu koja se prijavila, a nije pozvana, ali pretpostavljam da i njima stiže e-mail u isto vreme kao i kandidatima pozvanim na test. Naime, oko tri nedelje pre testa MDCS šalje e-mail sa “čestitkama” i pozivom da dođete na testiranje tog i tog datuma. Ove godine je test održan u Matematičkoj gimnaziji u Beogradu, a ne u prostorijama u MDCS u Makedonskoj. Zašto? Možda zato što mu je prisustvovalo oko 150 ljudi.
Congratulations, we would like to invite you to the next step of the hiring process, which is a written test.
The test will take place at the Matematička Gimnazija on the Saturday May 7th, starting at 10:00 am. Microsoft staff will be at the site at 9:30 am.
The test covers basic Computer Science; we will ask you to write code for some problems and solve math problems. It is a paper and pencil test administered in English. It is 4 hours long.
Kao što je i najavljeno, test je počeo oko 10 ujutru (sa malim zakašnjenjem, naravno). Pre testa su svima pročitana uputstva i pravila, i tokom ovog govora imali smo priliku da dobro osmotrimo konkurenciju. Koliko sam ja mogao da primetim, većina ljudi je ipak bila nešto starija, pa pretpostavljam da su oni došli radi zaposlenja, a ne prakse.
А sada ono što ljude najviše interesuje – test.
Test se radi na papiru, na engleskom, bez ikakvih dodatnih pomagala (npr. digitrona) i traje četiri sata. Tokom tog perioda, srećom, dozvoljeni su odlasci u WC, kao i odlazak po hranu i piće koje je MDCS obezbedio, tako da je atmosfera u krajnjem slučaju veoma prijatna i opuštena. Ja obično nemam problema sa tremom, ali čini mi se da ni drugi ljudi nisu imali, možda baš zbog ovakve prijateljske atmosfere. U svakom trenutku je moguće postaviti neko pitanje vezano za zadatke, i sve će vam biti pojašnjeno (ja sam ovo možda i previše puta iskoristio, sigurno su me zapamtili). O prepisivanju ne treba ni pričati – em je teško izvesti ga, em nikome nije u interesu.
Što se tiče samih zadataka… Nisu teški. Možda je nešto teže sve postići za 4 sata, uvek se potkradu neke greške, i svakako je veoma teško imati maksimum poena — do sada to nikome nije pošlo za rukom — ali iz ovog ugla, posle testa, jasno je da nisu teški. Svako ko sebe smatra materijalom za Microsoft bi morao sasvim solidno da uradi test. Rečeno je da je, okvirno, potrebno preko 50% da bi neko bio pozvan na intervju, što je, složićete se, sasvim pristojna cifra koju nije teško dostići.
Od sedam zadataka koliko je bilo na testu, prvih pet je bilo iz programiranja, dok su poslednja dva bila iz matematike. Trik pitanja, kakva se mogu očekivati na intervjuu, nije bilo, ali su zadaci ipak zahtevali malo više razmišljenja i obraćanja pažnje na detalje. Sadržaj zadataka je bio sledeći:
- Dat je skup rimskih cifara (I, V, X, L, C, D, M). Potrebno je formirati rimske brojeve od svih ovih cifara tako da zbih brojeva bude minimalan. Za maksimalan broj bodova traži se linearna složenost. Jednostavan takmičarski zadatak.
- Dato je binarno stablo. Potrebno je obeležiti čvorove čiji je broj elemenata u njihovom podstablu (računajući i koren) manji od dubine tog čvora. Traži se linearna složenost. Ovaj zadatak čak ni nije takmičarski, više je običan školski primer.
- Na raspolaganju vam je N kutija i dozvoljeno je M bacanja. Kutije se bacaju sa nekog od spratova zgrade beskonačne visine. Ukoliko se kutija baci sa nekog sprata iznad sprata X, ona će se razbiti. Potrebno je sa najviše M bacanja kutija odrediti najviši sprat (tj. najveću vrednost koju algoritam uspe da pronađe) sa kojeg je moguće baciti kutiju a da se ne razbije. Malo konfuzan zadatak, ja sam ga loše protumačio.
- 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).
- Dat je neki tekst i željeni broj linija teksta. Potrebno je odrediti minimalnu širinu ekrana (u karakterima) takvu da tekst može da stane u željeni (ili manji) broj linija, bez prelamanja reči. Traži se nlogn složenost.
- Zadatak iz verovatnoće (obična i uslovna). Jednostavan, ali su jednačine nešto duže.
- Zadatak iz matematičke analize. Data je jedna funkcija; potrebno je odrediti funkcije koje (u kombinaciji sa početnom funkcijom) ispunjavaju određene uslove.
Dakle, neko ko barata svim ovim oblastima ne bi imao nimalo problema. Međutim, koliko sam ja video, nije bilo previše takvih među ovogodišnjim kandidatima — svi su se nešto žalili…
Rezultati se očekuju u toku nedelje, kada će se početi i sa ozloglašenim intervjuima. Oni koji su euforični zbog prolaska na intervju neretko bivaju izrešetani od strane zaposlenih uz pomoć najčudnijih, ali i najzanimljivijih pitanja. Tako sam ja barem čuo.
Neka im je sa srećom.
Dve nedelje nakon testa pozvan sam na intervju. Moje utiske možete pročitati ovde.
Добар текст, баш фино што си ово искуство поделио са људима. Није ми јасан овај 3. задатак, али претпостављам да га ни ти ниси добро разумео да би могао да га разјасниш :)
Знам да ти ово није било проблем, а имајући у виду да си бистар, жељно ишчекујем твој извештај са интервјуа ;) Срећно!
Ах, да, срећно и у Шпанији :D
Ono što je dovelo do moje greške jeste to što sam prevideo da se jednom bačena kutija, u slučaju da se ne razbije, može ponovo koristiti, pa to onda povećava broj mogućih bacanja. Naravno, iako je zgrada beskonačne visine, ograničen si na UINT_MAX, što se vidi iz zaglavlja funkcije koje ti je dato.
Što se tiče rešenja zadatka, i dalje mi nije jasno šta bi bilo tačno rešenje, niti kako procenjuju da li je neki algoritam dovoljno dobar. Očigledno je da se u nekim slučajevima ne može tačno odrediti koji sprat je kritičan, već je potrebno naći što približniju vrednost, pa su zbog toga mogući različiti pristupi algoritmu. Ja sam ispisao binarnu pretragu, ali ona, avaj, daje veoma loše rezultate za malo M…
Da li si resio ovaj zadatak naknadno, i da li si probao da promenis sa binarne na linearnu pretragu po odredjenom uslovu( recimo linearna je efikasnija kada se resenje nalazu u 1-koren od n). Interpolaciona pretraga deluje kao to sto su oni trazili, mada tesko da ces je napisati sam ako ne znas napamet onaj izraz vec smisljene interpolacione pretrage
aj kad si faca daj nam i resenja
Rado ću pomoći oko rešavanja ako neko zapne, ali nema poente pisati cela rešenja… S obzirom da je dato koja se složenost traži, nije teško proveriti da li je neko rešenje tačno ili ne.
Kako si prosao na testu? Jel su te kontaktirali za intervju? Meni se zadatci nisu bas cinili mnoogo laki, kako ih ti opisujes, a kolko vidim i ti si se namucio. Mada ja bas i nisam iz oblasti programerstva, pa ne mogu da tvrdim sta je lako, a sta ne :)
Još mi nije stigao nikakav mail. OK, nisu mnogo laki zadaci, ali veoma su daleko od nerešivih — zbog toga ja i nisam previše zadovoljan svojim učinkom, kad gledam iz ovog ugla…
Koja je ideja za 5 zadatak?
Cini mi se da dobijanje nekog arraya reci(preko regular expressionsa ili manuelno) nije resenje.
Sa druge strane imam sledecu(verovatno pogresnu) ideju:
nadju se sve pozicije u stringu gde se zavrsavaju reci, brojevi ili interpunkcijski znaci tj ili prazna mesta ili mesta gde se zavrsava rec, broj ili niz interpunkcijskih znakova npr “?!?!?”.
U recenici “Pera radi testove, a Djura ne radi… testove.” bi se po ovome gore nasle sledece pozicije (4,9,17,18, 20, 26,29,34). Potom bi za npr 4 redova, pokusavao da rasporedim 4 “markera” na te pozicije vodeci racuna da mi maximalni razmak izmedju svih markera bude minimalan. Nisam siguran kako bih to uradio u nlogn(n broj redova) doduse.
Da li bi mogao da objasnis pravo resenje(npr da napises algoritam bez implementacije u konkretnom jeziku) ili makar pravu ideju?
Osim ako sam još onda loše razumeo zadatak, n u složenosti se odnosi na dužinu teksta. Imajući to na umu, implementirao sam svojevrsno “bruteforce” rešenje upotrebom binarne pretrage.
Naime, ideja je da se radi binarna pretraga po dužini jednog reda. Na početku su granice za binarnu pretragu 1 i N. Kada se vrši jedna iteracije binarne pretrage, računa se koliko je redova potrebno ukoliko je jedan red dužine X – ovo se može uraditi jednim prolazom kroz tekst, linearno. Ukoliko je u toj iteraciji potrebno više linija nego što se traži u zadatku, povećavamo broj karaktera po redu (idemo na desnu polovinu intervala binarne pretrage). U suprotnom, prelazimo na levi interval.
Postupak se ponavlja sve dok se interval pretrage ne svede na jedan broj, što je ukupno logn iteracija, a u svakoj imamo n za prolazak kroz tekst.
Prvo hvala sto si podelio svoje iskustvo, jer je to jedino konkretno o njihovom testu sto sam uspela da nadjem.:) Nisam bas dobro razumela ovaj prvi zadatak. Koliko mi brojeva treba da napravimo od ovih cifara? Da li se gleda zbir cifara ili brojeva? Da li za svaki broj moramo da iskoristimo sve cifre? I mozda cu biti malo glupa, ali kako se tacno izracunava slozenost nekog algoritma. Ako bi mogao da me uputis na neki link gde bih to procitala, ali da bude nesto konkretno sa primerima. :) Hvala unapred!
Nije bitno koliko se brojeva napravi, ali potrebno je da se sve cifre iskoriste. Dakle, ako su date cifre IIVVXXCC možemo, na primer, da napravimo brojeve I, IV, V, X, X, C, C. Kada se to uradi, računa se zbir ovih novoformiranih brojeva.
Što se tiče računanja složenosti algoritma, ona se zasniva na broju operacija koje će se izvršiti za ulaz veličine N (npr. ako je dato N cifara). Ovo se može precizno izračunati analiziranjem algoritma, ali se kod ovakvih problema uglavnom koriste grublje procene, kao što su:
Korisni linkovi bi bili sledeći:
http://en.wikipedia.org/wiki/Analysis_of_algorithms#Run-time_analysis
http://en.wikipedia.org/wiki/Big_O_notation
Prvi zadatak je ovako nesto? Koristio sam hash_map umesto vectora jer mi je bilo lakse. Izvini ako mislis da je postovanje celih resenja lose ;)
int result = 0;
int tmp;
std::hash_map map;
map[‘I’] = 2;
map[‘V’] = 1;
map[‘X’] = 2;
map[‘L’] = 1;
map[‘C’] = 5;
map[‘D’] = 3;
map[‘M’] = 2;
//”I” can be subtracted from “V” and “X” only.
//”X” can be subtracted from “L” and “C” only.
//”C” can be subtracted from “D” and “M” only.
//”V”, “L”, and “D” can never be subtracted[
std::hash_map resultMap;
tmp = std::min(map[‘C’], map[‘M’]);
resultMap[900] = tmp;
resultMap[1000] = map[‘M’] – tmp;
map[‘C’] = map[‘C’] – tmp;
tmp = std::min(map[‘C’], map[‘D’]);
resultMap[400] = tmp;
resultMap[500] = map[‘D’] – tmp;
map[‘C’] = map[‘C’] – tmp;
tmp = std::min(map[‘X’], map[‘C’]);
resultMap[90] = tmp;
resultMap[100] = map[‘C’] – tmp;
map[‘X’] = map[‘X’] – tmp;
tmp = std::min(map[‘X’], map[‘L’]);
resultMap[40] = tmp;
resultMap[50] = map[‘L’] – tmp;
map[‘X’] = map[‘X’] – tmp;
tmp = std::min(map[‘I’], map[‘X’]);
resultMap[9] = tmp;
resultMap[10] = map[‘X’] – tmp;
map[‘I’] = map[‘I’] – tmp;
tmp = std::min(map[‘I’], map[‘V’]);
resultMap[1] = map[‘I’] – tmp;
resultMap[4] = tmp;
resultMap[5] = map[‘V’] – tmp;
auto iterator = resultMap.begin();
while (iterator != resultMap.end()){
result += iterator->first * iterator->second;
iterator++;
}
printf(“%ld\n”, result);
Rekao bih da je to to. Algoritam treba što više velikih cifara da oduzme, pa se cifre obrađuju počevši od C (zalepivši je za M), ka manjim vrednostima.
Hvala ti za informacije, a imam i par pitanja, posto sam pozvan na testiranje.
1) Kod ovog zadatka sa duzinom linija teksta, nije mi bas najjasniji algoritam koji si ostavio u komentaru. Tebi je koliko sam razumeo niz, zapravo ceo tekst. A binarnu pretragu vrsis po kojim parametrima (zapravo mi nije jasno kako odredjujes broj linija po iteraciji i sta ti predstavlja levi I desni interval niza).
2) kako sam uzeo da obnovim matematiku, da li bi mogao da mi kazes na koje oblasti da obratim paznju iz analize?
3) ovo je malo offtopic, vezano je za tekst sa intervjua, ali da ne kacim 2 komentara. Kada si rekao da imas K niza, koji imaju ukupno N elemenata, ako krenes redombkroz pocetke nizova (kao nakon rekurzije u merge sortu), slozenost je O(n) jer prolazis kroz ukupno N elemenata , imas par if naredbi I to je to. Ako gresim, mozes li da mi objasnis zasto je slozenost kn, I kako dobijas poboljsanje koriscenjem heapa (posebno, jer si rekao da utice na smanjenje sa k na logk)?
Ha, izvini na spam-u shvatio sam na sta mislis, pogresno sam procitao neke stvari :)
Jesi li odgovorio sâm sebi na sva tri pitanja, ili je neko i dalje aktuelno? :)
Odgovorio sam samo na prvo :) druga dva me I dalje interesuju :)
Iz matematike su bitna verovatnoća (obična/uslovna i sl.) i analiza (limesi, izvodi, mooožda i integrali).
Što se tiče tog zadatka sa intervjua, stvar je u tome što spajanje nizova nije isto kao kod merge sorta. Kod njega prolaziš paralelno kroz dva niza, što se može lako realizovati, ali ovde imaš veliki broj nizova, pa to nije moguće. Tačnije, za svaki element moraš da odabereš iz kog niza ćeš ga uzeti, a kako ima K nizova, to je K poređenja, pa je složenost k*n.
Ako se tu još ubaci i heap, ne moramo da imamo po K poređenja za svaki element, i to tako što ćemo u heapu čuvati prve elemente svih K nizova. Na vrhu heapa se uvek nalazi sledeći koji uzimamo, i kada to učinimo, u heap dodamo sledeći element iz odabranog niza. Kako su operacije sa heapom logK, ukupna složenost je n*log(k).
Nacukao sam bio(imao sam malo vremena od posla :)) neki gist koji bi mozda trebao da bude resenje 5tog zadatka.
Ako bi hteo da ga pogledas da vidis da li treba da ga sklanjam ili ne (a usput ako nije problem da mi kazes gde gresim :) ) https://gist.github.com/2871157
Izvini što ti tek sad odgovaram, bio sam u gužvi prethodnih dana.
Bacio sam pogled na kôd, i to je ta ideja. Možda ima nekih sitnijih bagova, ali to bi moglo da se primeti tek kod testiranja. Samo ni nije jasno jedno — zašto ti je na početku desna granica txtLength-2, a ne txtLength-1?
Takođe, program bi se još mogao ubrzati kada bi kod tokom učitavanja čuvao reči kao celine umesto karakter po karakter. U tom slučaju ne bi morao u svakoj iteraciji binarne pretrage da radiš get_word(), već bi imao izračunate dužine reči, pa bi samo njih sabirao.
4/28/2012 Belgrade
1) Three points are given A(x1, y1), B(x2, y2), C(x3, y3). Write a method returning an array of points (x, y) inside the triangle ABC.
2) Implement Stack that also has method that returns maxumum element on stack. Faster solution for more points.
3) Implement Iterator to walk through files in a directory and all subdirectories. Interface of an API to be used was given.
4) a) In-order visit of nodes of binary search tree is forming string (in-order visit: visit node, than visit in-order left son, the visit in-order right son). Based on the output string for the in-order visit, reconstruct the binary tree.
Example:
String 5214768 reconstructs binary search tree
5
2 7
1 4 6 8
b) Can you reconstruct the binary search tree based on string for pre-order visit (pre-order visit left son, then visit the node, then pre-order visit right son)? Why, or why not?
5) a) In the game of battleships, ten 1-square ships are placed on 10X10 board. What’s the probability that two 1-square ships on opponents’ boards are in the same spot.
b) In the game of battleships, eight 1-square ships and also one 2-square ship are placed on 10X10 board. What is the probability that two ships intersect?
6) On the chess board a rook is placed in the corner. Two squares on the board are occupied. Write a method to return all possible 3 moves for the rook to go from its corner to the opposite corner, but it cannot go through occupied squares.
7) Give an example of function f(x) with no breaks knowing the following:
* f(-2) = -1
* f(2) = 1
* f(6) = -1
* the surface under f(x) above x axis is less than 1.99
Solution by segments don’t give max points. Solution should be the same expression for the whole range [-2, 6].
Tip: function doesn’t have to be differentiable, just continuous.
Hvala! Koristiće nekome :) Jako zanimljivi zadaci, ali nisu mnogo teški…
Zadaci sa testa – April 2013:
1. Data su dva cela broja p i q. Treba ispisati sva vremena kada je ugao izmedju kazaljki za sate i minute jednak p/q od punog ugla (i.e. 360 * p/q), ili “no” ako ne postoji ni jedno takvo vreme. Smatrati da kazaljke menjaju pozicije svakog minuta i da izmedju svaka dva minuta miruju.
2. Zadato je binarno stablo koje predstavlja disjunktne intervale u svojim listovima (oni mogu biti ili beli i crni). Što je veća dubina nekog lista, to je interval koji on predstavlja duži. Treba odrediti dužinu najdužeg belog intervala (gde za jediničnu dužinu uzimamo dužinu intervala koji je najdublje u stablu). Za maksimalan broj poena traži se O(N) rešenje (gde je N broj čvorova u stablu).
3. Koristeći C-ovske funkcije malloc i free, napisati funkcije AlignedMalloc i AlignedFree. AlignedMalloc osim veličine koja se alocira takodje ima i parametar alignment, i traži se da memorijska adresa koju vrati ova funkcija bude deljiva sa alignmentom. AlignedFree treba da oslobodi memoriju alociranu sa AlignedMalloc-om ako joj se prosledi pokazivač koji AlignedMalloc vrati.
4. Implementirati klasu MaxStack, koja kao i običan stack ima metode push i pop, kao i funkciju GetMaximum(), koja vraća maksimalni element u stacku bez menjanja njegove strukture. Za maksimalan broj poena traži se O(1) rešenje po operaciji.
5. Zadata je šahovska tabla veličine NxN, kao i niz polja te table koja su blokirana. Potrebno je odrediti broj načina na koji top može preći iz polja (0,0) u polje (N-1, N-1) u tačno 3 poteza.
6. 4n tačaka su ravnomerno rasporedjene na ivicama kvadrata (n+1 tačaka na svakoj ivici).
a) Na koliko načina možemo odabrati tri tačke tako da one prave (nedegenerisani) trougao?
b) Na koliko načina možemo odabrati tri tačke tako da su dve na istoj ivici, a trougao koji one formiraju nije tupougli?
7. Definisati elementarni (non-piecewise) izraz za funkcije koje imaju sledeće grafike:
a) f(x) je izlomljena linija koja je nula za x <= c, onda menja pravac tako da prolazi kroz tačku (a,b).
b) f(x) je izlomljena linija koja prolazi kroz… sedam različitih tačaka. Ne sećam se tačno koje su :D
Jel vec bilo testiranje? Izgleda da sam se kasno prijavio :(
Na sajtu (http://www.microsoft.com/serbia/mdcs/internship.aspx) ne piše nikakav rok, a s obzirom da često organizuju testiranja, slobodno im pošalji svoj CV i prijavi se.
Hvala :)
Poslao sam im, pa videcemo… :)
Kako se resava 7. zadatak iz aprila 2012? Hvala unapred…
S obzirom da je hint da funkcija ne mora da bude diferencijabilna, nekako se nameće da će rešenje imati neki “šiljak”. Najpoznatija takva funkcija je najverovatnije apsolutna vrednost, pošto ima šiljak u nuli usmeren na dole. Ako pametno transformišemo funkciju, možemo dobiti rešenje koje ima odgovarajuće vrednosti u -2, 2 i 6:
-|(x-2)/2|+1
Međutim, površina funkcije iznad x-ose ne zadovoljava uslov zadatka, jer je ona 2. Zbog toga moramo taj gornji trougao nekako da suzimo, tj. da “ulubimo” ivice. Za ovo možemo umesto x koristiti razne trigonometrijske funkcije, ali najlakše je upotrebiti koren, pa se dobija sledeće rešenje koje se lako proverava:
-sqrt(|x-2|)+1
Druga moguća rešenja, doduše teža za verifikaciju, su:
arccos(|x-2|/2-1)*2/pi-1
-|arctg(x-2)*2/arctg(4)|+1
Hvala svima na korisnim informacijama. Imam samo jedno pitanje: u kom programskom jeziku/jezicima je moguce na testu resavati programerske zadatke? Da li moze samo opis algoritma, neka pseudo forma… Ako ne, da li u obzir dolazi i npr. Java, ili samo nesto sto vise tezi MS-u, C/C++, C#?
Nema ograničenja koji jezik može da se koristi, ali pseudokôd nije dozvoljen. Naravno, ukoliko je ostalo malo vremena, a imaš dobru ideju, bolje je bar nešto napisati, pa makar to samo bio opis algoritma ili pseudokôd.
Pozdrav Nenade,
Hteo sam da te pitam da li je uobicajeno da poziv za test dobijem 3 dana pre odrzavanja istog?
Moje drugo pitanje odnosi se na sam test s obzirom da nisam programer i smatram da nisam preterano vest u tome. Ja sam se prijavio u cilju istrazivanja (research-a), po ugledu na laboratorije u NY. S obzirom na ovo, da li imam sansu da prodjem test? Napominjem da nisam zainterosavan za posiciju software developer-a (kao ni za praksu).
Hvala unapred na odgovoru i na fantasticnim tekstovima!
Ne bih rekao da je uobičajeno – recimo, ja sam poziv dobio dve nedelje pre testa. Verovatno su hteli da pozovu što više ljudi koji su se prijavili, pa su malo okasnili sa procesom odabira. Nadam se da ćeš ipak moći da prisustvuješ testu, greota propustiti ukazanu priliku.
Što se tiče samog sadržaja testa, on bi trebalo da je isti za sve pozicije, odnosno i za posao i za praksu i za research. Samim tim, biće ti potrebno znanje iz programiranja i matematike, ali imaj na umu da je na testu dovoljno nekih 50% da bi ga prošao, što bi te onda dovelo do intervjua koji su drugačiji za različite pozicije.
Hvala jos jednom na odgovoru! Prihvatio sam poziv na test pa cemo videti sta ce biti…
Perice, upravo sam doživeo istu stvar. Dobio sam poziv, ali moje znanje programiranje je ono koje sam naučio u srednjoj školi (npr. programirati kalkulator) i kao što možeš videti, ne podudara se toliko sa ovim zadacima. Napomenuću da smo učili osnove Pascal-a i Delphi-a kojih se i dan-danas sećam.
Kako si prošao sa testiranjem i da li je bilo toliko zastupljeno programiranje?
P.S. Tebi Nenade jedno veliko hvala, jer je ovo jedini sajt na koji sam naišao sa ovako dobrim informacijama. Ukoliko smatraš da mogu da doučim neke informacije za ova tri dana, a tiču se ovih zadataka, zamolio bih te da okačiš relevantne linkove koje verujem, neće samo biti meni od pomoći, već i drugima.
Izvini, tek sam sad video komentar, ali možda moj odgovor kasnije bude koristan i drugima.
Programiranje je dosta zastupljeno, tako da je ipak potrebno solidno znanje – srednja škola daje dobru osnovu, ali se tu uglavnom ne rade algoritmi i strukture podataka, koji su okosnica testova i intervjua u većini ovakvih kompanija. Te stvari se obično izučavaju tokom čitavih studija, i ove oblasti su veoma obimne, ali mislim da bi neko ko se samo tome posveti mogao da spremi intervju za nekih pola godine.
Cao, evo zadataka sa testa odrzanog 23. novembra 2013. Znacice ljudima.
1) Zadato je binarno stablo za pretragu.
a) napisati funkciju koja vraca vrednost k-tog najmanjeg elementa u stablu
b) napisati funkciju koja vraca sumu prvih k najmanjih elemenata u stablu
Za maksimalan broj bodova trazi se O(1) prostorna kompleksnost.
2) Zadata je povezana lista. Napisati funkciju koja brise sve cvorove iz liste za koje postoji cvor sa vecom vrednoscu na desnoj strani.
Za maksimalan broj bodova trazi se O(1) prostorna kompleksnost.
3) Data je deifinicja funckije u c-u.
a) objasniti sta zadata funckija radi
b) optimizovati zadatu funckiju
4) Dat je niz integera. Izracunati sumu HammingDistance-i za svaki moguci par elemenata iz niza. HammingDistance za dva broja predstavlja broj bitova koji se razlikuju u binarnoj reprezentaciji tih brojeva.
Trazi se sto bolja kompleksnost.
5) Ulazni podatak je niz redno postavljenih domina. Niz x predstavlja pozicije domina na x koordinati, niz h predstavlja visine domina. Napisati funkciju koja odredjuje koju dominu treba oboriti i u kom smeru, kako bi se formirao “lanac” oborenih domina maksimalne duzine.
Trazi se sto bolja kompleksnost.
6) Zadatak iz kombinatorike
7) Zadatak iz analize.
Od prva tri zadatka potrebno je uraditi bar dva da bi kandidat bio razmotren za intervju. Generalno mislim da zadaci nisu teski. Sa ove tacke gledista, mogao sam malo bolje da odradim. Moj savet ljudima koji budu polagali test je da dobro procitaju zadatke, lepo organizuju vreme jer ga nema dovoljno,i da se prvo fokusiraju na lakse zadatke.
Mene interesuje šta se očekuje od kandidata da napišu u CV-ju? Jasno je da, ako se prijavljujem za praksu, nemam nikakvo iskustvo niti bilo šta takvo, ali šta je zapravo bitno da se napiše? Ja planiram da ispišem projekte na kojima sam radila tokom studiranja i generalno informacije o studijama i skillovima vezanim za profesiju. Ne znam koliko je važno da pišem podatke iz srednje škole, s obzirom da sam išla u opštu gimnaziju, ili tako neke stvari sa strane koje nemaju veze sa programiranjem, niti da li da napišem jednu ili dve strane (očigledno prvi put u životu pišem CV :)). Pretpostavljam da motivaciono pismo ima nekako veću težinu. I generalno, da li je CV uopšte važan, jer ako sam dobro pročitala ovde na sajtu, svi koji se prijave budu pozvani na test? Hvala unapred
CV je tu da pokaže da ima smisla da te pozovu na test, dakle da imaš veze sa programiranjem. Ukoliko se dobro sećam, ja sam na svom prvom CVu imao obrazovanje (završena srednja škola i prosek, fakultet i trenutan prosek), takmičenja, vannastavne projekte, poznavanje tehnolgoija (npr. lista programskih jezika) i poznavanje stranih jezika. Dakle, ne previše informacija vezanih za srednju školu, osim ako mogu imati nekakve veze sa programiranjem (npr. takmičenja iz matematike). Ovo bi sve trebalo da može da ti stane na jednu stranu, i preko toga ne bi trebalo ići.
Motivaciono pismo mi nikada nije bilo jasno, pošto ga svi ionako pišu potpuno veštački i po nekakvim šablonima – ako se već prijavljuješ za praksu, logično je da imaš želju da tu praksu i dobiješ. Al’ svakako ga napiši kao i svi ostali, običaj je…
Pozdrav, izvinjavam se sto odgovaram na ovako star tekst.
Zanima me kako se radi ovaj problem sa buleanskim izrazima, samo ideja, naravno. Znam kako bih uradio za n*broj zagrada, ali linearna slozenost, nemam pojma.
Unapred hvala
Jeste prošlo pet meseci, ali nikad nije kasno… Opisao sam rešenje zadatka u novom tekstu:
https://www.bozidarevic.com/2015/02/parsiranje-bulovih-izraza/
Evo zadaci 10.10.2014 (Ne uzimati sve zdravo za gotovo, cisto da prenesem koliko se secam :D)
1. Data je matrica brojeva od 0 do 255 (kao piksela) i potrebno je odrediti najveci moguci niz ponavljajucih vrednosti bilo horizontalno bilo vertikalno, pritom se zna da je prolaz kroz redove mnogo efikasniji od prolaza kroz kolone zbog bafera.
2. Dat je niz ID-jeva automobila i potrebno je implementirati klasu koja nasledjuje interfejs koji u sebi ima metode crash(id) i advance(id)(da prestigne) i metodu koja ce na kraju, posle odredjenih operacija, ispisati trenutno stanje u trci.
3. Dat je niz binarnih brojeva i potrebno je odrediti najveci moguci podniz koji sadrzi podjednako nula i jedinica. Npr (0,1,0,0,1,0,1) rezultat je 3 Poenta je u sto boljoj efikasnosti.
4. Dato je bst stablo i broj nekog lista i potrebno je napraviti stablo gde je taj list koren od ostalih elemenata stabla. Isto poenta u sto boljoj efikasnosti.
5. Je bio nesto bas dug sa pizza mestima i kucama i razlikama izmedju pizza mesta, tako ne mogu da se setim kompletno :/
6. Da se nadje funkcija kojoj ce asimptote biti y = a*x i y=0 koliko mi se cini.
7.a) Dat je spil od 32 karte, igraju 2 osobe i izvlace po 3 karte. Koja je verovatnoca da je najveca karta osobe A manja od najmanje karte osobe B.
b) Isto to, samo bacaju kockicu 3 puta i koja je verovatnoca da najveci broj koji dobije osoba A bude manja od najmanjeg broja osobe B.
[…] texts about entire application process that I found was at the Nenad Bozidarevic’s blog: Utisci sa testa za praksu u Microsoft-u (Serbian-only). It gave me an insight of the kind of problems that are chosen for the test and the […]
[…] 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. […]
Ovaj sajt mi je bio od koristi i osećam obavezu da doprinesem (a i treba deliti). Test je upravo održan, april 2015.
1. Data je deo po deo linearna pozitivna funkcija čvorovima xi i yi. Treba naći vertikalne linije xa i xb koje dele površ između grafika i x ose na tri dela jednake površine.
2. Binarno stablo, svaki čvor ima dva pointera na decu ili na NULL i int vrednost. Treba izračunati sumu svih parnih vrednosti na k-toj dubini i od nje oduzeti sumu svih neparnih vrednosti na k-toj dubini.
3. Žica dužine l se prostire duž x ose i fiksirana je u koordinatnom početku a može da se rasteže i skuplja homogeno za vrednost između -e i e, 0<e<l. Na žici se nalazi n čvorova čije su početne koordinate date (između 0 i l) i sortirane. Kad se žica deformiše ovi čvorovi se kreću levo-desno. Na koordinati K nalazi se stub. Treba odrediti dužinu deformisane žice tako da je rastojanje od stuba do najbližeg čvora minimalno.
4. a) Na n polja nalazi se s robota čije su koordinate date. U svakom koraku roboti se kreću za jedno polje sa leva na desno, oni levi prvo, osim ako se na selećem polju već nalazi drugi robot. Treba napisati funkciju koja računa za koliko koraka će se roboti zaglaviti, u asimptotski optimalnom vremenu.
b) bilo je nešto, ne sećam se.
5. Data je int matrica MxN. Treba naći koliko ima podmatrica takvih da je zbir njihovih elemenata (ili možda elemenata u svakoj vrsti?) manji od zadate vrednosti. Traži se optimalna efikasnost.
6. a) Osam topova na šahovkoj tabli. Izračumati verovatnoću da se međusobno ne napadaju.
b) Dva bela i dva crna topa. Izračunati verovatnoću da se beli i crni međusobno ne napadaju.
7. Dati primer funkcije koja teži beskonačnosti za plus minus beskonačno, manje je od nule u plus minus 10 i pozitivna je u nuli. Ne sme biti definisana deo po deo već preko jednog izraza.
[…] на Ненад Божидаревиќ (инаку и една од причините зошто го започнав овој […]
Test za posao/praksu se razlikovao malo od ustaljenog formata. Ovaj put su bila postavljena četiri zadatka iz programiranja, a vreme za izradu je bilo 3 sata – dakle, u proseku više vremena po zadatku. Evo otprilike zadataka, kako ih se sećam:
1. Dat je niz brojeva. Treba formirati stablo tako da unutrašnji čvorovi (oni koji imaju potomke) budu neparni brojevi, a listovi (čvorovi koji nemaju potomke) budu parni. Dodatni uslov je da pre-order traversal (izvinjavam se, ali ne znam srpski termin) bude identičan datom nizu. Stablo je zadato tako da svaki čvor ima pokazivač na prvo dete (child) i pokazivač na brata (sibling).
2. Napisati funkciju koja proverava da li između dva stringa postoji 1-1 preslikavanje. Npr. između “good” i “feel” postoji 1-1, između “good” i “heal” ne. Obratiti pažnju na to da stringovi mogu biti različitih dužina (ovo je moja napomena, nije bilo eksplicitno rečeno u tekstu zadatka).
3. Zadat je niz dužine N=2^k. Naći maksimalni period niza, gde se pod periodom podrazumeva pod-niz koji ponavljanjem gradi zadati niz. Na primer, niz ABABAB ima period dužine 2 (AB), ali ABABA ima period dužine 1.
4. Data je jedostrano ulačnana lista. Napisati funkciju koja pravi inverziju redosleda između dva zadata čvora. Npr, u listi 1->2->3->4->5, ako su zadati čvorovi 2 i 4, rezultat treba da bude 1->4->3->2->5.
Koja je ideja za 3. zadatak?
Ima li neko bolju ideju za 3 zadatak od n*logn slozenosti?
Pozz
Mislim da je tekst zadatka pomalo netačan – verovatno je potrebno naći minimalni period niza (tj. najkraći podstring), odnosno period koji se najviše puta ponavlja:
– za string ABABAB period je dužine 2 i ponavlja se 3 puta
– za string ABABA period je dužine 5 i ne ponavlja se, tj. ponavlja se jednom
Takođe je bitno primetiti da je dat string dužine N=2^k, pa je njegova dužina deljiva isključivo sa stepenima dvojke, što dalje znači da i sâma perioda mora da bude dužine 2^p. Sada možemo napraviti sledeće zaključke:
– Niz će uvek imati periodu dužine N
– Sledeće moguće rešenje je perioda dužine N/2. Ovo možemo provetiti tako što redom poredimo karaktere 0 i N/2, 1 i N/2+1, 2 i N/2+2 itd.
– Ukoliko smo prethodni korak uspešno završili, to znači da su prva i druga polovina stringa identične. U slučaju da nisu, znamo da kraća perioda ne može postojati, pa možemo da prekinemo pretragu. Međutim, ukoliko ova perioda postoji, u sledećem koraku, kada budemo tražili periodu dužine N/4, dovoljno je da to proverimo samo na prvoj polovini stringa, jer znamo da je druga identična.
Kada se sve to uzme u obzir, ove provere će redom biti N (za periodu dužine N/2), N/2 (za N/4), N/4 (za N/8), itd.
Kako je N + N/2 + N/4 + … + 1 = 2N – 1, ukupna složenost bi bila 2*2^k-1, odnosno O(N).
E sad, sledeće pitanje koje treba postaviti jeste da li je moguća bolja složenost od te?
1. Izracunati matematicki izraz bez koriscenja dodatnih biblioteka, tipa Math. Izraz se sastoji od integera i znakova matematickih operacija +, – i *. Naravno potrebno je voditi racuna o prioritetu operacija. Na primer 12+2-4*2*6-1+212*5
2. Dato je binarno stablo, podaci u elementima su tipa int. Dat je niz integera. Potrebno je napraviti metodu koja ispituje da li je pre-order prolazak kroz stablo subsequence(podniz) datog niza.
3. Data je jednostruko spregnuta lista(pokazivaci samo na naredni cvor), podaci su tipa int. Potrebno je napraviti metodu koja kao ulazni arg prima listu i iz nje izbacuje sve cvorove koji posle sebe imaju cvor sa vecom vrednoscu. Primer: od liste 4->3->10->2->7->3->1->3 treba da dobijemo listu 10->7->3->3
4. Neki zadatak sa ogromnim i pomalo konfuznim tekstom. Alisa hoce da napise neki tekst na papir, koji ima svoje dimenzije u mm, njen tekst ima odredjeni broj karaktera(samo slova, space i .) i treba da odabere sto veci font da tekst stane na stranu, svaki font ima sirinu i visinu slova, i svaki je monospace(svako slovo ima istu visinu i sirinu). Pri tom ako cela rec ne staje u red ona dodaje crticu(-) i prenosi ostatak reci u sledeci red. Ako u red moze da stane samo jedno slovo od reci, dodaje se space i cela rec ide u novi red. Potrebno je napraviti metodu koja kao parametre prima tekst, njegovu duzinu(mada to se moze dobiti iz teksta), visinu i sirinu strane i niz dizmenzija fontova(na primer [(20,25),(30,35),(30,45),(35,50)]) poredjanih po rastucem redosledu, a treba da vrati 0 based index najveceg fonta koji se moze koristiti da ceo tekst stane na stranu.
1. Sortirati jednostruko spregnutu listu koriscenjem jednog transfera, gde “transfer” predstavlja izbacivanje nesortiranog cvora i ubacivanje istog cvora na odgovarajuce mesto. Ukoliko lista ne moze da se sortira samo jednim transferom, vratiti false u suprotnom true. Npr: 2 -> 3 -> 1 -> 4 moze da se sortira jednim transferom i postaje 1 -> 2 -> 3 -> 4, dok 2 -> 4 -> 3 -> 1 ne moze da se sortira. Trazila se linearna slozenost.
2. Dato je stablo sa dva pokazivaca na svoju decu. Naci najduzi put u binarnom stablu izmedju dva cvora.
3. Dat je string iz kog treba izbaciti odredjeni karakter. Npr string je “abcdc” a karakter za izbacivanje je “c”, rezultat je “abd”. Zahtev je bila O(1) prostorna kompleksnost.
4. Ne secam se. Neki matematicki zadatak sa funkcijama.
Ako moze ispravka teksta za zadatak broj 2, Avgust 2016. Naime, u binarnom stablu put izmedju svaka dva cvora je jedinstven, nema sta da se trazi najduzi put.
Ako se neko seca teksta zadatka sa ovog testiranja, neka ispravi.
Pozdrav!
Mislim da nije u pitanju traženje puta između dva određena čvora, već nalaženje najdužeg puta u stablu između bilo koja dva čvora, tj. nalaženje dva najudaljenija čvora.
OKTOBAR 2016
Da pokušam ja iz glave da opišem test. Sastojao se iz 4 zadataka, svi su bili programerskog tipa.
1. Dato je binarno stablo. Potrebno je proveriti da li koren ima bar jedan čvor i da li je vrednost čvora jednaka sumi svih njegovih podstabala. I ako nije, treba ispisati njenu putanju do tog čvora. Dakle ako imamo stablo:
Potpis metode: public void writeSubTree(Node root)
17
3 6
1 1 4 2
Program treba da ispiše. 17 3
2. Data su 2 stringa. Potrebno je napraviti metodu koja proverava da li je prvi string podstring drugog. Koriste se samo velika abecedna slova. Prvi string može koristiti i karakter “@” koji označava džokera.
Potpis metode koje je dat: public boolean checker (char a, b)
Primeri: s1 = XYXY s2= XY return true
s1 = XY@Y S2= XYX return true
s1 = XYXY s2= XX return false
3. Data je dvostrukospregnuta lista i pokaziavč na prvi element. Potrebno je napraviti metodu koja ispisuje istu listu u formatu “par-nepar” element. Tačnije uzima prvi neparan i zamenjuje ga sa poslednjim neparnim elementom.
Potpis metode: public Node writeReturn(Node head)
Dakle ako imamo listu: 1 2 3 4 5 treba dobiti 1 4 3 5,
ili 8 9 7 4 5 6 treba dobiti 8 6 7 4 5 9
ili 7 8 6 17 5 16 1 4 treba dobiti 7 4 6 16 5 17 1 8
4. Ne mogu da se setim. Bilo je nešto sa kvadrantima i koordinatnim sistemom.
*****Ono što sam primetio na testu je da nije moralo da se brine o kompleksnosti alogritma (nigde nije bilo naglašeno). Što je po meni bila olakšavajuća okolnost.
Toliko do mene. Ako je još neko radio u ovom roku neka me ispravi ako sam nešto pogrešio ili neka dopuni 4. zadatak. Pošto sam pisao iz glave, možda se potkrala koja greška, ali ovo je suština. Pozdrav
P.S. Hteo bih svima da se zahvalim koji su pisali zadatke ranije, meni je dosta pomoglo pri srepamnju. Na ovaj način se odužujem :D Posebnu zahalnost dugujem Nenadu koji je pokrenuo sve ovo.
Evo, da dopunim za 4ti zadatak. Potpis funkcije je int function(double x1, double x2, double y1, double y2). Date su dve tačke i treba kao povratnu vrednost vratiti kvadrante u kojima se nalaze tačke duži koju čine te dve tačke. Povratna vrednost je u stvari četvorocifren binaran broj prebačen u int pri čemu su cifre kvadranti, pri čemu su s desna na levo redom I, II, III i IV kvadrant. Znači ako se duž prostire kroz I i IV kvadrant, to je 1001 tj. vraćamo 6.
I ako za ovaj test nisam stigla da provežbam, videla sam bar kako otprilike izgledaju zadaci i vidim odakle ću se spremati za sledeći test. ;) Tako da, veliko hvala svima koji su doprineli.
Hvala vam što ste podelili ovo :) Napomenuo bih samo da, iako nisu eksplicitno naveli da je kompleksnost algoritama bitna, uvek treba tražiti što bolju, jer to može da napravi razliku između dobrog i odličnog kandidata.
3 zadatak, Oktobar 2016? Koja je ideja kako da se uradi i u kojoj slozenosti? Ako neko zna moze pomoc?
Pozz
TACNIJE 2 ZADATAK ME ZANIMA< OVAJ SA STRINGOVIMA?
Pozz
Pozdrav svima,ako neko hoce nek me doda na Linkedin-u(Petar Jaredic) da razmenimo iskustva oko spremanja ispita za Microsoft.
Nenade,tebi svaka cast sto si pokrenuo ovu pricu i pomogao nama koji konkurisemo za Microsoft.
Ovo su zadaci iz decembra 2016. Pisani su po secanju, tako da ako je neko bio na testu i misli da sam nesto pogresio neka ispravi (pogotovo 3. i 4.) :) Hvala svima na prethodnim testovima :)
1. a) Data je jednostruko ulacana lista. Potrebno je napisati funkaciju koja vraca listu sa obrnutim redosledom. npr ako je data lista 1->3->5->7->null potrebno je vratiti 7->5->3->1->null.
1. b) Data je isto jednostruko ulancana lista i potrebno je napisati funkciju koja vraca bool true ili false da li je lista palindrom, tj da li su njeni elementi isti kad se citaju u levo i desno. npr ako je dato 1->5->6->5->1->null treba vratiti true, isto za 1->5->5->1->null. A false npr za 1->2->4->6->null.
2. Napraviti funkciju koja prima int N, a vraca int koji oznacava koliko ima brojeva od 0 do 10^N koji imaju jedinstvene cifre. Npr ako je N=2 potrebno je vratiti 91, jer od 0 do 100 ima 10 brojeva koji ne spadaju u te brojeve [11,22,33,44,55,66,77,88,99 i 100].
3. Dato je binarno stablo koje sadrzi cvorove koji imaju pokazivace na first child i next, bool koji govori da li su operacije u sledecem nivou stabla paralelne (konkurentne) (true) ili ne (false) i int koji daje broj sekundi za koje je potrebno odradtiti tu operaciju. Potrebno je naci ukupno vreme potrebno da se odrade sve operacije u stablu. (Cisto da se zna, operacije stvarno ne postoje, nego je samo dato vreme za te “operacije”) Npr ako je dato stablo
9s
false
|
6s – 5s
false false
| |
3s 1s – 2s – 3s
true
|
2s – 3s – 4s – 5s
Rezultat je 26s.
4. Data je klasa class StringCollection u kojoj treba realizovati sledece funkcije:
doadti i izbaciti iz kolekcije string – AddToCollection(char* s); RemoveFromCollection(char* s);
-za dva stringa naci najveci zajednicki prefiks( “ABCD”, “ABPO”, najveci zajednicki prefiks je “AB”
-za zadato k, u kolekciji stringova naci zajednicki prefiks za najmanje k stringova (“ABC”,”ABFG”,”ABNN”, “AC”, za k=4 treba “A”, za k=3 “AB” valjda)
Pozdrav,
Dusan.
Za 3. zadatak stablo se poremetilo. Sto se tice ove dve uspravne crte u sredini, prva je izmedju 6 i 3, a druga izmedju 5 i 1. :)
Ako moze samo pojasnjenje za 3 zadatak, zar ukupno vreme za dati primer nije 34s? Po mojoj racunici?
Pozdrav, Aca.
Dusane, hvala na zadacima koje si napisao.
Ako moze samo pojasnjenje za 4-ti zad. u kom se jeziku radi i kako je klasa predstavljena, konkretno na sta se misli kad se kaze “ukloniti iz klase”.
Pozdrav..
class StringCollection
{
StringCollection();
~StringCollection();
void AddToCollection(char* s);
void RemoveFromCollection(char* s);
void longestCommonPrefix(int k);
};
Treba da se omoguci i postojanje istih stringova, tako da je potrebno voditi racuna i o tome prilikom izbacivanja stringova.
longestCommonPrefix(int k) treba da ispise najduzi zajednicki prefix bilo kojih k stringova koji se u tom trenutku nalaze u strukturi podataka.
Mozes u bilo kom jeziku, mislim da su na pocetku testa naveli da je pozeljno neki od sledecih: C#, Java, C++.
Pročitao sam na više mesta da test može da se radi u čistom C-u, pa me zanima šta bi se desilo u slučaju da padne zadatak kao što je ovde četvrti koji vezan sa objektne jezike. Da li postoji alternativni zadatak za ljude koji rade u funkcionalnom ili mora da se uradi tako kako je postavljeno u nekom drugom jeziku?
Pozdrav i hvala.
Mislim da ne bi bilo previše komplikovano da se zadatak realizuje sa globalnim promenljivama i funkcijama (jer je sâma logika i dalje ista), ali isto tako je za očekivati da kandidati poznaju barem jedan objektno-orijentisani jezik, jer se 99% vremena radi u nekom od njih.
Da li kod 4 zad. Decembar 2016 mi sami biramo private clanove klase StringCollection kako cemo da cuvamo stringove, i da li je moguce koristiti stl recimo ako kodujemo u cpp pa da onda ove stringove cuvamo u reciko hash_map ?
Ako moze neko neka pojasni,
Poz Nenad
Mislim da je odgovor na oba pitanja potvrdan – bez privatnih promenljivi ne bi ni mogao da se reši zadatak, a i nema razloga zašto ne bi koristio sve funkcionalnosti koje neki jezk nudi.
Da li se zadaci na testiranju rade isključivo u C-u?
Koji su termini za polaganje testa?
Pozdrav
Ako znaju oni koji su prosli dalje, ili ti Nenade, da li se intervjui obavljaju skroj na engleskom ili ide pola eng. pola srpski, kao i da li mora da se zna nek progr.i jezik ili moze da se pise pseudo?
Pozdrav, aca
Na intervjuu se koristi engleski jezik za komunikaciju, doduse na pocetku se par recenica prozbori i na srpskom.
Mislim da je potrebno da se radi u nekom programskom jeziku.
Override hvala ..
Reci mi samo koji je to nivo poznavanja engleskog koliko tecno sve to treba da zvuci?
Koji jezik preporucujete?
Pozdrav, aco
Potrebno je predstaviti sebe u najboljem svetlu, a za to je potrebno poznavanje svakodnevnog engleskog. Naravno niko ne ocekuje da govoris tecno kao maternji jezik.
Od programskih jezika mislim da mozes bilo koji od: C, C++, Java, C#, Python
Da li je dovoljno samo main metodu napisati ili mora čitava deklaracija i klase i sličnoga?
Obično je dovoljno napisati samo funkciju koja rešava problem, tj. čak ni main() nije potrebno – osim ukoliko se tako nešto traži u zadatku, naravno.
Da li neko moze da podeli iskustva vezana za intervju za poziciju Data scientist?
Zna li neko kako izgleda test za poziciju Math Data Collection and Labeling Associate ?
4 zadatka i 3 sata. Ko je provezbao, dovoljno vremena da se uradi. Zadaci su na engleskom, svaki zadatak ima opis, input i output, i eventualno sliku (da pojasni sustinu). Moze bilo koji programski jezik. Ne smeju se koristiti konteneri tipa Dictionary, List… Za svaki zadatak je potrebno napisati po jednu funkciju, data je deklaracija funkcije. Opisacu svojim recima kako su izgledali zadaci.
1. Data je jednostruko spregnuta lista. Treba napisati funkciju koja obrce listu parcijalno (u zavisnosti od broja k). Obrtanje liste parcijalno znaci da se obrnu prvih k elemenata, pa drugih k, i tako dalje. Ukoliko je poslednjih m elemenata manje od k, tada ne treba vrsiti obrtanje poslednjih m elemenata.
Deklaracija funckije: void reverse(Node** head, int k).
Primer – input: 3->4->1->8->2->5->9->6, k = 3, output: 1->4->3->5->2->8->9->6. Dakle, kada obrnemo prva tri elementa dobijemo 1->4->3, zatim obrnemo druga tri elementa, pa dobijemo 5->2->8, a poslednja 2 ne obrnemo jer je 2 < 3.
2. Data su dva stringa u rasponu od A-Z, treba proveriti da li su anagrami. Dva stringa su anagrami ukoliko su sastavljeni od istih karaktera, ali u drugacijem redosledu. Pri tome, u prvom stringu moze da se nadje specijalan karakter predstavljen znakom @. Specijaln karakter menja bilo koji drugi karakter.
Deklaracija: bool areAnagram(const char* s1, const char* s2)
Primeri:
input: s1=ABAB, s2=BABA, output: true
input: s1=A@A@, s2=BAAC, output: true
input: s1=ACA, s2=ACAB output: false
3. Dato je binarno stablo. Potrebno je vratiti broj koji govori koliko se cvorova nalazi izmedju dva najudaljenija lista u stablu.
Deklaracija: int getDistance(Node* root)
4. Matematicki zadatak. Bili su krugovi i neka formula. Ne znam sta je trebalo uraditi.
U mom slucaju se ispostavilo da su tri zadatka dovoljna za prolaz. Prvi krug je jedino vazan za prolaz u drugi, zaposlenje zavisi iskljucivo od toga kako ste se pokazali u drugom krugu.
Toliko od mene, nadam se da sam pomogao.
Pozdrav,
Nemanja
Za 15ak minuta treba da krenem na intervju i pade mi na pamet da nisam postavio test, pa evo ga:
1. Data je jednostruko ulancana lista celih brojeva. Listu treba sortirati tako da prvo idu brojevi deljivi sa 3, pa parni pa neparni. Poredak samih elemenata nije bitan. Uraditi uz konacan broj dodatnih promenljivih.
2. Neka je data ,,soba” dimenzija MxN. Soba ima zidove (na obodima). Na zidovima se nalaze prozori, a u sobi stubovi. Sa ulaza (pomocu prilozene funkcije) citaju se po dva broja. Prva dva su m,n, druga dva su broj prozora i broj stubova, w,p. Nakon toga su w puta date koordiante prozora, pa p puta koordinate stubova. Potrebno je izracunati koliko osvetljenih kockica ima u sobi. Svetlo ide od prozora do suprotnog zida, ili do stuba, ako se on na tom putu nalazi.
3. Osmisliti sistem koji treba da realizuje sledece operacije sa stringovima: Zadat je originalni string, npr. abbab, kao i stringTemplate, npr. ab?a?. Potrebno je realizovati sledece funkcije:
initialize-inicijalizuje ceo sistem
print-stampa trenutnu rec
reset-resetuje sistem na pocetno stanje
i, dve funkcije koje su sustina:
forward – pomera trenutni string za jedan karakter unapred. Kako?
originalni string = abbab
templateString = ab?a?
Treba uzeti karakter na mestu prvog ,,?” (wildcard) i pomeriti ga po ascii tabeli za +1. Dakle, od pocetka, posle tri funkcije forward imali bismo situaciju
abbac
abbad
abbae
itd.
kada se obrne ceo krug na mestu tog wildcarda, sto znaci ako je trenutni string abbaa, pa uradimo ponovo forward, treba podici i taj karakter, ali i sledeci wildcard, dakle nakon abbaa ide abcab. Funkcija vraca bool, gde se true vraca u svakom slucaju osim ako se doslo do kraja, dakle ako je i poslednji wildcard dosao do a – ababa.
druga funkcija je bila backward, i treba da radi po istom principu ali unazad.
Sve sto je dato su duzina stringa, originalni string i template, na vama je da osmislite kako funkcionise.
4. Bilo je nesto sa quadtree, nisam ga uradio niti previse shvatio.
Nadam se da je bilo od pomoci :)
Pozdrav
Pozdrav ljudi.
Vasi komentari su mi pomogli,prosao sam test.
Evo su zadaci:
1. U stringu koji sadrzi samo brojeve i razmake naci najduzi broj(ne mora da staje ni u jedan tip int,long,…). Vratiti indeks i duzinu. Ukoliko ih ima vise,vratiti prvo pojavljivanje.
2. Data je matrica polja i matrica figure koja pada (sadrzi samo 0 i 1). U sustini tetris. Dat je indeks u matrici polja figure koji predstavlja gornji levi ugao figure. Uklopiti pravilno figuru u polje i izracunati broj redova koji su popunjeni( gde su sve jedinice).
3. Data je jednostruko povezana lista. Izbaciti minimalan broj elemenata tako da rezultujuca lista bude cik cak. Cik cak u smislu a1a3…
Ili
a1>a2<a3…
4. Naci najduzi put izmedju dva cvora na najvecoj dubini u datom stablu. Znaci ako ima vise cvorova na najvecoj dubini,vratiti maksimalno rastojanje.
Pozdrav
Evo zadataka sa testa iz Novembra 2018
1. Data je jednostruko ulancana lista celih brojeva. Sortirati listu tako da prvo idu brojevi deljivi sa 3, pa parni brojevi i na kraju neparni.
Primer 1-3-4-2-6-8 posle sortiranja ce biti 3-6-4-2-8-1
2. Dat je niz karaktera koji cine cifre. Napisati funkciju koja zamenom mesta dve cifre daje najmanji veci broj od zadatog ili ne radi nista ako to nije moguce dobiti. Na primer za broj 27563 najmanji veci broj je 27653, a za broj 321 se ne moze zamenom mesta cifara dobiri takav broj.
3. Dato je stablo definisano kao
struct node{
struct node*left;
struct node *right;
struct node *parent;
int data;
};
Svaki cvor ima dva deteta (levo i desno) i pokavac na roditelja (sem korena stabla koji to nema). Listovi stabla nose oznaku B (0) ili W (1) za black i white. Data je duz koja je podeljena na segmente koji su obojeni u belo ili crno u zavinosti od boje koja se nalazi u listu stabla.
Primer jednog stabla i duzi cije segmentisanje je dato tim stablom:
O
/ \
/ \
O O
/ \ / \
O O O O
| | | / \
B W W O O
| |
B W
Duz: | _ _ | _ _ | _ _ | _ | _ |
B W W B W
Znaci duz se sastoji od ukupno 8 segmenata (crtica predstavlja jedan segmenat), a redosled i duzina bojenja prati pojavljivanje listova.
Potrebno je naci najduzi niz belih segmenata (u ovom slucaju je to 4 (2+2).
4.Nisam zapamtila tacno kako glasi, ali nesto nalik na tetris. Data je matrica polja i matrica figure koja pada i treba je uklopiti u polje.
Ako se neko seca 4. neka dopuni.
Pozdrav.
Pozdrav ljudi, evo reko da ostavim zadatke ovde, mozda nekom bude od pomoci :D
Pre svega jako bitna napomena, NISU nam dozvoljavali bilo kakav vid upotrebe STL-a, sto je otezavajuci faktor, dakle radite sa char* kada imate stringove i slicno, znaci najobicniji C. Kod mozete pisati kako hocete ali su preporucili C, ili eventualno C++. Takodje, vreme izrade je 3 SATA, sto je meni bilo iznenadjujuce jer sam ocekivao 4 sata, tako da morate malo brze da radite.
1. Dat je niz karaktera (char*) koji u sebi ima zagrade, na primer “abc(de)”. Neophodno je vratiti string BEZ zagrada, a pritom sve stvari unutar zagrada se obrcu, dakle u ovom slucaju “abc(de)” postaje “abced”. Ukoliko imate duple zagrade, slova ostaju nepromenjena, znaci “a(bc(de))” daje “acbde”.
2. Data je Jednostruko spregnuta lista, neophodno je utvrditi da li je “specijalna”, a specijalna je ako je sacinjavaju isti brojevi kada se gledaju parna mesta od napred, i neparna mesta od nazad. Primer specijalne liste:
5 -> 8 -> 2 -> 2 -> 8 -> 5. Otezavajuci faktor je bila unapred STATICNA upotreba memorije, dakle nemate mogucnost dinamickog niza ili necega. Takodje mislim da sabiranje nije moglo da se koristi, jer biste primera radi, za 7 2 i 8 1 dobili isto resenje, a nije isto.
3. Igrarija sa WxH matricom, dat je vodopad i od gore (logicno) pada voda. Na putu do dole se nalaze stene, koje su u matrici oznacene sa ‘R’, tamo gde nema stene stoji ‘O’. Kada voda udari u stenu, tok se razdvoji na 2 dela. Ukoliko je ceo red popunjen stenama, dolazi do zakrcenja i nista ne stize do dna. Funkcija treba da vraca Float array, u kom se nalaze jacine pojedinacnih tokova za svaku kolonu. Na pocetku svaki tok je 1, kada udari u stenu raspolovi se na 0.5 i 0.5 i oba idu u svoju stranu. Ukoliko je jedna strana blokirana, 2* 0.5 odlazi na slobodnu stranu.
4. Po meni apsolutno najtezi zadatak, dato je Binarno stablo, i prototip funkcije (ovo je problematicno) int* traverse(Node* head). Neophodno je vratiti niz intedzera koji ispisuje vrednosti drveta CounterClockwise. Dakle pocnete od donjeg levog pa idete niz donje grane, pa kad prodjete to idete na vrh,
pa onda n-1 red dole pa nazad na drugi itd. Funkcija koja ide u rekurziju je samo int* foo(Node* head), nemate pravo na vise argumenata, a imate samo 45min u proseku da smislite i realizujete ideju.
Srecno svima, ako sam negde pogresio, molim vas ispravite me. Pozdrav :D
Evo testa koji je bio odrzan u Martu 2019. Na testu nisu smele da se koriste nikakve biblioteke. Ako je jos neko bio na testu, neka slobodno ispravi ako sam nesto pogresila ili zaboravila :D
1. Napisati funckiju koja vraca rezultat (int) izraza koji je prosledjen kao niz karaktera (char*). Primer: “324 + 5 * 7 * 2 + 45 + 3 * 2”. Olaksavajuca okolnost je sto se u izrazu mogu naci samo operacije sabiranja i mnozenja. Takodje, ne postoje zagrade u izrazu. U sustini mogu se naci samo cifre, + i *. Koliko se secam izmedju svakog broja i operacije se nalazio razmak.
2. Data je dvostruko ulancana lista. Napisati funkciju koja kao ulaz dobija pokazivac na prvi element (Elem* head) i modifikuje listu na sledeci nacin: element(1) – element(n) – element(2) – element(n-1) – element(3) – element(n-2) itd… Izlaz funkcije je pokazivac na prvi element liste (Elem* head).
Primer:
Ulazna lista: 1 2 3 4 5
Izlazna lista: 1 5 2 4 3
Ne mogu da se setim da li je lista pored ovoga trebala da bude i cirkularna (da next pointer elementa 3 pokazuje na element 1, i prev pointer elementa 1 pokazuje na element 3). Ako se neko seca sta je bio slucaj, neka dopuni. U svakom slucaju mala je modifikacija :)
3. Napisati funkciju koja vraca najduzi put izmedju dva cvora u stablu (broj cvorova na putu izmedju dva najudaljenija cvora). Ulaz funkcije je pokazivac na root stabla (Node* root), a izlaz ceo broj (int).
4. Dat je koordinatni sistem i oznacena su cetiri kvadranta. Napisati funkciju koja kao ulaz dobija koordinate dve tacke (float x1, float y1, float x2, float y2) koje predstavljaju krajnje tacke jedne duzi, i vraca izlaz (int) koji daje informaciju kroz koje kvadrante duz prolazi. Izlaz je tipa integer i dobija se na sledeci nacin: Imamo 4-bitni binarni broj. Ukoliko duz prolazi kroz prvi kvadrant, na nultoj poziciji je 1 (u suprotnom 0). Ukoliko duz prolazi kroz drugi kvadrant, na prvoj poziciji je 1 (u suprotnom 0) itd… Na primer ukoliko duz prolazi kroz prvi, drugi i treci kvadrant binarni broj ce biti 0111, pa ce izlaz funcije biti 7.
SRECNO! ^___^