Nenad Božidarević

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)

Microsoft Development Center SerbiaPrvi 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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).
  5. 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.
  6. Zadatak iz verovatnoće (obična i uslovna). Jednostavan, ali su jednačine nešto duže.
  7. 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.

Komentari (75)

ТоМЦаа 6 years ago

Добар текст, баш фино што си ово искуство поделио са људима. Није ми јасан овај 3. задатак, али претпостављам да га ни ти ниси добро разумео да би могао да га разјасниш :)

Знам да ти ово није било проблем, а имајући у виду да си бистар, жељно ишчекујем твој извештај са интервјуа ;) Срећно!

Ах, да, срећно и у Шпанији :D

Odgovori

Nenad Božidarević 6 years ago

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…

Odgovori

asd 3 years ago

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

Odgovori

jovan 6 years ago

aj kad si faca daj nam i resenja

Odgovori

Nenad Božidarević 6 years ago

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.

Odgovori

Zibrrr 6 years ago

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 :)

Odgovori

Nenad Božidarević 6 years ago

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…

Odgovori

Igor 5 years ago

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?

Odgovori

Nenad Božidarević 5 years ago

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.

Odgovori

Miljana 5 years ago

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!

Odgovori

Nenad Božidarević 5 years ago

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:

  • Jednostruka petlja je složenosti N
  • Dvostruka petlja je složenosti N2
  • Sortiranje je složenosti NlogN
  • Binarna pretraja je složenosti logN
  • itd.

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

Odgovori

Igor 5 years ago

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);

Odgovori

Nenad Božidarević 5 years ago

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.

Odgovori

Aleksandar 5 years ago

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)?

Odgovori

Aleksandar 5 years ago

Ha, izvini na spam-u shvatio sam na sta mislis, pogresno sam procitao neke stvari :)

Odgovori

Nenad Božidarević 5 years ago

Jesi li odgovorio sâm sebi na sva tri pitanja, ili je neko i dalje aktuelno? :)

Odgovori

Aleksandar 5 years ago

Odgovorio sam samo na prvo :) druga dva me I dalje interesuju :)

Odgovori

Nenad Božidarević 5 years ago

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).

Odgovori

Igor 5 years ago

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

Odgovori

Nenad Božidarević 5 years ago

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.

Odgovori

Zadaci sa testiranja April 2012 5 years ago

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.

Odgovori

Nenad Božidarević 5 years ago

Hvala! Koristiće nekome :) Jako zanimljivi zadaci, ali nisu mnogo teški…

Odgovori

Petar Veličković 4 years ago

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

Odgovori

Nikola Zecevic 4 years ago

Jel vec bilo testiranje? Izgleda da sam se kasno prijavio :(

Odgovori

Nenad Božidarević 4 years ago

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.

Odgovori

Nikola Zecevic 4 years ago

Hvala :)
Poslao sam im, pa videcemo… :)

Odgovori

Maja Pavlovic 4 years ago

Kako se resava 7. zadatak iz aprila 2012? Hvala unapred…

Odgovori

Nenad Božidarević 4 years ago

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

Odgovori

Dragan 4 years ago

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#?

Odgovori

Nenad Božidarević 4 years ago

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.

Odgovori

Perica 4 years ago

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!

Odgovori

Nenad Božidarević 4 years ago

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.

Odgovori

Perica 4 years ago

Hvala jos jednom na odgovoru! Prihvatio sam poziv na test pa cemo videti sta ce biti…

Odgovori

Ognjen 2 years ago

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.

Odgovori

Nenad Božidarević 2 years ago

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.

Vucko 4 years ago

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.

Odgovori

Sofija 3 years ago

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

Odgovori

Nenad Božidarević 3 years ago

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…

Odgovori

Petar Novakovic 3 years ago

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

Odgovori

Nenad Božidarević 2 years ago

Jeste prošlo pet meseci, ali nikad nije kasno… Opisao sam rešenje zadatka u novom tekstu:
http://www.bozidarevic.com/2015/02/parsiranje-bulovih-izraza/

Odgovori

Marko Ilincic 3 years ago

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.

Odgovori

Marko 2 years ago

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.

Odgovori

Test januar 2016. 1 year ago

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.

Odgovori

Dev 6 months ago

Koja je ideja za 3. zadatak?

Odgovori

C 5 months ago

Ima li neko bolju ideju za 3 zadatak od n*logn slozenosti?
Pozz

Odgovori

Nenad Božidarević 5 months ago

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?

Odgovori

April 2016. 1 year ago

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.

Odgovori

Avgust 2016 11 months ago

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.

Odgovori

M 8 months ago

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!

Odgovori

Nenad Božidarević 7 months ago

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.

Odgovori

Tadija 10 months ago

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.

Odgovori

Jana 10 months ago

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.

Odgovori

Nenad Božidarević 10 months ago

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.

Odgovori

C 4 months ago

3 zadatak, Oktobar 2016? Koja je ideja kako da se uradi i u kojoj slozenosti? Ako neko zna moze pomoc?

Pozz

Odgovori

C 4 months ago

TACNIJE 2 ZADATAK ME ZANIMA< OVAJ SA STRINGOVIMA?

Pozz

Odgovori

Petar 8 months ago

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.

Odgovori

Decembar 2016. 7 months ago

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.

Odgovori

Decembar 2016. 7 months ago

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. :)

Odgovori

aca 7 months ago

Ako moze samo pojasnjenje za 3 zadatak, zar ukupno vreme za dati primer nije 34s? Po mojoj racunici?

Pozdrav, Aca.

Odgovori

a 7 months ago

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..

Odgovori

Override 7 months ago

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++.

Odgovori

Doggy 6 months ago

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.

Odgovori

Nenad Božidarević 6 months ago

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.

Odgovori

nenad 5 months ago

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

Odgovori

Nenad Božidarević 5 months ago

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.

Odgovori

Stefan 7 months ago

Da li se zadaci na testiranju rade isključivo u C-u?
Koji su termini za polaganje testa?

Pozdrav

Odgovori

Aco 7 months ago

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

Odgovori

Override 7 months ago

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.

Odgovori

Aco 7 months ago

Override hvala ..
Reci mi samo koji je to nivo poznavanja engleskog koliko tecno sve to treba da zvuci?
Koji jezik preporucujete?
Pozdrav, aco

Odgovori

Override 7 months ago

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

Miloš Rajković 2 months ago

Da li je dovoljno samo main metodu napisati ili mora čitava deklaracija i klase i sličnoga?

Odgovori

Nenad Božidarević 2 months ago

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.

Odgovori

Postavi komentar