Jane Street je kvantitativna investicijska tvrtka aktivna na više od 200 lokacija u 45 zemalja svijeta. Kao pružatelj likvidnosti i stvaratelj tržišta, pomaže u kreiranju okosnice globalnih tržišta. Njihov pristup temelji se na tehnologiji i kvantitativnoj analizi, ali uspjeh pokreću njihovi ljudi.
Posjeti blog i budi u toku s timovima za softversko inženjerstvo i računalnu tehnologiju Jane Street-a. Također, redovito objavljuju podcast pod nazivom Signals and Threads, a ovdje možeš pogledati epizodu za studeni na temu “Što je operativni sustav? (What is an Operating System)”.
Kako izgleda intervju za poziciju softverskog inženjera u Jane Street-u
Razmišljaš o prijavi za radno mjesto softverskog inženjera u Jane Street-u ili već imaš zakazan telefonski intervju, ali ne znaš što očekivati? U nastavku teksta pročitaj primjer telefonskog intervjua.
Dobit ćeš uvid u to kako izgleda tipičan telefonski intervju za posao u Jane Street-u. Pogledaj i zadatak koji Streetersi nazivaju “Memo” te su ga nekada redovito postavljali kandidatima (naravno, to više nije praksa, tako da ne moraš učiti išta napamet s ove stranice). Prema tome, ovaj tekst je zamišljen kao posebna analiza slučaja. Pročitaj blog i saznaj što Jane Street traži od kandidata.
Početak
Kako bi mogli zajedno raditi na testnom zadatku, Jane Street koristi dijeljeni mrežni program za uređivanje za koji će ti poslati poveznicu za korištenje (prije ili tijekom intervjua).
Od tebe se očekuje da napišeš kod u stvarnom programskom jeziku tijekom intervjua, a ne pseudokod. Možeš koristiti bilo koji programski jezik koji želiš, ali koristi onaj s kojim se najbolje snalaziš i koji će ti omogućiti da riješiš problem na najbolji način (smiješ ga promijeniti dok istražuješ problem). Upoznaj se s osnovnim strukturama podataka i API-jima jezika kojeg odabereš.
Nema dodatnih bodova za korištenje funkcionalnih jezika kao što je OCaml koji je korišten u ovom primjeru. Cilj je vidjeti kandidate u najboljem izdanju stoga koristi jezik koji ti najviše odgovara. Ako OCaml nije programski jezik s kojim najbolje barataš, nemoj ga koristiti.
Ako tijekom intervjua shvatiš da ti je zadatak poznat, reci kako bi ti drugi zadatak bio dodijeljen. Kao što ćeš vidjeti u nastavku ovog teksta, poznavanje zadatka unaprijed uvelike umanjuje ono što Jane Street može naučiti o tebi.
Prvi dio – Osnovno kodiranje
Znaš li za pojam memoizacija (engl. memorization)? Možeš li temeljito opisati na što se odnosi? Ne brini se ako ne znaš za taj pojam, slijedi objašnjenje (dobar uvod nalazi se na Wikipediji).
Zamislimo da postoji funkcija f tipa int -> int čiji izlaz ovisi samo o ulazu. Izračunati f veoma je zahtjevno. Cilj je da napišeš memoiziranu varijantu te funkcije, odnosno drugu funkciju g istog tipa koja daje iste vrijednosti – g(x) = f(x) za svaki x –, ali koja vrši skupi izračun samo jednom za svaku ulaznu vrijednost. Tipično prvo rješenje koje je traženo u ovoj fazi koristi hash tablicu za pohranu dobivenih rezultata. Moguće rješenje u OCaml moglo bi biti:
(Kao što je ranije navedeno, od tebe se ne zahtjeva da pišeš u OCaml-u, a možda ćeš također prigovoriti da se ovime vrši test-and-set bez zaključavanja te da zbog toga to nikako ne može biti thread-safe. Odlično primijećeno! Za ovaj zadatak zanemari ponovni ulaz kako bi fokus ostao na osnovnoj ideji.)
Neovisno o tome za koji API ili strukturu podataka se odlučiš za svoje rješenje: potrebno je opisati kako rade i koja je složenost raznih operacija.
Drugi dio – Obrazloženje i poboljšanje tvog koda
Možeš li se sjetiti bilo kakvih problema na koje se može naići pri korištenju funkcije iz prvog dijela? Na primjer, zamisli da se pokrene tvoja funkcija i aplikacija radi znatno lošije nego prije. Upravo suprotno od onoga što bi memoizacija trebala učiniti! Vidiš li u čemu bi mogao biti problem?
Veliki problem je korištenje memorije. Aplikacija može pozvati f s puno različitih ulaza i svaki će rezultat biti zauvijek pohranjen u hash tablici – curenje memorije! Možeš li smisliti neke ideje za poboljšanje?
Razuman pristup kontroli korištenja memorije je ograničiti veličinu hash tablice i izbaciti stvari iz nje pomoću FIFO metode. Koje negativne strane FIFO ima u odnosu na druge strategije izbacivanja? Kako modificirati svoju memo funkciju da se implementirao FIFO? Cilj je O(1) složenost prilikom izbacivanja iz predmemorije.
Postoji nekoliko načina da se to postigne. Dobro rješenje problema će držati zaseban red: kada dodaješ novi rezultat u svoju hash tablicu, ako veličina naraste preko ograničenja, onda izađi iz reda i ukloni taj element iz hash tablice.
Osim sposobnosti da napišeš kod koji to radi, Streetersi gledaju kako iznosiš svoje razmišljanje o problemu i ideje kako poboljšati kod. Ne očekuje se da se svaki kandidat odmah baci na rješenje O(1), ali ih zanima proces razgovora kroz ovaj problem i što možeš smisliti.
Treći dio – Idemo dalje
Kao što vjerojatno znaš, metoda FIFO može biti veoma neučinkovita u nekim slučajevima. Recimo da umjesto nje koristiš strategiju LRU (least recently used). I dalje je cilj da primjena bude što je moguće više učinkovita. Kako to implementirati?
Ponovno, postoji više načina da se to učini. Najjednostavnije rješenje pohranjuje vremenske oznake sa svakom vrijednošću u hash tablicu i linearno skenira kroz tablicu prilikom izbacivanja. To bi bio O(n). Moguće je poboljšati na O(log n) koristeći min-hrpu ili čak na O(1) koristeći dvostruko povezanu listu.
Napomena: implementacija najučinkovitijeg rješenja – Jedan način da se postigne O(1) jest da se zadrži dvostruko povezana lista i napravi da vrijednosti u hash tablici upućuju na elemente u toj listi. Zatim kada se traži predmemorirana vrijednost u hash tablici, možeš je izrezati iz njezine trenutne pozicije na listi i staviti je na vrh u O(1). Zadržava se zaseban pokazivač na dno dvostruko povezane liste za izbacivanje u O(1).
Malo kandidata se odmah sjeti dvostruko povezane liste, zato se ne brini ako ti nije odmah palo na pamet. Iako ćeš možda morati primijeniti dijelove svog rješenja, svrha ovog dijela je rasprava i testiranje tvojih ideja za poboljšanje kompleksnosti. Imat ćeš vodstvo do prave razine apstrakcije, tako da se ne moraš previše brinuti o tome koje detalje ćeš uključiti.
Za ovaj zadatak nude se i razna druga proširenja koja omogućuju da radiš koliko ti vrijeme dozvoli.
Što Jane Street traži od tebe
Ponovno, za dobar uvid pogledaj ovu objavu.
Tijekom intervjua Streetersi nastoje zajedničkim rješavanjem problema procijeniti koliko ćeš se dobro uklopiti u radno okruženje. To znači da je putovanje kroz intervju puno važnije od slike rješenja na kraju razgovora. Više ih zanima vidjeti kako pristupaš teškom problemu nego samo možeš li doći do rješenja.
Kao konkretan primjer, moguće je da će preferirati kandidata koji je napisao pažljiv i jasan kod, dobro komunicirao i imao dobre uvide i ideje na tom putu, ali nije prošao tako daleko kroz problem u usporedbi s drugim kandidatom koji je odmah riješio svaki dio, ali je bio nemaran i bilo ga je teško pratiti.
Zbog toga je nemoguće postaviti precizan set zahtjeva koji se moraju ispuniti tijekom intervjua, ali ipak, ovo je nekoliko okvirnih smjernica:
Svaki uspješan kandidat trebao bi doći do rješenja bez bugova za prvi dio relativno brzo. Ako ti nešto iz prvog djela nije poznato, odgodi svoju prijavu i uzmi više vremena za pripremu.
Većina kandidata koji prođu u potpunosti dovrše i drugi dio za vrijeme intervjua. Jaki kandidati dovrše treći dio s kompletnim rješenjem, ali ako ga ne dovršiš to ne znači da će te Jane Street odbiti! Kao što je ranije navedeno, najvažnije je ono što se događa tijekom intervjua, a ne krajnji rezultat.
Dijeljenje zadatka nakon intervjua
Jane Street želi vidjeti na koji način pristupaš zahtjevnom problemu i s tobom proći kroz proces pronalaženja rješenja. Ako već unaprijed znaš zadatak (tako što je dostupan na internetu ili iz razgovora s prijateljima koji su se ranije prijavili), to će umanjiti učinkovitost intervjua: tada će moći testirati samo možeš li napisati kod za problem koji već razumješ i riješen je, što je maleni dio onoga što žele saznati. Na primjer, nakon pročitanog ovog članka, Streetersi ne bi mnogo saznali ako bi zadani zadatak bio “Memo“!
Zbog toga zadatak iz intervjua ne dijeli ni s kim drugim, osobno ili online.
Jane Street se nastoji javiti kandidatima vezano za ishod intervjua unutar tjedan dana. Tijekom većih gužvi to može potrajati malo duže, ali savjetuju da ih kontaktiraš ako se ne jave 10ak dana.
Ako je intervju dobro prošao, pozvat će te da dođeš u jedan od ureda (New York, London ili Hong Kong) na jednodnevni intervju. Oni se odvijaju na isti način kao i telefonski razgovor – sva su pitanja tehnička.
Želiš se prijaviti?
Ako se osjećaš spremno za prijavu, onda slijedi poveznicu. Proces prijave je jednostavan – sve što ti je potrebno je životopis. Ako već imaš ponudu druge tvrtke i brine te termin razgovora, javi na početku procesa zapošljavanja. Također možeš pročitati razmišljanja Jane Street-a o kratkotrajnim ponudama (engl. exploding offers). To je nešto što trenutno ne rade, ali mnoge tvrtke koriste kao alat pri zapošljavanju.
Prijavi se i postani dio Jane Street-a!
