Zkouška 25.5.2009

Zkoušel Töpfer, zadání zabralo asi půl hodiny, na práci byly 2 hodiny času.

Zadání: Obchodování na burze
Na vstupu data o požadovaných transakcích, kde jeden záznam obsahuje:
ID makléře (10 znaků)
ID klienta (10 znaků)
ISIN akcie (12 znaků)
název akcie (20 znaků)
typ (1 znak, P jako prodej nebo N jako nákup)
limitní cena (číslo na 2 desetinná místa, v případě prodeje minimální cena, v případě nákupu maximální cena)
počet kusů (longint, počet kusů které je maximálně možno prodat nebo koupit)

Cílem programu je pro každý druh akcií (pro každý ISIN kód) najít cenu, při které se zobchoduje největší počet kusů. ISIN je unikátní kód druhu akcie, stejně tak název je unikátní. Výstupem sada záznamů, které obsahují:
ISIN akce
název akcie
určená cena
počet kusů, které ze za tuto cenu zobchodují

Omezení:
maximálně druhů akcií ... 3 000
maximálně požadavků ... 100 000 000
maximálně makléřů ... 10 000
maximálně klientů ... 10 000 000
cena akcií od 0,01 do 43 000 Kč
dostupná paměť RAM ... 1 MB
dostupná paměť na disku ... neomezeně

Požadavky je možné splnit částečně (někdo chce koupit 10 kusů, ale je k dispozici jen 5, pak se provede obchod na 5 akcií).

mne to pripada take ze cely cas do nas cpu grafove algoritmy, kdejake zoznamy a stromy a tu to slo len cez subory...
ale nebolo to ak take tazke, hlavne je pochopit o co tam ide. po vysvetleni zadania malo este dost vela ludi otazky

Řešil jsem takto:

Vstup si nejprve rozkouskuju do souborů podle ISINu (vnějším tříděním). Jednotlivé soubory pak seřadím vzestupně podle ceny (a případně ještě podle typu požadavku N/P). Přitom si ISINy a názvy akcií uložím do paměti (třeba jako pole) a toto pole seřadím vzestupně podle názvu. Pak s každým souborem (v pořadí v jakém mám seznam ISINů) udělám toto:

Budu mít dva čítače, jeden na prodeje, druhý na nákupy. Nejprve si soubor celý jednou projdu a sečtu počty kusů všechny nákupů. Nastavím čítač nákupů na tuto hodnotu. Pak procházím postupně všechny záznamy v souboru (jsou seřazené podle ceny vzestupně) a když najdu prodej, přičtu počet kusů k čítači prodejů, když najdu nákup odečtu počet kusů od čítače nákupů. Co je důležité je nejprve počítat prodeje a až pak nákupy. A v každém bodě je podívám na menší z těchto dvou čítačů. To určuje kolik je možné zobchodovat akcií při aktuální ceně. Pro každou cenu (a případně pro každé rozmezí mezi dvěma cenami) se podívám na dosavadní maximální možnost zobchodování akcií a kdyžtak vylepším. Na konci mám výsledek (a ještě si pochopitelně při nalezení lepšího čísla zapamatuji cenu).

Složitost je O(n.log n) kvůli vnějšímu třídění, procházení je pak lineární. Na ústní mi Holan pověděl, že je to v pořádku, ještě se mě zeptal, co jsou virtuální metody a kdy se vytváří ukazatel na tabulku virtuálních metod. Obojí jsem věděl, takže za 1.

Mě se na ústní ptal na dynamiku a pak jsem předváděla postup jak co nejlépe uzávorkovat n matic při násobení tak, aby se provedlo co nejméně násobení.

Ta pisemna mi prisla celkem jednoducha, u ustni se me Holan ptal na haldu, na virtualni metody a jejich tabulku v C#.

Na ústní části se mě Topfer ptal na vyhodnocování aritmetických výrazů a na dolní odhad složitosti třídění založeném na porovnávání.