Otázky na pohovoru

[Ivan Nový]

Mně kdysi dali pěknou úlohu:

Představ si, že máš soubor s logy, ve kterém jsou uloženy URL, která lidi navštívili. Jedno URL na jeden řádek. Ten soubor je obrovský, ani náhodou se nevejde do paměti. Různých URL je také velké množství, ani ty samotné se nevejdou do paměti.

Jak bys napsal program, co nejefektivnější, který by vypsal 5 nejčastějších URL? Ne napsat, ale vysvětlit. Vůbec jsme nebyli u PC.

To je docela složitá úloha, nečekali, že to dám z hlavy, ale dívali se jak přemýšlím a postupně mě vedli k výsledku.

Jedna z pozdějších nápověd bylo, že příkaz "sort | uniq -c | sort -nr | head -n 5" přesně kopíruje to řešení (a jak to ten sort s tak velkým souborem vlastně dělá?). Rozhodně nechtěli slyšet "strč to do databáze a udělej SELECT", protože v tom případě si ten člověk myslí, že databáze je nějaká magická krabička a nevidí za tím, jak na tuhle úlohu je neefektivní.

Ovšem nejefektivněji tu úlohu vyřešíte statisticky, náhodně vyberete určitý počet url, zlomek z celkového počtu a z nich vyberete 5 nejčastějších url. :-) 

[Reklama]

[me vakérav]

...(a jak to ten sort s tak velkým souborem vlastně dělá?)...

To zalezi jak je implementovanej, rek bych ze v dost pripadech ti ta ramka proste dojde .

Ne. Unixový sort je zrovna dělán tak, že RAMka nedojde (a o žádném jiném zjevně řeč není).

Jinak to samo muzes delat na disku jen to bude pomalejsi, pamet jako pamet ... nekam se to ale vejit musi.

Jasně, musí to být na disku, otázka je CO PŘESNĚ musí být na disku, aby to bylo furt ještě efektivní. Třeba alokovat paměť do aleluja a spoléhat na swap nebude efektivní vůbec.

Správná odpověď je:

• načíst tolik dat, kolik se mi vejde do paměti
• data seřadit
• (případně zkomprimovat) a zapsat na disk
• goto 1 pro další kousek dat, dokud něco zbývá
• vzít všechny ty uložené setříděné kousky dat a zmergovat je. Tedy postupně brát ten nejmenší prvek z nich (jo, to může být taky oříšek, pokud je kousků milion, ale kdyžtak se to může udělat rekurzivně) a dávat ho na výstup
• z výstupu udělat "uniq -c" (počítat, kolik tam je stejných prvků)
• výsledek analogicky seřadit podle velikosti
• vybrat prvních X výsledků, zbytek zahodit

BTW: Ja bych vazne chtel videt dneska firmu, ktera si dovoli pokladat podobne debilni otazky ktery tu sou zmineny, kdyz si muzou gratulovat, ze na ten pohovor dotycnej vubec prisel.

Podle mě je to výborná úloha na oddělení lidí typu „použijeme databázi“ a kteří nad problémem fakt přemýšlí. Pravda je, že ve většině firem ta databáze stačí. V tom tehdejším zaměstnání teda ale rozhodně nestačila, a právě proto vybrali tuhle úlohu.

[j]

....

Premianti? To je fakt smutný. I dement tohle dokáže odvodit: když je šance 20% na úspěch, tak je logicky šance na neúspěch 80%. U dvou pokusů tedy 0,8*0,8 = 64, čili 36% že se to povede.
A člověk nemusí umět 1 - (1-Sance na uspech)^pocet pokusu.

Fakt? Takze mi chces tvrdit, ze kdyz si milionkrat vsadim, ze mam prakticky jisty ze vyhraju?

[me vakérav]

....

Premianti? To je fakt smutný. I dement tohle dokáže odvodit: když je šance 20% na úspěch, tak je logicky šance na neúspěch 80%. U dvou pokusů tedy 0,8*0,8 = 64, čili 36% že se to povede.
A člověk nemusí umět 1 - (1-Sance na uspech)^pocet pokusu.

