# 30.5. 2016 - Holan - Burza

<{ForumPost(poster="hlupaco", timestamp=2016-06-01 16:13:07)}>
Opět Burza  
  
[10.6.2013](/NPRG031/Zkouska%20Holan%2010.6.2013)  
  
S komentářem anakondy:  
"souboru Holan dovoloval maximalne tolik, jako ISINu, tedy klidne i 3000. Sam jsem to tak napsal a u ustni casti mne vysvetlil, ze na to stacil soubor jeden, ale zadne problemy s tim nemel:). Nakonec za 1"  
nesouhlasím, možná mu byl student sympatický ale za tohle by mě poslal pryč dřív než bych to vůbec stačil doříct. S ukládáním do pole problém nebyl, na to ten 1 MB stačil. (ve smyslu array o 3000 prvcích)  
vlastně i na začátku zadání explicitně zmínil že udělat si jeden soubor pro každý ISIN je vyloženě zakázané  
  
Z Burzy jsem dostal 2 a nejspíš jen proto, že jsem mu v jednom bodě řekl, že předpokládám že umím soubor číst odzadu xD  
Vypadl jsem ale potom na teorii, neuměl jsem setřídit soubor :-( pokud má někdo stejný problém:  
[https://en.wikipedia.org/wiki/External_sorting](https://en.wikipedia.org/wiki/External_sorting)  
Tu první část, kde načítáte 100 MB do paměti, tu setřídíte a následně sléváte jsem mu na místě vymyslel ale zakázal mi jí, prý by to nebylo dost rychlé.  
Co chce je něco obdobného, bylo to prej jednou na přednášce ZS - na začátku je v souboru N 1-prvkových posloupností, soubor otevřu 2krát pro čtení a vždy slévám dvojice za sebou do nového souboru - mám soubor s N/2 2-prvkovými setříděnými posloupnostmi, opakuju...  
  
Zajímavá informace ke zkoušce obecně by mohla být, že Holan ten papír co odevzdáte vůbec nečte. Stačí tam kreslit jen schematický obrázky a hesla pro vás a potom ústně mu v podstatě celej algoritmus stejně přeřikáte znova, s pomocí toho papíru.  
  
Co ho už zajímalo víc byl pseudokód pro hlavní část algoritmu - v tomhle případě vybírání nejlepšího kursu akcie - kterej dost pitval a zkoumal i krajní případy, co se stane při rovnosti atd. S tim si teda na papíře určitě vyhrajte :-)  
  
Složitosti a Očka vůbec neřeší, pokud to je aspoň v základu dobře a nedějou se tam věci typu Nkrát otevři soubor.  
  
Řešení je úvodní soubor setřídit (hehe) podle ISINů, pak po blocích ISINů dělit na nákup/prodej... Tělo algoritmu už neni tak složitý když si dobře soubory připravíte. Určitě to jde s méně než deseti, pokud máte koule tak možná i pěti soubory (otevřenými v jednom okamžiku).
<{/ForumPost}>

<{ForumPost(poster="Samuel", timestamp=2016-06-01 20:02:05)}>
No tak ja som z burzy dostal za 1 a tu mate moje rady:  
  
1. Nakreslit obrazok!! Holan ma obrazky rad. Je potom vidno co presne algoritmus robi.  
2. Napisat vsetky dolezite casti! Tzn. nepredpokladajte, ze k vam bude zhovievavy, ak mu poviete nieco, co nemate napisane na papieri. Mozete doplnit detaily ktore ste nestihli napisat ale v podstate musi byt jasne, ako vase riesenie funguje.  
3. V ulohe burza mate malo pamate. Tzn. nepocitajte s tym, ze si loadnete vsetky ISINy do pama a tak podobne. Odporucam pocitat s konstantnym mnozstvom pamate, potom nebude problem a vojdete sa aj do 1 kb.  
4. Pseudokod: Minimalne mne velmi pomohol. Snazil som sa mu vysvetlit, ako funguje pocitnie kurzu, ale oc mi to neslo, tak som otocil papier na stranu s pseudokodom a Holan sa velmi potesil. Kede pseudokod bol jasne a prehladne napisany, tak mi moj pos bez rypavych otazok uznal a napisal mi jednotku.  
5. Ak nechape nejakej casti vasho riesenia, tak mu to nakreslite/napiste este raz a zrozumitelnejsie.  
  
Co sa tyka citania z disku, dajte si na to pozor. Ziadne citanie od zadu, otvaranie desiatich suborov a podobne. Snazte sa prist na riesenie, ktore vsetko vypocita naraz. Konkretne ja som si na zaciatku roztriedil subor podla ISINov a potom som zacal riesit samotne ISINy. Vytvoril som dva subory, jeden na nakup, jeden na predaj, roztriedil som ich zostupne podla ceny a prechadzal oba naraz. Najprv subor Prejad urcil kurz a potom som v subore predaj vypocital, kolko akcii sa preda pri danej cene. Tak som prechadzal oba subory, az kym sa pocet predanzch akcii zacal znizovat. Potom uz nema zmysel pocitat dalej a rovno mozete vypisa vysledok a pokracoval dalsim ISINom. Dokopy som mal naraz otvorene max 2 subory s tym, ze je to mozne vyriesit aj s jednym. Staci nakupy a predaje dat dokopy, roztriedit zostupne a... no,  si uz rozmyslite sami.  
  
Tak... Tolko k pisomnej casti.  
  
Ak mu je jasne,ako vas algoritmus funguje, tak sa vas opyta este nejaku teoreticku otazku. Konkretne u mna sa pytal na hladanie medianu.   
  
Na zaciatku som navrhol riesenie v O(NlongN), kde najprv roztriedite subor a potom vezmete prostrey prvok. Potom som spomenul Quicklect, co je alg. ktory hlada k-ty najvacsi prvok v linearnom case (priemerne).   
Nakoniec sa maopyal, ako by som hladal napr. 1000 najvacsi prvok. Prisiel som s riesenim, ktore pouzivalo haldu, v ktorej sa udrzovalo 1000 najmensich prvkov. Hladanie tohto prvku by potom bolo v linearnom case, pretoze operacie v halde (insert a extract max) su sice logaritmicke, ale logaritmus 1000 je rovny 10 (čo som označil akokonštantu, ktora sa schova do thety) a navyse sa v nahodne usporiadanej postupnosti nebude do haldy insertovat tak casto :)  
  
No.. a poto uz mi dal za jedna a stastne som isiel prec.  
  
Tak... vela stastia pri skuske, snad vam moje rady nejak pomozu. Nezabudnite hlavne v tej pisomnej casti nakreslit pekny obrazok a pseudokod. Na nom sa vase riesenie vysvetluje lepsie.
<{/ForumPost}>