Fakt? Takze mi chces tvrdit, ze kdyz si milionkrat vsadim, ze mam prakticky jisty ze vyhraju?

Samozřejmě. Minimálně jednou vyhraješ s velmi vysokou pravděpodobností.

Otázka je, jestli alespoň jednou vyhraješ, ne jestli budeš celkově v zisku.

[Trader]

...(a jak to ten sort s tak velkým souborem vlastně dělá?)...

Ja bych vazne chtel videt dneska firmu, ktera si dovoli pokladat podobne debilni otazky ktery tu sou zmineny,

Google, Apple, Microsoft, Amazon neznáš?

[Reklama]

[gll]

BTW: Ja bych vazne chtel videt dneska firmu, ktera si dovoli pokladat podobne debilni otazky ktery tu sou zmineny, kdyz si muzou gratulovat, ze na ten pohovor dotycnej vubec prisel.

Podle mě je to výborná úloha na oddělení lidí typu „použijeme databázi“ a kteří nad problémem fakt přemýšlí. Pravda je, že ve většině firem ta databáze stačí. V tom tehdejším zaměstnání teda ale rozhodně nestačila, a právě proto vybrali tuhle úlohu.

Není to naopak? Sort stačí na jednoázové vyhledávání. Databázi použijete, když v těch datech hledáte opakovaně a nechcete řadit soubor pro každé hledání.

[gll]

Jedna z pozdějších nápověd bylo, že příkaz "sort | uniq -c | sort -nr | head -n 5" přesně kopíruje to řešení (a jak to ten sort s tak velkým souborem vlastně dělá?). Rozhodně nechtěli slyšet "strč to do databáze a udělej SELECT", protože v tom případě si ten člověk myslí, že databáze je nějaká magická krabička a nevidí za tím, jak na tuhle úlohu je neefektivní.

dost záleží na tom, jak vypadají vstupní data. Jestli se tam opakuje pár url, tak řazení není dobrý způsob. Lepší ty county ukládat do slovníku.

[anon]

...(a jak to ten sort s tak velkým souborem vlastně dělá?)...

Ja bych vazne chtel videt dneska firmu, ktera si dovoli pokladat podobne debilni otazky ktery tu sou zmineny,

Google, Apple, Microsoft, Amazon neznáš?

Takze takovy dinosauri, kde budes lopatit.

A ptaji se na nesmysly aby vypadali cool - to sedi.

[pepan]

...(a jak to ten sort s tak velkým souborem vlastně dělá?)...

Ja bych vazne chtel videt dneska firmu, ktera si dovoli pokladat podobne debilni otazky ktery tu sou zmineny,

Google, Apple, Microsoft, Amazon neznáš?

Takze takovy dinosauri, kde budes lopatit.

A ptaji se na nesmysly aby vypadali cool - to sedi.

+1

[L.]

dost záleží na tom, jak vypadají vstupní data. Jestli se tam opakuje pár url, tak řazení není dobrý způsob. Lepší ty county ukládat do slovníku.

V zadání bylo, že ani unikátní URL se nevejdou do paměti.

[grg]

Ne. Unixový sort je zrovna dělán tak, že RAMka nedojde (a o žádném jiném zjevně řeč není).

Toto zadanie je zaujímavé v tom, ako by sa dalo so skúšaným filozoficky diskutovať nad podstatou rôznych fundamentálnych objektov, ktoré sa na to využijú (ja už odpoveď prepisujem odznova tretí krát, vždy ma niečo nové napadlo, čo znegovalo predošlý text). T.j. nie len samotný algoritmus, ale všetka omáčka okolo, čo za akých obmedzení ako urobiť.

Lebo ak máme napr. disk z ľubovoľným prístupom, ten sa dá považovať vlastne za RAM (ako swap file), čiže napríklad by bolo vhodné sa pre účel tohto príkladu pozerať na súbor (a pajpu tiež) z pohľadu, akoby šlo o pásku (zapíšem, pretočím, sekvenčne prečítam). To podľa mňa veľkú časť uchádzačov ani nenapadne (a teda požiadavka "Různých URL je také velké množství, ani ty samotné se nevejdou do paměti." ani nedáva zmysel) - napr. ak budeme predpokladať dostatočne veľké diskové miesto a povedzme unixový systém, naivné riešenie môže byť vytvorenie samostatného súboru obsahujúceho číslo ako počet výskytov pre každé unikátne URL, a potom sekvenčne prechádzať pôvodný súbor a inkrementovať obsah príslušného súboru patriaceho danému URL...

[me vakérav]

Lebo ak máme napr. disk z ľubovoľným prístupom, ten sa dá považovať vlastne za RAM (ako swap file), čiže napríklad by bolo vhodné sa pre účel tohto príkladu pozerať na súbor (a pajpu tiež) z pohľadu, akoby šlo o pásku (zapíšem, pretočím, sekvenčne prečítam). To podľa mňa veľkú časť uchádzačov ani nenapadne (a teda požiadavka "Různých URL je také velké množství, ani ty samotné se nevejdou do paměti." ani nedáva zmysel) - napr. ak budeme predpokladať dostatočne veľké diskové miesto a povedzme unixový systém, naivné riešenie môže byť vytvorenie samostatného súboru obsahujúceho číslo ako počet výskytov pre každé unikátne URL, a potom sekvenčne prechádzať pôvodný súbor a inkrementovať obsah príslušného súboru patriaceho danému URL...

Čili každý načtený řádek s URL povede minimálně k jednomu zápisu na disk?

Jako jo, půjde to, ale bude to nechutně pomalé. Troufám si tvrdit, že tak pomalé, že už bude lepší naalokovat si celý soubor do paměti a spoléhat se na swap (a to bude také hrozné).

Navíc to bude patrně neefektivní i jinak (např. souborové systémy nejsou optimalizované na tak velké množství souborů apod.).

Disk se nedá považovat za RAM, protože RAM je o několik řádů rychlejší. Tahle poučka se nezměnila ani s příchodem SSD.

[gll]

Ne. Unixový sort je zrovna dělán tak, že RAMka nedojde (a o žádném jiném zjevně řeč není).

Toto zadanie je zaujímavé v tom, ako by sa dalo so skúšaným filozoficky diskutovať nad podstatou rôznych fundamentálnych objektov, ktoré sa na to využijú (ja už odpoveď prepisujem odznova tretí krát, vždy ma niečo nové napadlo, čo znegovalo predošlý text). T.j. nie len samotný algoritmus, ale všetka omáčka okolo, čo za akých obmedzení ako urobiť.

Lebo ak máme napr. disk z ľubovoľným prístupom, ten sa dá považovať vlastne za RAM (ako swap file), čiže napríklad by bolo vhodné sa pre účel tohto príkladu pozerať na súbor (a pajpu tiež) z pohľadu, akoby šlo o pásku (zapíšem, pretočím, sekvenčne prečítam). To podľa mňa veľkú časť uchádzačov ani nenapadne (a teda požiadavka "Různých URL je také velké množství, ani ty samotné se nevejdou do paměti." ani nedáva zmysel) - napr. ak budeme predpokladať dostatočne veľké diskové miesto a povedzme unixový systém, naivné riešenie môže byť vytvorenie samostatného súboru obsahujúceho číslo ako počet výskytov pre každé unikátne URL, a potom sekvenčne prechádzať pôvodný súbor a inkrementovať obsah príslušného súboru patriaceho danému URL...

postni sem to řešení. Podle mě plácáš nesmysly.

[gll]

dost záleží na tom, jak vypadají vstupní data. Jestli se tam opakuje pár url, tak řazení není dobrý způsob. Lepší ty county ukládat do slovníku.

V zadání bylo, že ani unikátní URL se nevejdou do paměti.

to jsem přehlédl.

[kkt1]

Ono je vhodne vychazet z urcitych omezeni ktere predem zname. Je rozdil jestli je velikost vstupu v MB nebo v PB a dle toho je rozdil jestli mate k dispozici 2GB ram nebo 2TB ram a to same s mistem na disku. Univerzalni algoritmus bude sice fungovat, ale bude zaroven desne neefektivni a pomaly a na rovinu, k cemu je vam algoritmus ktery se bude snazit radek po radku kopirovat a tridit PB dat kdyz se nedozijete vysledku?